复杂网络的重叠社区及社区间的结构洞识别

doi:10.3969/j.issn.0372-2112.2016.11.006

电子学报 ›› 2016, Vol. 44 ›› Issue (11): 2600-2606.DOI: 10.3969/j.issn.0372-2112.2016.11.006

复杂网络的重叠社区及社区间的结构洞识别

刘世超, 朱福喜, 冯曦

武汉大学计算机学院, 湖北武汉 430072

收稿日期:2015-05-12 修回日期:2015-11-09 出版日期:2016-11-25
- 通讯作者:
- 朱福喜
- 作者简介:
- 刘世超,男,1989年2月出生,河南周口人.武汉大学计算机学院博士生,研究方向为社会网络分析和Web数据挖掘.E-mail:nani@whu.edu.cn;冯曦,女,1991年11月出生,陕西西安人.武汉大学计算机学院硕士生,研究方向为社会网络分析和数据挖掘.E-mail:fengxiwhu@outlook.com
- 基金资助:
- 国家自然科学基金 (No.61272277）; 中央高校基本科研业务费专项基金 (No.274742）

Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks

LIU Shi-chao, ZHU Fu-xi, FENG Xi

Computer School of Wuhan University, Wuhan, Hubei 430072, China

Received:2015-05-12 Revised:2015-11-09 Online:2016-11-25 Published:2016-11-25

摘要/Abstract

摘要：

大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点.本文提出一种基于多标签传播方式MLPS（Multiple Label Propagation Strategy）的重叠社区识别算法，该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签，然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程，迭代停止后将具有相同标签的结点划分为同一社区.通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度，且具有接近线性的时间复杂度.另外，在对MLPS算法输出的重叠结构进行分析的基础上，本文提出社区间的结构洞识别算法SHCDA（Structural Holes Between Communities Detection Algorithm），该算法通过分析重叠结构和重叠结点的位置特征，计算重叠结点作为结构洞的得分，最后输出top-k结构洞.本文在不同特性的数据集上进行实验，结果证明了SHCDA算法具有最好的准确度.

关键词: 复杂网络, 重叠社区, 多标签传播, 结构洞识别

Abstract:

Many researchers focus on how to detect overlapping communities effectively and accurately when coping with large-scale networks in recent years.This paper proposes a novel overlapping community detection algorithm based on a multiple label propagation strategy,called MLPS algorithm.Firstly,MLPS selects a set of nodes as initial seeds by using Influence Maximization Model,each of which is assigned a unique label;Inspired by strategy based on similarity and influence diffusion,MLPS incorporates with these two strategies to guide the process of label propagation;Finally,nodes with the same tag are divided into one community after propagation.Experimental results on synthetic datasets and real networks illustrate that MLPS has both high accuracy and modularity at the same time.In addition,another algorithm named Structural Holes between Communities Detection Algorithm (SHCDA) is presented on the basis of the output of MLPS.SHCDA computes the scores of overlapping nodes who serve as structural holes by analyzing the overlapping structure and position feature of overlapping nodes,and then selects top-k structural holes as the output.Experimental results on different datasets show that SHCDA gets the best accuracy.

Key words: complex networks, overlapping community, multiple label propagation, structural holes detection

中图分类号:

TP391

刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.

LIU Shi-chao, ZHU Fu-xi, FENG Xi. Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks[J]. Acta Electronica Sinica, 2016, 44(11): 2600-2606.

参考文献

[1] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[2] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[3] Shi C,Cai Y,Fu D,et al.A link clustering based overlapping community detection algorithm[J].Data & Knowledge Engineering,2013,87:394-404.
[4] Whang J J,Gleich D F,Dhillon I S.Overlapping community detection using seed set expansion[A].CIKM 2013[C].San Francisco,CA,USA,ACM,2013.2099-2108.
[5] Burt R S.Structural Holes:The Social Structure of Competition[M].MA,Harvard University Press,1992.
[6] Kleinberg J,Suri S,Tardos é,et al.Strategic network formation with structural holes[A].Proceedings of the 9th ACM Conference on Electronic Commerce[C].Chicago,Illinois,USA,ACM,2008.284-293.
[7] Buskens V,Van de Rijt A.Dynamics of networks if everyone strives for structural holes[J].American Journal of Sociology,2008,114(2):371-407.
[8] 李泓波,等.基于拓扑势的重叠社区及社区间结构洞识别.电子学报,2014,42(1):62-69. Li H B,et al.Identification of overlapping communities and structural holes between communities based on topological potential[J].Acta Electronica Sinica,2014,42(1):62-69.(in Chinese)
[9] Lou T,Tang J.Mining structural hole spanners through information diffusion in social networks[A].WWW 2013[C].Rio de Janeiro,Brazil,International World Wide Web Conferences Steering Committee,2013.825-836.
[10] Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[11] Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):026129.
[12] Liu X,Murata T.Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A:Statistical Mechanics and its Applications,2010,389(7):1493-1500.
[13] Xie J,Szymanski B K.Community detection using a neighborhood strength driven label propagation algorithm[A].NSW 2011[C].New York,USA,IEEE,2011.188-195.
[14] Gregory S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):103018.
[15] Wu Z H,Lin Y F,Gregory S,et al.Balanced multi-label propagation for overlapping community detection in social networks[J].Journal of Computer Science and Technology,2012,27(3):468-479.
[16] Xie J,Szymanski B K,Liu X.Slpa:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[A].ICDMW 2011[C].Vancouver,BC,Canada,IEEE,2011.344-349.
[17] Dai Q,Guo M,Liu Y,et al.MLPA:Detecting overlapping communities by multi-label propagation approach[A].CEC 2013[C].Cancun,Mexico,IEEE,2013.681-688.
[18] Aral S,Walker D.Identifying influential and susceptible members of social networks[J].Science,2012,337(6092):337-341.
[19] Li Q,et al.Identifying influential spreaders by weighted LeaderRank[J].Physica A:Statistical Mechanics and its Applications,2014,404:47-55.
[20] Wang Y,Feng X.A Potential-Based Node Selection Strategy for Influence Maximization in a Social Network[M].Advanced Data Mining and Applications.Springer Berlin Heidelberg,2009.350-361.
[21] Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):046110.
[22] Nicosia V,Mangioni G,Carchiolo V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,2009(03):P03024.
[23] Zachary W.An information flow model for conflict and fission in small groups1[J].Journal of anthropological research,1977,33(4):452-473.
[24] Lusseau D,Schneider K,Boisseau O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[25] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[26] Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical review E,2006,74(3):036104.
[27] Newman M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.
[28] Page L,Brin S,Motwani R,et al.The PageRank citation ranking:Bringing order to the web[R].Stanford InfoLab,1999-66.

复杂网络的重叠社区及社区间的结构洞识别

Identifying Overlapping Communities and Structural Holes Between Communities in Complex Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[2]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[3]	胡钢, 高浩, 徐翔, 许丽鹏. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48(12): 2402-2408.
[4]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[5]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[6]	王尔申, 王玉伟, 庞涛, 曲萍萍, 姜毅. 基于边攻击成本的复杂网络鲁棒性研究[J]. 电子学报, 2018, 46(5): 1166-1172.
[7]	何鹏, 王鹏, 李兵, 胡思文. 基于多粒度软件网络模型的软件系统演化分析[J]. 电子学报, 2018, 46(2): 257-267.
[8]	马慧芳, 谢蒙, 何廷年, 蔺想红. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.
[9]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[10]	国琳, 左万利. 基于兴趣图谱的用户兴趣分布分析及专家发现[J]. 电子学报, 2015, 43(8): 1561-1567.
[11]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[12]	张桂杰, 张健沛, 杨静, 辛宇. 基于链接相似性聚类的重叠社区识别[J]. 电子学报, 2015, 43(7): 1329-1335.
[13]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[14]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.
[15]	李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, 2014, 42(1): 62-69.