Déplier la structure communautaire d’un réseau en mesurant la proximité aux représentants de communauté

International audienceHow to find all overlapping communities in a complex network? That is, how to find all relevant groups of nodes in a linked dataset? No entirely satisfying solution to that important problem exists, having a criterion to decide which group is relevant and finding quickly these groups in large networks are bottlenecks. We found that in many networks the number of these groups is limited and that there exist, for each group, at least one node that can characterize it by itself: a node belonging only to that group and important within it. We call such a node a community representative. We develop an algorithm to find these overlapping communities. The community detection is done through measuring the proximities of all nodes to the representatives and then finding irregularities in the decrease of these values reflecting the presence of relevant groups. We show that our approach handles very large real-world networks and have comparable or even better performances compared to state of the art methods.Nous proposons un algorithme pour déplier la structure communautaire des grands graphes de terrain. L'algorithme est basé sur la détection de la communauté de chaque représentant communautaire : noeud contenu dans une seule communauté et important en son sein. Cette détection est faite avec une approche à base de mesure de proximité développée récemment. Par comparaison avec d'autres méthodes de l'état de l'art nous montrons que notre algorithme a des performances équivalentes voire meilleures et est capable de traiter les plus grands graphes de terrain