Dynamic network formation

Dynamique de formation des réseaux

Rémi Varloot (1, 2)

1 DI-ENS - Département d'informatique - ENS Paris
2 DYOGENE - Dynamics of Geometric Networks

This thesis focuses on the rapid mixing of graph-related Markov chains. The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium. The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs.

Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes. La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l’importance des transitions le long d’une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l’une de ces dynamiques, d’un temps de mélange rapide. Nous définissons notamment l’expansion partielle d’un graphe. Celle-ci permet de suivre l’avancement de la dynamique, partant d’un état de faible expansion, jusqu’à obtention d’une bonne expansion à l’équilibre. La fin de cette thèse porte sur une amélioration de l’algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l’échantillonnage préférentiel, qui permet de réduire la complexité de l’algorithme. Nous fournissons une preuve de correction, ainsi qu’une étude de l’impact de cette méthode sur la vitesse d’échantillonnage d’ensembles indépendants pour certains graphes.

Mots clés: Social networks; Dynamic graphs; Markov chains

Mots clés: Réseaux sociaux; Graphes dynamiques; Chaînes de Markov

Domaines: Algorithme et structure de données [cs.DS]; Enseignement de la physique [physics.ed-ph]

Rémi Varloot. Dynamic network formation. Data Structures and Algorithms [cs.DS]. Université Paris sciences et lettres, 2018. English. ⟨NNT : 2018PSLEE048⟩. ⟨tel-02385281⟩