Complex networks display community structures. Nodes within groups are densely connected but
among groups are sparsely connected. In this paper, an algorithm is presented for community detection named
Markov Random Walks Ants (MRWA). The algorithm is inspired by Markov random walks model theory, and
the probability of ants located in any node within a cluster will be greater than that located outside the cluster.
Through the random walks, the network structure is revealed. The algorithm is a stochastic method which uses
the information collected during the traverses of the ants in the network. The algorithm is validated on different
datasets including computer-generated networks and real-world networks. The outcome shows the algorithm
performs moderately quickly when providing an acceptable time complexity and its result appears good in practice.
MA Jian *(马健), FAN Jianping (樊建平), LIU Feng (刘峰), LI Honghui (李红辉)
. A Community Detection Algorithm Based on Markov Random Walks Ants in Complex Network[J]. Journal of Shanghai Jiaotong University(Science), 2019
, 24(1)
: 71
-77
.
DOI: 10.1007/s12204-019-2041-2
[1] NEWMAN M E J. Fast algorithm for detecting communitystructure in networks [J]. Physical Review E,2004, 69(6): 066133.
[2] GIRVAN M, NEWMAN M E J. Community structurein social and biological networks [J]. Proceedings of theNational Academy of Sciences of the United States ofAmerica, 2002, 99(12): 7821-7826.
[3] RAGHAVAN U N, ALBERT R, KUMARA S. Nearliner time algorithm to detect community structuresin large-scale networks [J]. Physical Review E, 2007,76(3): 036106.
[4] PONS P, LATAPY M. Computing communities inlarge networks using random walks [J]. Journal ofGraph Algorithms and Applications, 2006, 10(2): 191-218.
[5] ROSVALL M, BERGSTROM C T. Maps of randomwalks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciencesof the United States of America, 2008, 105(4):1118-1123.
[6] SU C, JIA X T, XIE X Z, et al. A new randomwalkbased label propagation community detection algorithm[C]//IEEE/WIC/ACM International Conferenceon Web Intelligence and Intelligent Agent Technology.Singapore: IEEE, 2015: 137-140.
[7] KUNCHEVA Z, MONTANA G. Community detectionin multiplex networks using locally adaptive randomwalks [C]//IEEE/ACM International Conferenceon Advances in Social Networks Analysis and Mining.Pairs, France: ACM, 2015: 1308-1315.
[8] YANG B, CHEUNG W K, LIU J M. Community miningfrom signed social networks [J]. IEEE Transactionon Knowledge and Data Engineering, 2007, 19(10):1333-1348.
[9] JIN D, YANG B, LIU J, et al. Ant colony optimizationbased on random walk for community detectionin complex networks [J]. Journal of Software, 2012,23(3): 451-464 (in Chinese).
[10] ZHOU X, LIU Y H, ZHANG J D, et al. An ant colonybased algorithm for overlapping community detectionin complex networks [J]. Physica A: Statistical Mechanicsand its Applications, 2015, 427: 289-301.
[11] NEWMAN M E J, GIRVAN M. Finding and evaluatingcommunity structure in networks [J]. PhysicalReview E, 2004, 69(2): 026113.
[12] ZACHARY W W. An information flow model for conflictand fission in small groups [J]. Journal of AnthropologicalResearch, 1977, 33(4): 452-473.
[13] LUSSEAU D. The emergent properties of a dolphinsocial network [J]. Proceedings of the Royal Societyof London. Series B: Biological Sciences, 2003,270(Sup2): 186-188.
[14] NEWMAN M E J. Modularity and community structurein networks [J]. Proceedings of the NationalAcademy of Sciences of the United States of America,2006, 103(23): 8577-8582.
