Vertex-centred Method to Detect Communities in Evolving Networks
Résumé
Finding communities in evolving networks is a difficult task and raises issues different from the classic static detection case. We introduce an approach based on the recent vertex-centred paradigm. The proposed algorithm, named DynLOCNeSs, detects communities by scanning and evaluating each vertex neighbourhood, which can be done independently in a parallel way. It is done by means of a preference measure, using these preferences to handle community changes. We also introduce a new vertex neighbourhood preference measure, CWCN, more efficient than current existing ones in the considered context. Experimental results show the relevance of this measure and the ability of the proposed approach to detect classical community evolution patterns such as grow-shrink and merge-split.
Trouver des communautés dans des réseaux évoluant avec le temps est une tâche difficile et soulève des questions différentes du cas statique. We proposons une approche basée sur le paradigme orienté-sommet. L'algorithme dont cet article fait l'objet, nommé DynLOCNeSs, détecte les communautés en explorant le voisinage de chaque sommet indépendamment, tâche qui peut être parallélisée. Cette exploration est réalisée à l'aide d'une mesure de préférence, également utilisée cette mesure pour gérer les changements de communautés. Nous introduisons également une nouvelle mesure de préférences entre sommets nommée CWCN, plus efficace que les mesures existantes dans le contexte considéré. Les résultats expérimentaux montrent la pertinence de cette mesure et de l'approche, ainsi que leur capacité à détecter les motifs classiques d'évolutions de communautés grow-shrink (augmentation-rétrécissement) et merge-split (fusion-séparation).
Origine : Fichiers produits par l'(les) auteur(s)