Résumé

La détection des communautés est devenue un domaine de recherche majeur ces dernières années. Plusieurs algorithmes appliqués aux graphes orientés ont été developpés. Ces derniers se focalisent sur la densité de liens à l’intérieur des communautés et considèrent la relation entre les noeuds comme symmétrique, car ils ignorent l’orientation des liens, ce qui biaise les résultats en produisant des communautés non-significatives. Ce document propose un algorithme basé sur l’extraction des kernels via la distribution des triades, utilisant l’optimi- sation de la nouvelle métrique Kernel Degree Clustering (KDC), et trouve des communautés plus sémantiques que la modularité, en accord à la notion de centralisation de l’information. Les expérimentations montrent que la nouvelle approche produit les résultats préconisés que ceux produits par certains algorithmes de détection de communautés de l’état de l’art.

Abstract

Community detection has become a major active area of research in recent years. A plethora of relevant methods have been implemented for directed graphs. Most of them focus on the density of links, and consider the relationship between nodes as symmetric by ignoring links directionality during their clustering step, this leading to non-semantic results. This paper propose an efficient method based on the extraction of kernels through the distribution of triads in the graph, using Kernel Degree Clustering (KDC) a novel metric to judge the quality of a community partitioning, demonstrated to yield superior results over other commonly used metrics like modularity in conformity with centrality. To validate our approach, we conduct experiments on some networks which show that it has better performance over some of the other state-of-the-art methods and uncovers expected communities.