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

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
- 通讯作者:
- 张健沛
- 作者简介:
- 李泓波 男，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
- Supported by:
- National Natural Science Foundation of China (No.61073041, No.61073043); Natural Science Foundation of Heilongjiang Province, China (No.F200901, No.F200917); Science and Technology Research Foudation of Education Department of Heilongjiang Province (No.12531529); Excellent Academic Leader Fund of Harbin, Heilongjiang Province (No.2010RFXXG002, No.2011RFXXG015); Research Fund for the Doctoral Program of Higher Education of China (No.20112304110011)

摘要/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, et al. 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]	郑云飞, 王晓兵, 张雄伟, 曹铁勇, 孙蒙. 基于金字塔知识的自蒸馏HRNet目标分割方法[J]. 电子学报, 2023, 51(3): 746-756.
[2]	李钦, 刘伟, 牛朝阳, 宝音图, 惠周勃. 低信噪比下基于分裂EfficientNet网络的雷达信号调制方式识别[J]. 电子学报, 2023, 51(3): 675-686.
[3]	隗昊, 唐焕玲, 周爱, 张益嘉, 陈飞, 鲁明羽. 基于双路分段注意力神经张量网络的临床文本关系抽取[J]. 电子学报, 2023, 51(3): 658-665.
[4]	黄赟, 张帆, 郭威, 陈立, 羊光. 一种基于数据标准差的卷积神经网络量化方法[J]. 电子学报, 2023, 51(3): 639-647.
[5]	范兵兵, 何庭建, 张聪炫, 陈震, 黎明. 联合遮挡约束与残差补偿的特征金字塔光流计算方法[J]. 电子学报, 2023, 51(3): 648-657.
[6]	张金颢, 周恒, 张守龙, 蒋廷勇, 王胜涛, 刘真. 基于仿真及神经网络的大型电磁脉冲模拟器近区场计算[J]. 电子学报, 2023, 51(3): 712-719.
[7]	吕杭, 蒋明峰, 李杨, 张鞠成, 王志康. 基于混合时频域特征的卷积神经网络心律失常分类方法的研究[J]. 电子学报, 2023, 51(3): 701-711.
[8]	杨威, 李玮杰, 刘永祥, 黎湘. 基于测地线流式核的雷达目标高分辨距离像鲁棒识别方法[J]. 电子学报, 2023, 51(3): 527-536.
[9]	许辰人, 马翔天, 徐昊天, 刘启瑞, 王诚科, 王雄, 高峰, 陈晓光, 孔令和. 5G抗干扰技术综述[J]. 电子学报, 2023, 51(3): 765-778.
[10]	唐维伟, 钟胜, 卢金仪, 颜露新, 谭富中, 邹旭, 徐文辉. 基于FPGA的Skynet网络结构优化及高时效实现[J]. 电子学报, 2023, 51(2): 314-323.
[11]	杨利平, 侯振威, 辜小花, 郝峻永. 弱标签声音事件检测的空间-通道特征表征与自注意池化[J]. 电子学报, 2023, 51(2): 297-306.
[12]	刘少鹏, 赵慧民, 洪佳明, 吴晓航, 许发宝, 欧阳佳, 梁鹏, 熊建斌. 面向医学图像生成的鲁棒条件生成对抗网络[J]. 电子学报, 2023, 51(2): 427-437.
[13]	王子为, 鲁继文, 周杰. 基于自适应梯度优化的二值神经网络[J]. 电子学报, 2023, 51(2): 257-266.
[14]	张轶, 翟盛华, 陶海红. 雨衰时间序列的混沌识别与预测[J]. 电子学报, 2023, 51(2): 365-371.
[15]	许新征, 李杉. 基于特征膨胀卷积模块的轻量化技术研究[J]. 电子学报, 2023, 51(2): 355-364.