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

北京大学学报（自然科学版）

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

黄健斌¹,钟翔²,孙鹤立³,茆婉婷¹

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 Jianbin¹, ZHONG Xiang², SUN Heli³, MAO Wanting¹

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

摘要/Abstract

摘要： 提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(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

中图分类号:

TP311

黄健斌,钟翔,孙鹤立,茆婉婷. 基于相似性模块度最大约束标记传播的网络社团发现算法[J]. 北京大学学报（自然科学版）.

HUANG Jianbin,ZHONG Xiang,SUN Heli,MAO Wanting. A Network Community Detection Algorithm via Constrained Label Propagation with Maximization of Similarity-Based Modularity[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2013/V49/I3/389

[1]	沈劲鹏, 王新安. 适用于床垫式生理信号监测系统的信号处理方法[J]. 北京大学学报自然科学版, 2018, 54(5): 921-926.
[2]	孙基男, 潘克峰, 陈雪峰, 张君福. 基于符号执行的注入类安全漏洞的分析技术[J]. 北京大学学报自然科学版, 2018, 54(1): 1-13.
[3]	王星光, 张瑞洁, 张毅. 基于地理关联度和证据理论的地名消歧方法研究[J]. 北京大学学报自然科学版, 2017, 53(2): 344-352.
[4]	高勇, 姜丹, 刘磊, 林星, 邬伦. 一种地理信息检索的定性模型[J]. 北京大学学报（自然科学版）, 2016, 52(2): 265-273.
[5]	刘磊,高勇,林星,邬伦. 定性地理信息检索方法及其实现[J]. 北京大学学报（自然科学版）, 2013, 49(6): 1017-1024.
[6]	仲兆满,刘宗田,李存华. 事件本体模型及事件类排序[J]. 北京大学学报（自然科学版）, 2013, 49(2): 234-240.
[7]	王铁磊,韦韬,邹维. 基于roBDD的细颗粒度动态污点分析[J]. 北京大学学报（自然科学版）, 2011, 47(6): 1003-1008.
[8]	刘钊,黄罡,张颖,梅宏. 一种自动化的资源按需管理方法[J]. 北京大学学报（自然科学版）, 2009, 45(5): 783-790.
[9]	黄雨胡文蕙张世琨. 基于扩展库所网的工作流过程规约和模式描述[J]. 北京大学学报（自然科学版）, 2009, 45(4): 572-578.
[10]	付艳,杨冬青,唐世渭,伍伟,王腾蛟,高军. 基于实体识别的在线主题检测方法[J]. 北京大学学报（自然科学版）, 2009, 45(2): 227-232.
[11]	屈红刚,潘懋,明镜,吴自兴,孙志东. 基于交叉折剖面的高精度三维地质模型快速构建方法研究[J]. 北京大学学报（自然科学版）, 2008, 44(6): 915-920.
[12]	陶有东,童云海,谭少华,唐世渭,杨冬青. 一种实现OLAP数据隐私保护的方法[J]. 北京大学学报（自然科学版）, 2008, 44(5): 705-710.
[13]	屈红刚,潘懋,吕晓俭,刘学清,张永波,于春林. 城市三维地质信息管理与服务系统设计与开发[J]. 北京大学学报（自然科学版）, 2008, 44(5): 781-786.
[14]	韦韬,毛剑,邹维. 反编译中的复合条件分支识别算法[J]. 北京大学学报（自然科学版）, 2008, 44(1): 37-43.
[15]	冯耀东,黄罡,梅宏. 一种自适应软件体系结构建模及其实施方法[J]. 北京大学学报（自然科学版）, 2008, 44(1): 67-76.