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

作者：He, Dongxiao; Liu, Jie; Yang, Bo; Huang, Yuxiao; Liu, Dayou^*; Jin, Di

来源：Advances in Complex Systems, 2012, 15(8): 1250036.

DOI：10.1142/S0219525912500361

• Complex networks
• community detection
• ant-based algorithm
• simulated annealing
• modularity

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.

• 出版日期2012-12
• 单位吉林大学