ANT COLONY OPTIMIZATION WITH A NEW RANDOM WALK MODEL FOR COMMUNITY DETECTION IN COMPLEX NETWORKS

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

来源：Advances in Complex Systems, 2011, 14(5): 795-815.

DOI：10.1142/S0219525911003219

• Complex network
• community detection
• ant colony optimization
• clustering ensemble
• Markov random walk

Detecting communities from complex networks has recently triggered great interest. Aiming at this problem, a new ant colony optimization strategy building on the Markov random walks theory, which is named as MACO, is proposed in this paper. The framework of ant colony optimization is taken as the basic framework in this algorithm. In each iteration, a Markov random walk model is employed as heuristic rule; all of the ants' local solutions are aggregated to a global one through an idea of clustering ensemble, which then will be used to update a pheromone matrix. The strategy relies on the progressive strengthening of within-community links and the weakening of between-community links. Gradually this converges to a solution where the underlying community structure of the complex network will become clearly visible. The proposed MACO has been evaluated both on synthetic benchmarks and on some real-world networks, and compared with some present competing algorithms. Experimental result has shown that MACO is highly effective for discovering communities.

• 出版日期2011-10
• 单位吉林大学