Group detection in complex networks: An algorithm and comparison of the state of the art
arXiv:1305.5136 · doi:10.1016/j.physa.2013.12.003
Abstract
Complex real-world networks commonly reveal characteristic groups of nodes like communities and modules. These are of value in various applications, especially in the case of large social and information networks. However, while numerous community detection techniques have been presented in the literature, approaches for other groups of nodes are relatively rare and often limited in some way. We present a simple propagation-based algorithm for general group detection that requires no a priori knowledge and has near ideal complexity. The main novelty here is that different types of groups are revealed through an adequate hierarchical group refinement procedure. The proposed algorithm is validated on various synthetic and real-world networks, and rigorously compared against twelve other state-of-the-art approaches on group detection, hierarchy discovery and link prediction tasks. The algorithm is comparable to the state of the art in community detection, while superior in general group detection and link prediction. Based on the comparison, we also dis- cuss some prominent directions for future work on group detection in complex networks.
15 pages, 6 figures, 6 tables
References in corpus (38)
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- The large-scale organization of metabolic networks
- Random graphs with arbitrary degree distributions and their applications
- Near linear time algorithm to detect community structures in large-scale networks
- Mixing patterns in networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Defining and identifying communities in networks
- Community detection algorithms: a comparative analysis
- Stochastic blockmodels and community structure in networks
- The Dynamics of Viral Marketing
- An information-theoretic framework for resolving community structure in complex networks
- Mixture models and exploratory analysis in networks
- Robustness of community structure in networks
- Graph Evolution: Densification and Shrinking Diameters
- Towards real-time community detection in large networks
- A sequential algorithm for fast clique percolation
- Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
- Robust network community detection using balanced propagation
- Structural Inference of Hierarchies in Networks
- Entropy of stochastic blockmodel ensembles
- Role models for complex networks
- Community structure of complex software systems: Analysis and applications
- Protein-Interaction-Networks: More than mere modules
- Ubiquitousness of link-density and link-pattern communities in real-world networks
- Software systems through complex networks science: Review, analysis and applications
- Discovering Network Structure Beyond Communities
- Generalized network community detection