The Topology of Directed Complex Networks: Computational Analysis and Applications

Cette thèse est consacrée à l'étude de la topologie des réseaux complexes orientés basée sur l'analyse computationnelle et statistique, ainsi qu'au développement de nouveaux outils computationnels dédiés à l'analyse de données modélisées sous forme de graphes orientés. Dans la première partie, nous nous intéressons à l'analyse de graphes orientés modélisant un ensemble d'associations libres. Après avoir isolé le “core” du graphe d'associations libres (i.e., sa composante fortement connexe principale), nous analysons ses propriétés topologiques fondamentales et vérifions que la grande majorité des noeuds du “core” appartiennent à un triangle. Nous en déduisons que les triangles jouent un rôle essentiel dans la structure du graphe, et observons que ce dernier se décompose de manière homogène en un ensemble de grappes de triangles (i.e., sous-graphes complets de triangles) de tailles comparables. Nous démontrons pour finir que ces grappes de triangles regroupent des mots fortement liés du point de vue sémantique, et nous en concluons que les triangles constituent des “briques” sémantiques fondamentales du réseau sémantique formé par le “core”. Dans la deuxième partie, nous présentons une nouvelle méthode d'analyse de données basée sur l'utilisation de processus de diffusion sur un graphe orienté. Pour une base de données modélisée sous forme d'un graphe orienté, l'idée est de générer des vecteurs numériques de grande dimension à partir des valeurs de la distribution d'une marche aléatoire biaisée associée à chacun des noeuds du graphe. En faisant démarrer ces processus de diffusion à partir de sous-ensembles quelconques de la base de données considérée, nous sommes ainsi en mesure de générer des “signatures” (nous utilisons le terme de “diffusion fingerprints”) permettant de caractériser ces sous-ensembles. Nous appliquons notre méthode à des problèmes de fouille de graphe et de classification textuelle et présentons une heuristique permettant de réduire la dimension des vecteurs de diffusion générés, pour un coût computationnel négligeable. Dans la troisième partie, nous nous intéressons au problème consistant à échantilloner un réseau complexe orienté de très grande taille, dans le cas où il n'est pas possible de l'explorer entièrement, et que sa structure n'est connue que très partiellement. Nous commençons par décrire un ensemble de mesures fondamentales dont nous souhaitons que les valeurs soit préservées au mieux dans l'échantillon extrait, et présentons un ensemble d'algorithmes déterministes et probabilistes permettant de calculer ces mesures sur des graphes de très grande taille. Nous discutons ensuite des méthodes existantes visant à obtenir des échantillons uniformes de noeuds pour des graphes non-orientés et orientés. Enfin, nous décrivons une heuristique qui, sous les contraintes fortes que nous nous sommes fixées, explore un graphe orienté de manière itérative à partir d'un noeud sélectionné au hasard, en cherchant à en extraire un sous-graphe connecté reproduisant le mieux possible ses caractéristiques fondamentales