Détection de communautés dans les grands graphes de terrain
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Complex networks are useful objects for modeling many phenomena in several domains (sociology, linguistic, epidemiology, computer science, biology, etc). These graphs have non-trivial common structural properties, among wich the presence of communities (sets of vertices highly connected internally and less connected with external vertices). We developed in this thesis two complementary algorithms in order to detect community structures in complex networks. The first one computes a hierarchical structure of communities (dendrogram) from a distance based on random walks. This distance measures the structural similarity between vertices. The second one finds, from a dendrogram (obtained by our approach or any other), relevant partitions of vertices into communities at different scales. This algorithm is based on the optimization of quality functions. Finally, we propose a comparative analysis of the main existing community detection algorithms. This experimental evaluation uses both real world and generated networks.
Abstract FR:
Les grands graphes de terrain (encore appelés réseaux d'interactions ou réseaux complexes) permettent de modéliser de nombreux phénomènes dans diverses disciplines (sociologie, linguistique, épidémiologie, informatique, biologie, etc). Ces graphes possèdent des propriétés structurelles non-triviales communes parmi lesquelles la présence de communautés (c'est à dire des ensemble de sommets fortement connectés entre eux et plus faiblement vers l'extérieur). Nous proposons dans cette thèse deux nouveaux algorithmes complémentaires de détection de communautés dans les grands graphes de terrain. Le premier calcule une structure hiérarchique de communautés (dendrogramme) à partir d'une distance. Cette distance, basée sur les marches aléatoires, mesure la similarité structurelle des sommets. Le second algorithme permet, à partir d'un dendrogramme (calculé par notre approche ou par toute autre approche), de déterminer les partitions pertinentes des sommets en communautés à diverses échelles. Cet algorithme se base sur l'optimisation de fonctions de qualité. Nous proposons finalement une analyse comparative des principales approches de détection de communautés existantes. Cette analyse expérimentale utilise un large jeu de graphes test réels et générés.