基于结构紧密性的重叠社区发现算法

doi:10.3969/j.issn.0372-2112.2019.01.019

电子学报 ›› 2019, Vol. 47 ›› Issue (1): 145-152.DOI: 10.3969/j.issn.0372-2112.2019.01.019

所属专题：优秀论文(2022)

基于结构紧密性的重叠社区发现算法

潘剑飞^1,2, 董一鸿¹, 陈华辉¹, 钱江波¹, 戴明洋²

1. 宁波大学信息科学与工程学院, 浙江宁波 315211;
2. 北京百度在线科技有限公司, 北京 100084

收稿日期:2018-01-29 修回日期:2018-08-01 出版日期:2019-01-25
- 通讯作者:
- 董一鸿
- 作者简介:
- 潘剑飞 男,1991年出生,宁波大学信息科学与工程学院硕士生,百度算法工程师,主要研究方向为大数据、数据挖掘.
- 基金资助:
- 国家自然科学基金 (No.61572266，No.61472194）; 浙江省自然科学基金 (No.LY16F020003）; 宁波市自然科学基金 (No.2017A610114）

The Overlapping Community Discovery Algorithm Based on Compact Structure

PAN Jian-fei^1,2, DONG Yi-hong¹, CHEN Hua-hui¹, QIAN Jiang-bo¹, DAI Ming-yang²

1. Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo, Zhejiang 315211, China;
2. Baidu Online Technology Co. Ltd., Beijing 100084, China

Received:2018-01-29 Revised:2018-08-01 Online:2019-01-25 Published:2019-01-25
- Supported by:
- National Natural Science Foundation of China (No.61572266, No.61472194); National Natural Science Foundation of Zhejiang Province, China (No.LY16F020003); Ningbo Natural Science Fund (No.2017A610114)

摘要/Abstract

摘要： 随着网络结构的不断扩大和日益复杂，传统的重叠社区发现算法已经不能有效地处理大规模网络数据，发现合理的社区结构.本文提出了顶点引力的概念，引入顶点凝聚度和社区凝聚度作为满足社区的外部结构稀疏性和社区内部结构紧密性的判定指标，构造了基于结构紧密性的重叠社区发现算法OCSC.该算法经过预处理，核心子图划分以及核心社区的扩展三个步骤，能有效地发现重叠社区，通过对人工合成网络和真实网络结构的社区发现实验，运用NMI和F1Score等指标验证OCSC算法的合理性和优越性.

关键词: 社区发现, 重叠社区, 核心社区, 大规模网络结构, spark

Abstract: With the continuous expansion and complexity of network structure,the traditional overlapping community detection algorithm can not effectively discover reasonable community structure in large-scale network structure.Based on the concept of vertex gravity proposed in this paper,we introduce vertex cohesion and community cohesion as indexes for community structure-close internal structure and sparse external structure,and then put forward overlapping community structure algorithm OCSC.The steps of OCSC algorithm include pre-processing,core sub-mapping and core community expansion.Finally,NMI and F1Score confirm the rationality and superiority of OCSC algorithm by experimentation on synthetic and real network structures.

Key words: community discovery, overlapping community, core community, large-scale network structure, spark

中图分类号:

TP311

潘剑飞, 董一鸿, 陈华辉, 等. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.

PAN Jian-fei, DONG Yi-hong, CHEN Hua-hui, et al. The Overlapping Community Discovery Algorithm Based on Compact Structure[J]. Acta Electronica Sinica, 2019, 47(1): 145-152.

参考文献

[1] Wang YZ,Jin XL,Cheng XQ.Network big data:Present and future[J].Chinese Journal of Computers,2013,36(6):1125-1138.
[2] Newman MEJ,Girvan M.Finding and evaluating community structure in networks[J].Physcial Review E,2004,69(2):026111.
[3] Xie JR,Szymanski BK,Liu XM.SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[A].Proc of the 2011 IEEE 11th Int'l Conf on Data Mining Workshops[C].Washington:IEEE,2011.344-349.
[4] 王诗懿,董一鸿,李志超.大规模复杂网络下重叠社区的识别[J].电子学报,2015,43(8):1575-1582. Wang SY,Dong YH,Li ZC.Identification of overlapping communities on large scale complex networks[J].Acta Electronica Sinica,2015,43(8):1575-1582.(in Chinese)
[5] Adamcsek B,Palla G,Farkas IJ,Dere-nyi I,Vicsek T.C nder:locating cliques and overlapping modules in biological networks[J].Bioinformatics,2006,22:1021-1023.
[6] Prat-P,Rez A,Dominguez-Sal D,et al.Putthree and three together:triangle-driven community detection[J].ACM Transactions on Knowledge Discovery from Data,2016,10(3):22.
[7] Zhang XW,You HB,Zhu W,Qiao SJ,Li JW,Gutierrez LA,Zhang Z,Fan XN.Overlapping community identification approach in online social networks[J].Physica A,2015,421:233-428.
[8] Gregory S.An algorithm to find overlapping community structure in networks[A].Proc of the European Conf on Principles of Data Mining and Knowledge Discovery[C].Berlin,Heidelberg:Springer-Verlag,2007.91-102.
[9] Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.
[10] Gopalan PK,Blei DM.Effcient discovery of overlapping communities in massive networks[J].Proc Natl Acad Sci,2013,110(36):14534-14539.
[11] Li M,Liu J.A link clustering based memetic algorithm for overlapping community detection[J].Physica A Statistical Mechanics & Its Applications,2018:410-423.
[12] Lancichinetti A,Fortunato S.Limits of modularity maximization in community detection[J].Physical Review E,2011,84:066122.
[13] Altaf-Ul-Amin M,Shinbo Y,Mihara K,Kurokawa K,Kanaya S.Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J].BMC Bioinformatics,2006,7:207.
[14] J Whang,D Gleich,I Dhillon.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering,2015,28(5):1272-1284.
[15] Cai G Y.Study onlabel propagation based community detection algorithm for social semantic network[J].Computer Science,2013,40(2):53-57.
[16] Yang J,Leskovec J.Overlapping community detection at scale:a nonnegative matrix factorization approach[A].ACM International Conference on Web Search and Data Mining[C].ACM,2013.587-596.

基于结构紧密性的重叠社区发现算法

The Overlapping Community Discovery Algorithm Based on Compact Structure

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[2]	廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087.
[3]	陈洁, 李锐, 赵姝, 张燕平. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.
[4]	晋云霞, 杨贺昆, 冯朝胜, 刘帅南, 李航, 邹莉萍, 万国根. 一种支持解密外包的KP-ABE方案[J]. 电子学报, 2020, 48(3): 561-567.
[5]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[6]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[7]	马慧芳, 谢蒙, 何廷年, 蔺想红. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.
[8]	卞琛, 于炯, 英昌甜, 修位蓉. 并行计算框架Spark的自适应缓存管理策略[J]. 电子学报, 2017, 45(2): 278-284.
[9]	吴奇, 陈福才, 黄瑞阳, 常振超. 基于语义路径的异质网络社区发现方法[J]. 电子学报, 2016, 44(6): 1465-1471.
[10]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[11]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[12]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[13]	张桂杰, 张健沛, 杨静, 辛宇. 基于链接相似性聚类的重叠社区识别[J]. 电子学报, 2015, 43(7): 1329-1335.
[14]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[15]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.