大规模复杂网络下重叠社区的识别

doi:10.3969/j.issn.0372-2112.2015.08.016

电子学报 ›› 2015, Vol. 43 ›› Issue (8): 1575-1582.DOI: 10.3969/j.issn.0372-2112.2015.08.016

大规模复杂网络下重叠社区的识别

王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波

宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2014-09-25 修回日期:2015-02-25 出版日期:2015-08-25
- 通讯作者:
- 董一鸿
- 作者简介:
- 王诗懿 女,1988年生于河南周口.现为宁波大学信息科学与工程学院硕士研究生.主要研究方向为大数据、数据挖掘. E-mail:zwb_wsy@126.com
- 基金资助:
- 国家自然科学基金 (No.61472194); 浙江省自然科学基金 (No.LY13F020040); 宁波市自然科学基金 (No.2013A610063,No.2014A610023)

The Identification of Overlapping Communities in Large-Scale Complex Networks

WANG Shi-yi, DONG Yi-hong, LI Zhi-chao, CHEN Hua-hui, QIAN Jiang-bo

Department of Information Science and Engineering, Ningbo University, Ningbo, Zhejiang 315211, China

Received:2014-09-25 Revised:2015-02-25 Online:2015-08-25 Published:2015-02-09
- Supported by:
- National Natural Science Foundation of China (No.61472194); National Natural Science Foundation of Zhejiang Province, China (No.LY13F020040); Ningbo Natural Science Fund (No.2013A610063, No.2014A610023)

摘要/Abstract

摘要：

随着网络规模的不断扩大,经典的复杂网络重叠社识别算法已不能高效处理现有的大规模网络图数据.本文在GraphLab并行计算模型上提出了基于重要节点扩展的重叠社区识别算法DOCVN (Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab).算法选取网络中PageRank值大的节点作为重要节点,计算其他节点归属于重要节点的节点归属度,并以重要节点为中心形成核心社区及扩展社区,最后根据重要节点间的连接紧密度合并核心社区及扩展社区,并计算出每个节点在所属社区里的节点重要度,实现了大规模网络的重叠社区识别.实验表明该算法与PD (Propinquity Dynamics)等现有并行算法相比更能有效地识别大规模网络的重叠社区结构.

关键词: 大规模复杂网络, GraphLab, 重叠社区识别, 社会网络, 核心社区

Abstract:

With the unceasing expanding of network scale, many classic detection algorithms of overlapping communities cannot work efficiently in large-scale complex network.Detecting the overlapping community algorithm based on vital node expanding in parallel framework GraphLab (DOCVN) is introduced to identify the overlapping communities.In this algorithm, nodes with high PageRank value are regarded as vital nodes, and then the affiliation degree of other nodes to these vital nodes are computed.After that, kernel communities and expanding communities are identified respectively.Finally, the kernel communities and expanding communities are combined into some overlapping communities by judging whether they connect tightly.And the importance weight of each node in its community is also computed.Experimental results show that the algorithm is more effective than the existing parallel algorithms like PD (Propinquity Dynamics) to identify large-scale overlapping communities.

Key words: large-scale complex network, GraphLab, overlapping community identification, social network, kernel community

中图分类号:

TP391

王诗懿, 董一鸿, 李志超, 等. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.

WANG Shi-yi, DONG Yi-hong, LI Zhi-chao, et al. The Identification of Overlapping Communities in Large-Scale Complex Networks[J]. Acta Electronica Sinica, 2015, 43(8): 1575-1582.

参考文献

