北京大学学报(自然科学版)

基于相似性模块度最大约束标记传播的网络社团发现算法

黄健斌1,钟翔2,孙鹤立3,茆婉婷1   

  1. 1. 西安电子科技大学软件学院, 西安710071; 2. 西安电子科技大学计算机学院, 西安710071; 3. 西安交通大学计算机科学与技术系, 西安 710049;
  • 收稿日期:2012-03-01 出版日期:2013-05-20 发布日期:2013-05-20

A Network Community Detection Algorithm via Constrained Label Propagation with Maximization of Similarity-Based Modularity

HUANG Jianbin1, ZHONG Xiang2, SUN Heli3, MAO Wanting1   

  1. 1. School of Software, Xidian University, Xi’an 710071; 2. School of Computer Science, Xidian University, Xi’an 710071; 3. Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049;
  • Received:2012-03-01 Online:2013-05-20 Published:2013-05-20

摘要: 提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算, 通过最大约束标记传播模型更新节点标记, 使社团的划分结果更加符合社团内部结构相对紧密、 社团之间结构相对稀疏的特点, 提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果, 判定标记更新过程趋于稳定, 从而在稳定时停止更新, 降低了运行时间。MLPA避免了传统的邻接矩阵计算方法, 适合大规模网络的社团发现。

关键词: 社团发现, 标记传播, 结构相似度, 模块度

Abstract: A fast network community detection algorithm, MLPA, was proposed based on constrained label propagation with maximization of similarity-based modularity. The update process was completed via constrained maximization of similarity-based modularity model. The application of model and structural-similarity makes the accuracy high and the result fits in with character of community, which is densely inter-connected and sparsely connected to other parts of the network. Combined with experimental result that most of the vertices can be assigned to the proper community only within five iterations, the algorithm tries to stop the update process when labels reaches stable. Thus it can reduce the running time greatly. MLPA is efficient for detecting communities in large-scale networks without traditional adjacency matrix calculation.

Key words: community detection, label propagation, structural-similarity, modularity

中图分类号: