Contribution to community discovery in complex networks contribution à la détection des communautés dans les réseaux complexes

Abstract

Les réseaux complexes sont des ensembles constitués d’un grand nombre d’entités interconnectées par des liens. Ils ont en effet eu un essor important en biologie, transports, réseaux sociaux en ligne, etc. Parmi celles-ci, de nombreuses applications récentes traitent d’immenses volumes de données personnelles ou publiques qui en découlent. Les réseaux complexes sont modélisés par des graphes dans lesquels les nœuds représentent les entités et les arêtes entre les nœuds représentent les liens entre ces entités. Ces entités ont généralement tendance à se regrouper en communautés, en fonction de certains critères de similarité ou de connectivité. Ceci constitue une problématique d’actualité appelée "détection des communautés". Une pléthore de méthodes de détection de communautés ont été implémentées. Toutefois, plusieurs d’entre elles considèrent que les communautés devraient être denses et par conséquent ne tiennent pas compte de l’intérêt des entités d’une même communauté. Lorsque l’intérêt est pris en compte, il est basé sur la sémantique. La sémantique possède la limite principale que le réseau devrait être préalablement connu pour être exploité. Ainsi, un aspect fondamental reste à considérer, à savoir l’intérêt basé sur la topologie qui n’exige pas une connaissance a priori de l’entièreté du réseau. Les travaux de recherche présentés dans ce manuscrit exploitent les graphes orientés, attribués et multidimensionnels et proposent des nouvelles méthodes de détection des communautés d’intérêt. De ce fait, nous proposons dans la première contribution, une méthode de détection de communautés d’intérêt dans les réseaux orientés, basée sur les triades, à travers une approche centrée graine. En effet, la triade constitue une structure topologique élémentaire plus significative que les structures centrées autour de l’acteur et de la diade, car elle offre plus de configurations. Nous définissons ainsi une mesure de similarité permettant d’implémenter l’importance des liens entrants par rapport à ceux sortants. Ainsi les communautés obtenues sont denses en triades. Cette densité traduit l’idée selon laquelle les nœuds de la même communauté adhèrent à l’opinion forte des nœuds d’intérêt préalablement identifiés. La deuxième contribution propose une méthode hybride d’optimisation d’une nouvelle fonction de qualité, la modularité hybride. Celle-ci intègre la modularité classique de Newman et une modularité basée sur les attributs et l’orientation des liens à travers la précédente mesure de similarité. Cette méthode est appliquée aux graphes attribués et permet d’identifier des communautés d’intérêt dont les entités sont topologiquement similaires et homogènes par leurs attributs. A travers cette méthode hybride, la densité des liens n’est pas garantie, mais l’intérêt relatif à l’équivalence topologique et à l’homogénéité des attributs est assurée. Enfin, pour le cas des graphes multidimensionnels modélisant plusieurs types d’interactions entre deux entités, nous proposons dans la troisième contribution une méthode d’identification de communautés dont l’intérêt est modélisé par le niveau d’activité d’un nœud dans une dimension. Ces méthodes sont basées sur des techniques d’apprentissage automatique. Nos algorithmes mis en œuvre sur des exemples de graphes du contexte, confirment leur pertinence en extrayant des groupes d’entités plus homogènes par des caractéristiques topologiques communes.