AN ANT-BASED ALGORITHM WITH LOCAL OPTIMIZATION FOR COMMUNITY DETECTION IN LARGE-SCALE NETWORKS

Dongxiao He (), Jie Liu (), Bo Yang (), Yuxiao Huang (), Dayou Liu () and Di Jin ()
Additional contact information
Dongxiao He: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
Jie Liu: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
Bo Yang: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
Yuxiao Huang: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
Dayou Liu: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
Di Jin: College of Computer Science and Technology, Jilin University, Changchun, 130012, China;

Advances in Complex Systems (ACS), 2012, vol. 15, issue 08, 1-26

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.

Keywords: Complex networks; community detection; ant-based algorithm; simulated annealing; modularity (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525912500361
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:15:y:2012:i:08:n:s0219525912500361

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525912500361

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().