An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
arXiv:1303.4711 · doi:10.1142/S0219525912500361
Abstract
In this paper, we propose a multi-layer ant-based algorithm MABA, which detects communities from networks by means of locally optimizing modularity using individual ants. The basic version of MABA, namely SABA, combines a self-avoiding label propagation technique with a simulated annealing strategy for ant diffusion in networks. Once the communities are found by SABA, this method can be reapplied to a higher level network where each obtained community is regarded as a new vertex. The aforementioned process is repeated iteratively, and this corresponds to MABA. Thanks to the intrinsic multi-level nature of our algorithm, it possesses the potential ability to unfold multi-scale hierarchical structures. Furthermore, MABA has the ability that mitigates the resolution limit of modularity. The proposed MABA has been evaluated on both computer-generated benchmarks and widely used real-world networks, and has been compared with a set of competitive algorithms. Experimental results demonstrate that MABA is both effective and efficient (in near linear time with respect to the size of network) for discovering communities.
18 pages,7 figures, 4 tables. arXiv admin note: text overlap with arXiv:0803.0476, arXiv:cond-mat/0309508 by other authors
References in corpus (23)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Maps of random walks on complex networks reveal community structure
- The structure of scientific collaboration networks
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale 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
- Hierarchical structure and the prediction of missing links in networks
- Link communities reveal multiscale complexity in networks
- The performance of modularity maximization in practical contexts
- A Local Method for Detecting Communities
- Multiresolution community detection for megascale networks by information-based replica correlations
- Maximizing Modularity is hard
- Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks