A Community Detection Algorithm Based on Markov Random Walks Ants in Complex Network

doi:10.1007/s12204-019-2041-2

Abstract

Abstract: 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.

Key words: complex network| community detection| Markov chain| random walk

摘要： 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.

关键词: complex network| community detection| Markov chain| random walk

CLC Number:

TP 391

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 Jiao Tong University (Science), 2019, 24(1): 71-77.

References 14

[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.

[1]	ZHAO Yao, YU Wenqiang, LI Dongdong, GAO Shaowei, WANG Yan. Influence of Incentive-Based Demand-Side Response on Distribution Network Reliability Considering Prosumers [J]. Journal of Shanghai Jiao Tong University, 2026, 60(1): 74-86.
[2]	NI Yu, XU Yazhou, LUO Yizhe, YU Mengxin, JIN Zhao, FENG Shuo, SHI Yucheng, XU Mingliang. System Effectiveness Evaluation Method for Multi-Spacecraft Operational Systems Based on Complex Network Theory [J]. Air & Space Defense, 2026, 9(1): 132-144.
[3]	MA Yonglin, LI Hao, XIONG Wei, LI Lingzhi, TANG Jingmian. Uncertainty Quantification Approach for Aerial Target Recognition Based on Hierarchical Bayesian Models [J]. Air & Space Defense, 2026, 9(1): 20-27.
[4]	MIAO Ji, DUAN Liping, LIU Jiming, LIN Siwei, ZHAO Jincheng. Structural Simulation Model Updating Based on Improved MCMC Algorithm and Surrogate Model [J]. Journal of Shanghai Jiao Tong University, 2025, 59(8): 1114-1122.
[5]	ZHANG Chenwei, WANG Ying, LI Yaping, ZHANG Kaifeng. Optimization Model for Safeguarding Vulnerable Components in Integrated Energy Systems Based on Weighted Betweenness [J]. Journal of Shanghai Jiao Tong University, 2025, 59(7): 923-937.
[6]	LIANG Haolan, LIU Dongqi, ZENG Xiangjun, ZHANG Qiong, ZHANG Tao, WANG Rui. Dynamic Modeling and Optimal Defense Strategy Against DdoS Attacks on Power Advanced Metering Infrastructure [J]. Journal of Shanghai Jiao Tong University, 2025, 59(11): 1660-1674.
[7]	LU Pengli^1∗ (卢鹏丽), CHEN Wei¹ (陈玮), GUO Yuhong²(郭育红), CHEN Yahong³(陈娅红). Symmetric Nonnegative Matrix Factorization for Vertex Centrality in Complex Networks [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(6): 1037-1049.
[8]	FAN Hong, HE Jie, TIAN Shuxin. Robust Evaluation Method of Integrated Energy System Based on Variable Step Simulation and Improved Entropy Weight Method [J]. Journal of Shanghai Jiao Tong University, 2024, 58(1): 59-68.
[9]	SU Hongjia, LUO Yucheng, LIU Fei. Review of Equipment Effectiveness Evaluation and Supporting Technologies [J]. Air & Space Defense, 2023, 6(3): 29-38.
[10]	YUAN Ming, LIU Qun, SUN Haichao, TAN Hongsheng. A Heterogeneous Network Representation Method Based on Variational Inference and Meta-Path Decomposition [J]. Journal of Shanghai Jiao Tong University, 2021, 55(5): 586-597.
[11]	YAN Hua (闫华), GAO Li (高黎), QI Lei (漆磊), WAN Ping (万平). Simplified Markov Model for Reliability Analysis of Phased-Mission System Using States Merging Method [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(3): 418-.
[12]	CAO Qian,LI Jun,QU Dawei. Construction of Typical Driving Cycle for Passenger Cars in the City of Dalian [J]. Journal of Shanghai Jiao Tong University, 2018, 52(11): 1537-1542.
[13]	XU Yong1 (徐勇), TANG Qian2 (唐倩), HOU Linzao2 (候林早), LI Mian2* (李冕). Decision Model for Market of Performing Arts with Factorization Machine [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(1): 74-84.
[14]	JIA Xiaoli,JIANG Xiaobo,JIANG Sanxin，LIU Peilin. A Reconstruction Algorithm for Speech Compressive Sensing Using Structural Features [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1111-1116.
[15]	ZHANG Honga* (张红), HU Changzhenb (胡昌振), WANG Xiaojuna (王小军). Brittleness Analysis and Important Nodes Discovery in Large Time-Evolving Complex Networks [J]. Journal of shanghai Jiaotong University (Science), 2017, 22(1): 50-054.