On Accuracy of Community Structure Discovery Algorithms
arXiv:1112.4134 · doi:10.4156/jcit.vol6.issue11.32
Abstract
Community structure discovery in complex networks is a quite challenging problem spanning many applications in various disciplines such as biology, social network and physics. Emerging from various approaches numerous algorithms have been proposed to tackle this problem. Nevertheless little attention has been devoted to compare their efficiency on realistic simulated data. To better understand their relative performances, we evaluate systematically eleven algorithms covering the main approaches. The Normalized Mutual Information (NMI) measure is used to assess the quality of the discovered community structure from controlled artificial networks with realistic topological properties. Results show that along with the network size, the average proportion of intra-community to inter-community links is the most influential parameter on performances. Overall, "Infomap" is the leading algorithm, followed by "Walktrap", "SpinGlass" and "Louvain" which also achieve good consistency.
References in corpus (12)
- The structure and function of complex networks
- Finding and evaluating community structure in networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Defining and identifying communities in networks
- Statistical Mechanics of Community Detection
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- An information-theoretic framework for resolving community structure in complex networks
- Evaluating Local Community Methods in Networks