Community detection algorithm evaluation with ground-truth data
| Autor: | Chantal Cherifi, Hocine Cherifi, Malek Jebabli, Atef Hamouda |
|---|---|
| Přispěvatelé: | Université de Bourgogne (UB), Université de Tunis El Manar (UTM), Décision et Information pour les Systèmes de Production (DISP), Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Unité de Recherche en Programmation Algorithmique et Heuristique (URPAH), Faculté des Sciences Mathématiques, Physiques et Naturelles de Tunis (FST), Université de Tunis El Manar (UTM)-Université de Tunis El Manar (UTM) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Statistics and Probability
Computer science ‘Community-graph’ Community structure Variation (game tree) [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Complex network Condensed Matter Physics 01 natural sciences Graph 010305 fluids & plasmas Set (abstract data type) 0103 physical sciences Network analysis 010306 general physics Cluster analysis Algorithm |
| Zdroj: | Physica A: Statistical Mechanics and its Applications Physica A: Statistical Mechanics and its Applications, Elsevier, 2018, 492, pp.651-706. ⟨10.1016/j.physa.2017.10.018⟩ |
| ISSN: | 0378-4371 |
| DOI: | 10.1016/j.physa.2017.10.018⟩ |
| Popis: | International audience; Community structure is of paramount importance for the understanding of complex networks. Consequently, there is a tremendous effort in order to develop efficient community detection algorithms. Unfortunately, the issue of a fair assessment of these algorithms is a thriving open question. If the ground-truth community structure is available, various clustering-based metrics are used in order to compare it versus the one discovered by these algorithms. However, these metrics defined at the node level are fairly insensitive to the variation of the overall community structure. To overcome these limitations, we propose to exploit the topological features of the ‘community graphs’ (where the nodes are the communities and the links represent their interactions) in order to evaluate the algorithms. To illustrate our methodology, we conduct a comprehensive analysis of overlapping community detection algorithms using a set of real-world networks with known a priori community structure. Results provide a better perception of their relative performance as compared to classical metrics. Moreover, they show that more emphasis should be put on the topology of the community structure. We also investigate the relationship between the topological properties of the community structure and the alternative evaluation measures (quality metrics and clustering metrics). It appears clearly that they present different views of the community structure and that they must be combined in order to evaluate the effectiveness of community detection algorithms. © 2017 Elsevier B.V. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect