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

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

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