Journal of Frontiers of Computer Science and Technology ›› 2014, Vol. 8 ›› Issue (3): 296-304.DOI: 10.3778/j.issn.1673-9418.1306046

Previous Articles     Next Articles

Community Detection on Bipartite Networks Based on Ant Colony Optimization

XU Yongcheng1+, CHEN Ling1,2   

  1. 1. Department of Computer Science, College of Information Engineering, Yangzhou University, Yangzhou, Jiangsu 225009, China
    2. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
  • Online:2014-03-01 Published:2014-03-05

基于蚁群优化的二分网络社区挖掘

徐永成1+,陈  崚1,2   

  1. 1. 扬州大学 信息工程学院 计算机系,江苏 扬州 225009
    2. 南京大学 计算机软件新技术国家重点实验室,南京 210093

Abstract: Detecting communities from networks receives much attention in recent decades, especially from bipartite networks. Detecting communities from bipartite network is very important in the research on the theory and applications of complex network analysis. This paper proposes an algorithm based on ant colony optimization for detecting community structures from bipartite networks. The algorithm firstly transforms the problem of community detection into the problem of ant colony optimization, then constructs a graph model for ants foraging. Meanwhile, this paper redefines heuristic information according the degree of vertexes. Each ant chooses its path according to the pheromone and heuristic information on each path to construct a solution. The quality of solution obtained by each ant is measured by its bipartite modularity. The experimental results show that the proposed algorithm can not only accurately identify the number of communities of a network, but also obtain higher quality of community detection.

Key words: detecting communities, bipartite network, ant colony optimization, bipartite modularity

摘要: 近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数,而且可以获得高质量的社区划分。

关键词: 社区挖掘, 二分网络, 蚁群优化算法, 二分模块度