The Topology of Directed Complex Networks: Computational Analysis and Applications

Diplôme Thèse The Topology of Directed Complex Networks: Computational Analysis and Applications eng 2015-05-22 author Dubuisson Jimmy 690731 director Chopard Bastien 22320 director Eckmann Jean-Pierre 0000-0001-6118-1077 24759 10.13097/archive-ouverte/unige:73280 urn:nbn:ch:unige-732800 Sc. 4783 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. Graph theory Complex network Machine learning Natural language processing Classification Authorship detection Random walk Pagerank Dimensionality reduction Metabolic pathway Subgraph extraction Sampling Online social network Monte carlo Algorithmics Heuristic Mapreduce Dewey 500.2 Dewey 025.063 13 Centre universitaire d'informatique 0D3 37 Département de physique théorique 133 32 Département d'informatique 18 false 808 Groupe Eckman 728 Scientific and Parallel Computing 5d773ae4-f605-4682-93d5-7e79a76cd625 Thesis Public The-Topology-of-Directed-Complex-Networks_for-printing_v2.pdf 1438307 application/pdf openAccess Centres et instituts / Centre universitaire d'informatique Faculté des sciences / Section de physique / Département de physique théorique Faculté des sciences / Département d'informatique

Title	Published in	Access level	OA Policy	Year	Views	Downloads

The Topology of Directed Complex Networks: Computational Analysis and Applications				2015	1,168	2,736

Archive ouverte UNIGE

Dubuisson, Jimmy