基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性

李泓波, 张健沛, 杨静, 白劲波, 初妍

电子学报 ›› 2014, Vol. 42 ›› Issue (1) : 62-69.

PDF(5911 KB)
PDF(5911 KB)
电子学报 ›› 2014, Vol. 42 ›› Issue (1) : 62-69. DOI: 10.3969/j.issn.0372-2112.2014.01.010
学术论文

基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性

  • 李泓波1, 张健沛2, 杨静2, 白劲波3,4, 初妍2
作者信息 +

Identification of Overlapping Communities and Structural Holes Between Communities Based on Topological Potential—Also on the Fragility of Network from the Perspective of the Structural Hole Theory

  • LI Hong-bo1, ZHANG Jian-pei2, YANG Jing2, BAI Jin-bo3,4, CHU Yan2
Author information +
文章历史 +

摘要

社会网络和复杂网络上的社区识别已经成为当前研究的热点和前沿课题.针对目前社区识别方法不能兼具较低时间复杂度、无须专家知识或先验知识和允许存在重叠节点的不足,提出了基于拓扑势理论的重叠社区识别方法.通过提出的重叠节点社区归属不确定性测度,该方法同时实现了社区间结构洞的识别.实验验证了该方法的有效性.另外,文章在理论证明的基础上提出了影响因子优化算法;论证了结构洞理论视角下网络的脆弱性.

Abstract

Community identification has been a hot spot and a cutting-edge topic among researchers.Since none of the present community identification methods simultaneously meets the requirements,such as lower time complexity,independence of expertise or experiences,allowance for overlapping nodes and so on,an overlapping community identification method is proposed based on topological potential theory.This method can also identify the structural holes in communities at the same time by the presented uncertainty measure of the community identity of the overlapping nodes,and its effectiveness is verified by experiments.In addition,an influence factor optimization algorithm is proposed and network fragility is discussed and prooved from the perspective of structural hole theory.

关键词

网络 / 重叠社区 / 结构洞 / 识别 / 拓扑势 / 影响因子 / 不确定性测度 / 脆弱性

Key words

network / overlapping community / structural holes / identification / topological potential / influence factor / uncertainty measure / fragility

引用本文

导出引用
李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, 2014, 42(1): 62-69. https://doi.org/10.3969/j.issn.0372-2112.2014.01.010
LI Hong-bo, ZHANG Jian-pei, YANG Jing, BAI Jin-bo, CHU Yan. Identification of Overlapping Communities and Structural Holes Between Communities Based on Topological Potential—Also on the Fragility of Network from the Perspective of the Structural Hole Theory[J]. Acta Electronica Sinica, 2014, 42(1): 62-69. https://doi.org/10.3969/j.issn.0372-2112.2014.01.010
中图分类号: TP391   

参考文献

[1] 潘磊,金杰,王崇骏,等.社会网络中基于局部信息的边社区挖掘[J].电子学报,2012,40(11):2255-2262. Pan L,Jin J,Wang C J,et al.Detecting link communities based on local information in social networks[J].Acta Electronica Sinica,2012,40(11):2255-2262.(in Chinese)
[2] Gao J,Liang F,et al.On community outliers and their efficient detection in information networks [A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining [C].Washington,DC,USA:ACM,2010.813-822.
[3] Xu K Q,Li J X,Liao SS.Sentiment community detection in social networks [A].Proceedings of iConference [C].Seattle,WA,USA:ACM,2011.804-805.
[4] 张伟哲,王佰玲,等.基于异质网络的意见领袖社区发现[J].电子学报,2012,40(10):1927-1932. Zhang W Z,Wang B L,et al.Public opinion leader community mining based on the heterogeneous network[J].Acta Electronica Sinica,2012,40(10):1927-1932.(in Chinese)
[5] Kamath K Y,Caverlee J.Identifying hotspots on the real-time web [A].Proceedings of the 19th ACM International Conference on Information and Knowledge Management [C].Toronto,Ontario,Canada:ACM,2010.1837-1840.
[6] 刘挺.社会计算[J].中国计算机学会通讯,2011,7(12):6-7. Liu T.Social computing[J].Communication of the CCF,2011,7(12):6-7.(in Chinese)
[7] 毛文吉,曾大军,柯冠岩,等.社会计算的研究现状与未来[J].中国计算机学会通讯,2011,7(12):8-11. Mao W J,Zeng D J,Ke G Y,et al.The current statusand future of social computing research[J].Communication of the CCF,2011,7(12):8-11.(in Chinese)
[8] Girvan M,Newman M E J.Community structure in social and biological networks [A].Proceedings of the National Academy of Sciences of the United States of America [C].USA:PMC,2002.7821-7826.
[9] Fortunato S,Latora V,Marchiori M.Method to find community structures based on information centrality[J].Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2004,70(5):056104.
[10] Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2004,69(6):66-133.
[11] Radicchi F,Castellano C,Cecconi F,et al.Defining and identifying communities in networks [A].Proceedings of the National Academy of Sciences of the United States of America [C].USA:PMC,2004.2658-2663.
[12] Newman M E J,et al.Finding and evaluating community structure in networks[J].Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2004,69(2):026113.
[13] 淦文燕,赫南,李德毅,等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8):2241-2254. Gan W Y,He N,Li DY,et al.Community discovery method in networks based on topological potential[J].Journal of Software,2009,20(8):2241-2254.(in Chinese)
[14] Han Y N,Li D Y,Wang T.Identifying different community members in complex networks based on topology potential[J].Frontiers of Computer Science,2011,5(1):87-99.
[15] Burt R S.Structural holes:the social structure of competition Cambridge[M].MA:Harvard University Press,1992.
[16] 汪小帆,等.复杂网络理论及其应用[M].北京:清华大学出版社,2006. Wang X F,et al.Theory and application of complex network[M].Beijing:Tsinghua University Press,2006.(in Chinese)
[17] Albert R,Jeong H,Barabasi A L.Error and attack tolerance of complex networks .Nature,2000,406:378-382.
[18] Zhang J P,Li H B,Yang J,Bai J B,et al.Community discovery method with uncertainty measure of overlapping nodes based on topological potential[J].Journal of Harbin Institute of Technology (New Series),2012,19(2):16-22.
[19] 张健沛,李泓波,杨静,等.基于归属不确定性的变规模网络社区识别[J].电子学报,2012,40(12):2512-2518. Zhang J P,Li H B,et al.Variable scale network overlapping community identification based on identity uncertainty[J].Acta Electronica Sinica,2012,40(12):2512-2518.(in Chinese)
[20] Han Y N,Li D Y.A novel measurement of structure properties in complex networks .Lecture Notes of the Institute for Computer Sciences,Social Information and Telecommunications Engineering,2009,(5):1292-1297.
[21] Newman M E J.Network Data [OL].http://www-personal.umich.edu/~mejn/netdata/,2013-04-19/2013-07-20.
[22] Lusseau D,Schneider K,Boisseau O J,Haase P,Slooten E,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology Sociobiology,2003,54(4):396-405.

基金

国家自然科学基金 (No.61073041,No.61073043); 黑龙江省自然科学基金 (No.F200901,No.F200917); 黑龙江省教育厅科学技术研究基金 (No.12531529); 哈尔滨市优秀学科带头人基金 (No.2010RFXXG002,No.2011RFXXG015); 高等学校博士学科点专项科研基金 (No.20112304110011)
PDF(5911 KB)

2699

Accesses

0

Citation

Detail

段落导航
相关文章

/