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

doi:10.3969/j.issn.0372-2112.2014.01.010

电子学报

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

李泓波¹, 张健沛², 杨静², 白劲波^3,4, 初妍²

1. 肇庆学院计算机学院, 广东肇庆 526061;
2. 哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001;
3. 哈尔滨工程大学经济管理学院, 黑龙江哈尔滨 150001;
4. 黑龙江工程学院计算机科学与技术学院, 黑龙江哈尔滨 150050

收稿日期:2012-01-29 修回日期:2013-08-28 出版日期:2014-01-25 发布日期:2014-01-25
通讯作者: 张健沛
作者简介:李泓波 男，1971年生，黑龙江人，工学博士.主要研究方向为社会网络、复杂网络上的社区发现、挖掘和分析，以及群体智能和数据挖掘等. E-mail:islhb@126.com
基金资助:
国家自然科学基金（No.61073041，No.61073043）；黑龙江省自然科学基金（No.F200901，No.F200917）；黑龙江省教育厅科学技术研究基金（No.12531529）；哈尔滨市优秀学科带头人基金（No.2010RFXXG002，No.2011RFXXG015）；高等学校博士学科点专项科研基金（No.20112304110011）

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-bo¹, ZHANG Jian-pei², YANG Jing², BAI Jin-bo^3,4, CHU Yan²

1. School of Computer Science, Zhaoqing University, Zhaoqing, Guangdong 526061, China;
2. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
3. School of Economics and Management, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
4. School of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin, Heilongjiang 150050, China

Received:2012-01-29 Revised:2013-08-28 Online:2014-01-25 Published:2014-01-25

摘要/Abstract

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

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

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

中图分类号:

TP391

李泓波, 张健沛, 杨静, 白劲波, 初妍. 基于拓扑势的重叠社区及社区间结构洞识别——兼论结构洞理论视角下网络的脆弱性[J]. 电子学报, DOI: 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, DOI: 10.3969/j.issn.0372-2112.2014.01.010.

参考文献

[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.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘倩, 张昊, 宋莹炯, 王刚. 小样本条件下基于矩阵乘法和秩分析的LDPC参数估计方法[J]. 电子学报, 2022, 50(5): 1075-1082.
[2]	张继龙, 李业振, 刘勇, 王栋. 基于透镜成像原理的微波阵列快速成像技术[J]. 电子学报, 2022, 50(5): 1107-1116.
[3]	廖勇, 李玉杰. 一种轻量化低复杂度的FDD大规模MIMO系统CSI反馈方法[J]. 电子学报, 2022, 50(5): 1211-1217.
[4]	宋唐益嘉, 胡鹤飞, 张思睿, 许凌毅, 辛宁. 天基信息港对等共享网络性能仿真[J]. 电子学报, 2022, 50(5): 1266-1269.
[5]	张云, 化青龙, 姜义成, 徐丹. 基于混合型复数域卷积神经网络的三维转动舰船目标识别[J]. 电子学报, 2022, 50(5): 1042-1049.
[6]	冀振燕, 韩梦豪, 宋晓军, 冯其波. 面向激光光条图像修复的循环相似度映射网络[J]. 电子学报, 2022, 50(5): 1234-1242.
[7]	佘维, 霍丽娟, 刘炜, 张志鸿, 宋轩, 田钊. 一种可隐藏敏感文档和发送者身份的区块链隐蔽通信模型[J]. 电子学报, 2022, 50(4): 1002-1013.
[8]	严莉, 张凯, 徐浩, 韩圣亚, 刘珅岐, 史玉良. 基于图注意力机制和Transformer的异常检测[J]. 电子学报, 2022, 50(4): 900-908.
[9]	袁冠, 邴睿, 刘肖, 代伟, 张艳梅, 蔡卓. 基于时空图神经网络的手势识别[J]. 电子学报, 2022, 50(4): 921-931.
[10]	王延达, 陈炜通, 皮德常, 岳琳. 一种自适应记忆神经网络多跳读取与覆盖度机制结合的药物推荐模型[J]. 电子学报, 2022, 50(4): 943-953.
[11]	崔亚奇, 何友, 唐田田, 熊伟. 一种深度学习航迹关联方法[J]. 电子学报, 2022, 50(3): 759-763.
[12]	王志晓, 张磊, 孙成成, 芮晓彬, 黄珍珍, 张孙贤. 基于社区划分与连边逆序放回的网络分解算法[J]. 电子学报, 2022, 50(3): 540-547.
[13]	刘微容, 米彦春, 杨帆, 张彦, 郭宏林, 刘仲民. 基于多级解码网络的图像修复[J]. 电子学报, 2022, 50(3): 625-636.
[14]	高鹏, 柴鹏翔, 郎俊. 基于0-1背包算法的社交网络行为隐写术[J]. 电子学报, 2022, 50(3): 753-758.
[15]	张浩, 胡昌华, 杜党波, 裴洪, 张建勋. 多状态影响下基于Bi‑LSTM网络的锂电池剩余寿命预测方法[J]. 电子学报, 2022, 50(3): 619-624.