Metric properties of large graphs
Identifieur interne : 000095 ( Hal/Corpus ); précédent : 000094; suivant : 000096Metric properties of large graphs
Auteurs : Guillaume DucoffeSource :
Descripteurs français
- mix :
English descriptors
- mix :
Abstract
Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example
Url:
Links to Exploration step
Hal:tel-01485328Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Metric properties of large graphs</title><title xml:lang="fr">Propriétés métriques des grands graphes</title><author><name sortKey="Ducoffe, Guillaume" sort="Ducoffe, Guillaume" uniqKey="Ducoffe G" first="Guillaume" last="Ducoffe">Guillaume Ducoffe</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-211142" status="VALID"><idno type="RNSR">201322124W</idno><orgName>Combinatorics, Optimization and Algorithms for Telecommunications</orgName><orgName type="acronym">COATI</orgName><desc><address><addrLine>2004 route des Lucioles BP 93 F-06902 Sophia Antipolis (France)</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/coati</ref></desc><listRelation><relation active="#struct-34586" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-451999" type="direct"></relation><relation active="#struct-13009" type="indirect"></relation><relation active="#struct-117617" type="indirect"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID"> <idno type="RNSR">198318250R</idno> <orgName>Inria Sophia Antipolis - Méditerranée </orgName> <orgName type="acronym">CRISAM</orgName> <desc> <address> <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/sophia/</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"> <orgName>Institut National de Recherche en Informatique et en Automatique</orgName> <orgName type="acronym">Inria</orgName> <desc> <address> <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/en/</ref> </desc> </org></tutelle><tutelle active="#struct-451999" type="direct"><org type="department" xml:id="struct-451999" status="VALID"><orgName>COMmunications, Réseaux, systèmes Embarqués et Distribués</orgName><orgName type="acronym">COMRED</orgName><date type="start">2016-03-02</date><desc><address><addrLine>Laboratoire I3SCS 4012106903 Sophia Antipolis Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.i3s.unice.fr/comred</ref></desc><listRelation><relation active="#struct-13009" type="direct"></relation><relation active="#struct-117617" type="indirect"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-13009" type="indirect"><org type="laboratory" xml:id="struct-13009" status="VALID"><orgName>Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis</orgName><orgName type="acronym">I3S</orgName><desc><address><addrLine>2000, route des Lucioles - Les Algorithmes - bât. Euclide B 06900 Sophia Antipolis</addrLine><country key="FR"></country></address><ref type="url">http://www.i3s.unice.fr/</ref></desc><listRelation><relation active="#struct-117617" type="direct"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-117617" type="indirect"><org type="institution" xml:id="struct-117617" status="VALID"> <orgName>Université Nice Sophia Antipolis</orgName> <orgName type="acronym">UNS</orgName> <desc> <address> <addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine> <country key="FR"></country> </address> <ref type="url">http://unice.fr/</ref> </desc> <listRelation> <relation active="#struct-523042" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-523042" type="indirect"><org type="regroupinstitution" xml:id="struct-523042" status="VALID"> <orgName>Université Côte d'Azur </orgName> <orgName type="acronym">UCA</orgName> <date type="start">2015-03-01</date> <desc> <address> <addrLine>Parc Valrose, 28 avenue Valrose 06108 Nice Cedex 2 </addrLine> <country key="FR"></country> </address> </desc> </org></tutelle><tutelle name="UMR7271" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno> <idno type="ISNI">0000000122597504</idno> <orgName>Centre National de la Recherche Scientifique</orgName> <orgName type="acronym">CNRS</orgName> <date type="start">1939-10-19</date> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.cnrs.fr/</ref> </desc> </org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:tel-01485328</idno><idno type="halId">tel-01485328</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-01485328</idno><idno type="url">https://tel.archives-ouvertes.fr/tel-01485328</idno><date when="2016-12-09">2016-12-09</date><idno type="wicri:Area/Hal/Corpus">000095</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Metric properties of large graphs</title><title xml:lang="fr">Propriétés métriques des grands graphes</title><author><name sortKey="Ducoffe, Guillaume" sort="Ducoffe, Guillaume" uniqKey="Ducoffe G" first="Guillaume" last="Ducoffe">Guillaume Ducoffe</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-211142" status="VALID"><idno type="RNSR">201322124W</idno><orgName>Combinatorics, Optimization and Algorithms for Telecommunications</orgName><orgName type="acronym">COATI</orgName><desc><address><addrLine>2004 route des Lucioles BP 93 F-06902 Sophia Antipolis (France)</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/coati</ref></desc><listRelation><relation active="#struct-34586" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-451999" type="direct"></relation><relation active="#struct-13009" type="indirect"></relation><relation active="#struct-117617" type="indirect"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-34586" type="direct"><org type="laboratory" xml:id="struct-34586" status="VALID"> <idno type="RNSR">198318250R</idno> <orgName>Inria Sophia Antipolis - Méditerranée </orgName> <orgName type="acronym">CRISAM</orgName> <desc> <address> <addrLine>2004 route des Lucioles BP 93 06902 Sophia Antipolis</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/centre/sophia/</ref> </desc> <listRelation> <relation active="#struct-300009" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"> <orgName>Institut National de Recherche en Informatique et en Automatique</orgName> <orgName type="acronym">Inria</orgName> <desc> <address> <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.inria.fr/en/</ref> </desc> </org></tutelle><tutelle active="#struct-451999" type="direct"><org type="department" xml:id="struct-451999" status="VALID"><orgName>COMmunications, Réseaux, systèmes Embarqués et Distribués</orgName><orgName type="acronym">COMRED</orgName><date type="start">2016-03-02</date><desc><address><addrLine>Laboratoire I3SCS 4012106903 Sophia Antipolis Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.i3s.unice.fr/comred</ref></desc><listRelation><relation active="#struct-13009" type="direct"></relation><relation active="#struct-117617" type="indirect"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-13009" type="indirect"><org type="laboratory" xml:id="struct-13009" status="VALID"><orgName>Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis</orgName><orgName type="acronym">I3S</orgName><desc><address><addrLine>2000, route des Lucioles - Les Algorithmes - bât. Euclide B 06900 Sophia Antipolis</addrLine><country key="FR"></country></address><ref type="url">http://www.i3s.unice.fr/</ref></desc><listRelation><relation active="#struct-117617" type="direct"></relation><relation active="#struct-523042" type="indirect"></relation><relation name="UMR7271" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-117617" type="indirect"><org type="institution" xml:id="struct-117617" status="VALID"> <orgName>Université Nice Sophia Antipolis</orgName> <orgName type="acronym">UNS</orgName> <desc> <address> <addrLine>Parc Valrose - BP 2135 - 06103 Nice cedex 2</addrLine> <country key="FR"></country> </address> <ref type="url">http://unice.fr/</ref> </desc> <listRelation> <relation active="#struct-523042" type="direct"></relation> </listRelation> </org></tutelle><tutelle active="#struct-523042" type="indirect"><org type="regroupinstitution" xml:id="struct-523042" status="VALID"> <orgName>Université Côte d'Azur </orgName> <orgName type="acronym">UCA</orgName> <date type="start">2015-03-01</date> <desc> <address> <addrLine>Parc Valrose, 28 avenue Valrose 06108 Nice Cedex 2 </addrLine> <country key="FR"></country> </address> </desc> </org></tutelle><tutelle name="UMR7271" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno> <idno type="ISNI">0000000122597504</idno> <orgName>Centre National de la Recherche Scientifique</orgName> <orgName type="acronym">CNRS</orgName> <date type="start">1939-10-19</date> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.cnrs.fr/</ref> </desc> </org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algorithms</term><term>Boolean function learning</term><term>Coloring games</term><term>Complexity in P</term><term>Graph</term><term>Gromov Hyperbolicity</term><term>Nash equilibrium</term><term>Treebreadth</term><term>Treelength</term><term>Treewidth</term></keywords><keywords scheme="mix" xml:lang="fr"><term>Algorithmes</term><term>Apprentissage de fonction booléenne</term><term>Complexité dans P</term><term>Graphe</term><term>Hyperbolicité</term><term>Jeux de coloration</term><term>Équilibre de Nash</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Metric properties of large graphs</title><title xml:lang="fr">Propriétés métriques des grands graphes</title><author role="aut"><persName><forename type="first">Guillaume</forename><surname>Ducoffe</surname></persName><idno type="halauthorid">1101973</idno><affiliation ref="#struct-211142"></affiliation></author><editor role="depositor"><persName><forename>ABES</forename><surname>STAR</surname></persName><email type="md5">f5aa7f563b02bb6adbba7496989af39a</email><email type="domain">abes.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2017-03-08 15:56:06</date><date type="whenModified">2018-01-31 10:24:06</date><date type="whenReleased">2017-03-14 09:41:35</date><date type="whenProduced">2016-12-09</date><date type="whenEndEmbargoed">2017-03-08</date><ref type="file" target="https://tel.archives-ouvertes.fr/tel-01485328/document"><date notBefore="2017-03-08"></date></ref><ref type="file" subtype="author" n="1" target="https://tel.archives-ouvertes.fr/tel-01485328/file/2016AZUR4134.pdf"><date notBefore="2017-03-08"></date></ref></edition><respStmt><resp>contributor</resp><name key="131274"><persName><forename>ABES</forename><surname>STAR</surname></persName><email type="md5">f5aa7f563b02bb6adbba7496989af39a</email><email type="domain">abes.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">tel-01485328</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-01485328</idno><idno type="halBibtex">ducoffe:tel-01485328</idno><idno type="halRefHtml">Other [cs.OH]. Université Côte d'Azur, 2016. English. 〈NNT : 2016AZUR4134〉</idno><idno type="halRef">Other [cs.OH]. Université Côte d'Azur, 2016. English. 〈NNT : 2016AZUR4134〉</idno></publicationStmt><seriesStmt><idno type="stamp" n="STAR">STAR - Dépôt national des thèses électroniques</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="UNICE">Université Nice Sophia Antipolis</idno><idno type="stamp" n="INRIASO">INRIA-SOPHIA</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="INRIA2">INRIA 2</idno><idno type="stamp" n="INRIA-SOPHIA">INRIA Sophia Antipolis - Méditerranée</idno><idno type="stamp" n="I3S">Laboratoire d'Informatique, Signaux et Systèmes de Sophia-Antipolis</idno><idno type="stamp" n="UCA-TEST">UCA-TEST</idno><idno type="stamp" n="UNIV-COTEDAZUR">Université Côte d'Azur</idno></seriesStmt><notesStmt></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Metric properties of large graphs</title><title xml:lang="fr">Propriétés métriques des grands graphes</title><author role="aut"><persName><forename type="first">Guillaume</forename><surname>Ducoffe</surname></persName><idno type="halauthorid">1101973</idno><affiliation ref="#struct-211142"></affiliation></author></analytic><monogr><idno type="nnt">2016AZUR4134</idno><imprint><date type="dateDefended">2016-12-09</date></imprint><authority type="institution">Université Côte d'Azur</authority><authority type="school">École doctorale Sciences et technologies de l'information et de la communication (Sophia Antipolis, Alpes-Maritimes)</authority><authority type="supervisor">David Coudert</authority><authority type="jury">Victor Chepoi [Rapporteur]</authority><authority type="jury">Laurent Viennot [Rapporteur]</authority><authority type="jury">Michele Flammini</authority><authority type="jury">Cyril Gavoille</authority><authority type="jury">Nicolas Nisse</authority><authority type="jury">Robert Endre Tarjan</authority></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">Graph</term><term xml:lang="en">Algorithms</term><term xml:lang="en">Complexity in P</term><term xml:lang="en">Gromov Hyperbolicity</term><term xml:lang="en">Treelength</term><term xml:lang="en">Treebreadth</term><term xml:lang="en">Treewidth</term><term xml:lang="en">Coloring games</term><term xml:lang="en">Nash equilibrium</term><term xml:lang="en">Boolean function learning</term><term xml:lang="fr">Algorithmes</term><term xml:lang="fr">Complexité dans P</term><term xml:lang="fr">Hyperbolicité</term><term xml:lang="fr">Jeux de coloration</term><term xml:lang="fr">Équilibre de Nash</term><term xml:lang="fr">Apprentissage de fonction booléenne</term><term xml:lang="fr">Graphe</term></keywords><classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode><classCode scheme="halTypology" n="THESE">Theses</classCode></textClass><abstract xml:lang="en">Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example</abstract><abstract xml:lang="fr">Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Psychologie/explor/BernheimV1/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000095 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 000095 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Psychologie
|area= BernheimV1
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:tel-01485328
|texte= Metric properties of large graphs
}}
| This area was generated with Dilib version V0.6.33. |  |