Paper Info
Title
Ant colony optimization with Markov random walk for community detection in graphs
Abstract
Network clustering problem (NCP) is the problem associated to the detection of network community structures. Building on Markov random walks we address this problem with a new ant colony optimization strategy, named as ACOMRW, which improves prior results on the NCP problem and does not require knowledge of the number of communities present on a given network. The framework of ant colony optimization is taken as the basic framework in the ACOMRWalgorithm. At each iteration, a Markov random walk model is taken as heuristic rule; all of the ants' local solutions are aggregated to a global one through 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 performance of algorithm ACOMRW was tested on a set of benchmark computer-generated networks, and as well on real-world network data sets. Experimental results confirm the validity and improvements met by this approach.
Year
DOI
Venue
2011
10.1007/978-3-642-20847-8_11
PAKDD (2)
Keywords
Field
DocType
ant colony optimization,markov random walk,ncp problem,network community structure,community detection,benchmark computer-generated network,algorithm acomrw,markov random walk model,basic framework,real-world network data set,complex network
Ant colony optimization algorithms,Data mining,Heuristic,Community structure,Computer science,Random walk,Matrix (mathematics),Markov chain,Complex network,Artificial intelligence,Cluster analysis,Machine learning
Conference
Volume
ISSN
Citations 
6635
0302-9743
4
PageRank 
References 
Authors
0.52
7
5
Name
Order
Citations
PageRank
Di Jin131749.25
Dayou Liu281468.17
Bo Yang382264.08
Carlos Baquero4674.65
Dongxiao He520128.10