[1] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69:026113.
[2] Clauset A.Finding local community structure in networks[J].Physical Review E,2005,72:026132.
[3] 王庚.基于标签传播的稳定重叠社区挖掘算法研究[D].山东:山东建筑大学,2013. Wang G.Research to Stable Detecting Overlapping Communities by Label Propagation on Social Networks[D].Shandong:Shandong Jianzhu University,2013.(in Chinese)
[4] Lancichinetti A,Fortunato S,Kertesz J.Detecting the overlaping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11:033015.
[5] Zhang Y,Wang J,Wang Y,et al.Parallel community detection on large networks with Propinquity dynamics[A].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Pairs:ACM,2009.997-1006.
[6] 从玉相.基于 MapReduce 的社区挖掘算法[D].上海:上海交通大学,2013. Y X Cong.Community Detection Based on MapReduce[D].Shanghai:Shanghai Jiao Tong University,2013.(in Chinese)
[7] J Shi,W Xue,W Wang,Y Zhang,et al.Scalable community detection in massive social networks using MapReduce[J].IBM,J RES & DEV,2013,57(3):3-14.
[8] A Clauset,Newman M E J,et al.Finding community structure in very large networks[J].Physical Review E,2004,70:066111.
[9] J Riedy,D A Bader,H Meyerhenke.Scalable multi-threaded community detection in social networks[A].Proceedings of IEEE International Conference on Tools with Artificial Intelligence[C].Seoul,Korea:IEEE,2012.1619-1628.
[10] F Niu,B Recht,S J Wright,et al.Hogwild !:A Lock-free Appoach to Parallelizing Stochastic Gradient Descent[DB/OL].Available:http://books.nips.cc/papers/files/nips24/NIPS2011_0485.pdf,2011.
[11] Bryan K,Leise T.The $25 000 000 000 eigenvector:the linear algebra behind Google[J].SIAM Rev,2006,48(3):569-581.
[12] Lancichinetti A,Fortunato S.Limits of modularity maximization in community detection[J].Physical Review E,2011,84:066122.
[13] Jure L.Stanford large network dataset collection[OL].http://snap.stanford.edu/data/index.html,2013.
[14] L Danon,A Diaz-Guilera,J Duch,A Arenas.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,09:p09008.
[15] Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):247-256.

大规模复杂网络下重叠社区的识别

The Identification of Overlapping Communities in Large-Scale Complex Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	高玉君, 梁刚, 蒋方婷, 许春, 杨进, 陈俊任, 王浩. 社会网络谣言检测综述[J]. 电子学报, 2020, 48(7): 1421-1435.
[2]	杨洁, 朱咸军, 周献中, 柳毅. 基于混杂社会网络的个性化Web服务推荐方法[J]. 电子学报, 2020, 48(2): 341-349.
[3]	马慧芳, 刘文, 李志欣, 蔺想红. 融合耦合距离区分度和强类别特征的短文本相似度计算方法[J]. 电子学报, 2019, 47(6): 1331-1336.
[4]	汪林玉, 谷科, 余飞, 尹波, 廖年冬. 基于个人意愿的社会网络团体结构与信息检测方案[J]. 电子学报, 2019, 47(4): 886-895.
[5]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[6]	朱恩强, 吴艳蕾, 许宇光, 牛云云. 基于树核度的社交网络影响最大化问题[J]. 电子学报, 2019, 47(1): 161-168.
[7]	俞春花, 刘学军, 李斌, 章玮. 基于上下文相似度和社会网络的移动服务推荐方法[J]. 电子学报, 2017, 45(6): 1530-1536.
[8]	龚卫华, 兰雪锋, 裴小兵, 杨良怀. 基于k-度匿名的社会网络隐私保护方法[J]. 电子学报, 2016, 44(6): 1437-1444.
[9]	王萌萌, 左万利, 王英. 基于加权非负矩阵分解的链接预测算法[J]. 电子学报, 2016, 44(10): 2391-2397.
[10]	蔡青松, 刘燕, 牛建伟, 孙利民. 一种关注消息时效性的机会社会网络中节点传播能力分析模型[J]. 电子学报, 2015, 43(9): 1705-1713.
[11]	兰丽辉, 鞠时光. 基于向量相似的权重社会网络隐私保护[J]. 电子学报, 2015, 43(8): 1568-1574.
[12]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[13]	张波, 黄震华, 李美子, 向阳. 一种社会网络服务协作决策的竞标组织方法[J]. 电子学报, 2015, 43(4): 625-630.
[14]	牛建伟, 戴彬, 孙利民, 林佳骝, 熊永平. PQBCF:一种基于中间中心度的机会网络P2P查询算法[J]. 电子学报, 2013, 41(9): 1815-1820.
[15]	刘昕, 贾春福, 石乐义, 辛兆君. 基于社会计算的IM恶意代码防御机制[J]. 电子学报, 2013, 41(6): 1130-1139.