Journal of Shanghai Jiao Tong University (Science) ›› 2019, Vol. 24 ›› Issue (1): 71-77.doi: 10.1007/s12204-019-2041-2

• • 上一篇    下一篇

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

MA Jian *(马健), FAN Jianping (樊建平), LIU Feng (刘峰), LI Honghui (李红辉)   

  1. (School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)
  • 出版日期:2019-02-28 发布日期:2019-01-28
  • 通讯作者: MA Jian *(马健) E-mail:13112083@bjtu.edu.cn

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

MA Jian *(马健), FAN Jianping (樊建平), LIU Feng (刘峰), LI Honghui (李红辉)   

  1. (School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)
  • Online:2019-02-28 Published:2019-01-28
  • Contact: MA Jian *(马健) E-mail:13112083@bjtu.edu.cn

摘要: 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

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

中图分类号: