Overlapping Community Detection Versus Ground-Truth in AMAZON Co-Purchasing Network

Malek Jebabli (1) , Hocine Cherifi (1) , Chantal Cherifi (2) , Atef Hamouda (3)

1 Le2i - Laboratoire Electronique, Informatique et Image [UMR6306]
2 DISP - Décision et Information pour les Systèmes de Production
3 UTM - Université de Tunis El Manar

Objective evaluation of community detection algorithms is a strategic issue. Indeed, we need to verify that the communities identified are actually the good ones. Moreover, it is necessary to compare results between two distinct algorithms to determine which is most effective. Classically, validations rely on clustering comparison measures or on quality metrics. Although, various traditional performance measures are used extensively. It appears very clearly that they cannot distinguish community structures with different topological properties. It is therefore necessary to propose an alternative methodology more sensitive to the community structure variations in order to conduct more effective comparisons. In this paper, we present a framework to tackle this challenge through a comprehensive analysis of the community structure of overlapping community structured networks. We illustrate our approach with an experimental analysis of a real-world network with a ground-truth community structure that we compare with the output of eight different overlapping community detection procedures, representative of categories of popular algorithms available in the literature. The results allow a better understanding of their behavior. Furthermore, they demonstrate that more emphasis should be put on the topology of the uncovered community structure in order to evaluate the effectiveness of community detection algorithms.

Mots clés: Community structure; detection algorithms; overlap- ping community networks; network analysis

Domaines: Informatique [cs]

Malek Jebabli, Hocine Cherifi, Chantal Cherifi, Atef Hamouda. Overlapping Community Detection Versus Ground-Truth in AMAZON Co-Purchasing Network. 11th IEEE International Conference on Signal-Image Technology & Internet-Based Systems (SITIS 2015), University of Bourgogne; University of Milan, Nov 2015, Bangkok, Thailand. pp.328 - 336, ⟨10.1109/SITIS.2015.47⟩. ⟨hal-01534523⟩