搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用邻域“结构洞”寻找社会网络中最具影响力节点

苏晓萍 宋玉蓉

引用本文:
Citation:

利用邻域“结构洞”寻找社会网络中最具影响力节点

苏晓萍, 宋玉蓉

Leveraging neighborhood “structural holes” to identifying key spreaders in social networks

Su Xiao-Ping, Song Yu-Rong
PDF
导出引用
  • 识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.
    The identifying of influential nodes in large-scale complex networks is an important issue in optimizing network structure and enhancing robustness of a system. To measure the role of nodes, classic methods can help identify influential nodes, but they have some limitations to social networks. Local metric is simple but it can only take into account the neighbor size, and the topological connections among the neighbors are neglected, so it can not reflect the interaction between the nodes. The global metrics is difficult to use in large social networks because of the high computational complexity. Meanwhile, in the classic methods, the unique community characteristics of the social networks are not considered. To make a trade off between affections and efficiency, a local structural centrality measure is proposed which is based on nodes' a nd their ‘neighbors’ structural holes. Both the node degree and “bridge” property are reflected in computing node constraint index. SIR (Susceptible-Infected-Recovered) model is used to evaluate the ability to spread nodes. Simulations of four real networks show that our method can rank the capability of spreading nodes more accurately than other metrics. This algorithm has strong robustness when the network is subjected to sybil attacks.
    • 基金项目: 国家自然科学基金(批准号: 61373136, 61103051)、教育部人文社会科学研究项目(批准号: 12YJAZH120)和南京工业职业技术学院重大项目(批准号: Yk13-02-03)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61373136, 61103051), the Ministry of Education Research in the Humanities and Social Sciences Planning Fund Project, China (Grant No. 12YJAZH120) and the Nanjing Institute of Industry Technology Major Programs, China (Grant No. Yk13-02-03).
    [1]

    Wang L, Wang J, Shen H W, Cheng X Q 2013 Chin. Phys. B 22 108903

    [2]

    Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS one 8 e59613

    [3]

    Konstantin K, Ángeles S M, San M M 2012 Scientific Reports 2 292

    [4]

    Page L, Brin S, Motwani R, Winograd T 1999 Stanford InfoLab

    [5]

    Overington J P, Al-Lazikani B, Hopkins A L 2006 Nature Reviews Drug Discovery 5 993

    [6]

    Yıldırım M A, Goh K I, Cusick M E, Barabási A L, Vidal M 2007 Nature Biotechnol. 25 1119

    [7]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [8]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [9]

    Albert R, Jeong H, Barabási A L 2000 Nature 406 378

    [10]

    Freeman L C 1977 Sociometry 40 35

    [11]

    Krackhardt D 1990 Administr. Sci. Quart. 35 342

    [12]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888

    [13]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A: Statist. Mech. Appl. 391 1777

    [14]

    Chen D B, Gao H, L L Y, Zhou T 2013 PloS one 8 e77455

    [15]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [16]

    Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Statist. Mech.: Theory and Experiment 2010 P10011

    [17]

    Bae J, Kim S 2014 Physica A: Statist. Mech. Appl. 395 549

    [18]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Statist. Mech. Appl. 392 4154

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [20]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902

    [21]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

    [22]

    Palla G, Barabási A L, Vicsek T 2007 Nature 446 664

    [23]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [24]

    Burt R S 2009 Structural Holes: The Social Structure of Competition (London: Harvard University Press) pp53-58

    [25]

    Burt R S, Kilduff M, Tasselli S 2013 Ann. Rev. Psychol. 64 527

    [26]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 PNAS 109 5962

    [27]

    Sun Y, Liu C, Zhang C, Zhang Z 2014 Phys. Lett. A 378 635

    [28]

    Liu C, Zhang Z 2014 Commun. Nonlinear Sci. Numer. Simulat. 19 896

    [29]

    Zhang Z K, Zhang C X, Han X P, Liu C 2014 PloS one 9 e95785

    [30]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [31]

    Knight W R 1966 J. Amer. Statist. Associat. 61 436

    [32]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

  • [1]

    Wang L, Wang J, Shen H W, Cheng X Q 2013 Chin. Phys. B 22 108903

    [2]

    Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS one 8 e59613

    [3]

    Konstantin K, Ángeles S M, San M M 2012 Scientific Reports 2 292

    [4]

    Page L, Brin S, Motwani R, Winograd T 1999 Stanford InfoLab

    [5]

    Overington J P, Al-Lazikani B, Hopkins A L 2006 Nature Reviews Drug Discovery 5 993

    [6]

    Yıldırım M A, Goh K I, Cusick M E, Barabási A L, Vidal M 2007 Nature Biotechnol. 25 1119

    [7]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [8]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [9]

    Albert R, Jeong H, Barabási A L 2000 Nature 406 378

    [10]

    Freeman L C 1977 Sociometry 40 35

    [11]

    Krackhardt D 1990 Administr. Sci. Quart. 35 342

    [12]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888

    [13]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A: Statist. Mech. Appl. 391 1777

    [14]

    Chen D B, Gao H, L L Y, Zhou T 2013 PloS one 8 e77455

    [15]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [16]

    Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Statist. Mech.: Theory and Experiment 2010 P10011

    [17]

    Bae J, Kim S 2014 Physica A: Statist. Mech. Appl. 395 549

    [18]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Statist. Mech. Appl. 392 4154

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [20]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902

    [21]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

    [22]

    Palla G, Barabási A L, Vicsek T 2007 Nature 446 664

    [23]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [24]

    Burt R S 2009 Structural Holes: The Social Structure of Competition (London: Harvard University Press) pp53-58

    [25]

    Burt R S, Kilduff M, Tasselli S 2013 Ann. Rev. Psychol. 64 527

    [26]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 PNAS 109 5962

    [27]

    Sun Y, Liu C, Zhang C, Zhang Z 2014 Phys. Lett. A 378 635

    [28]

    Liu C, Zhang Z 2014 Commun. Nonlinear Sci. Numer. Simulat. 19 896

    [29]

    Zhang Z K, Zhang C X, Han X P, Liu C 2014 PloS one 9 e95785

    [30]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [31]

    Knight W R 1966 J. Amer. Statist. Associat. 61 436

    [32]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

  • [1] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [2] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [3] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [4] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [5] 袁铭. 带有层级结构的复杂网络级联失效模型. 物理学报, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
    [6] 王兴元, 赵仲祥. 基于节点间依赖度的社团结构划分方法. 物理学报, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [7] 丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. 物理学报, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [8] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [9] 张檬, 吕翎, 吕娜, 范鑫. 结构与参量不确定的网络与网络之间的混沌同步 . 物理学报, 2012, 61(22): 220508. doi: 10.7498/aps.61.220508
    [10] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [11] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [12] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [13] 袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. 物理学报, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [14] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [15] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [16] 邵斐, 蒋国平. 基于社团结构的负载传输优化策略研究. 物理学报, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
    [17] 沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测. 物理学报, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [18] 王高峡, 沈轶. 网络的模块矩阵及其社团结构指标. 物理学报, 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
计量
  • 文章访问数:  5675
  • PDF下载量:  1822
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-05-19
  • 修回日期:  2014-09-09
  • 刊出日期:  2015-01-05

利用邻域“结构洞”寻找社会网络中最具影响力节点

  • 1. 南京工业职业技术学院计算机与软件学院, 南京 210046;
  • 2. 南京邮电大学自动化学院, 南京 210003
    基金项目: 国家自然科学基金(批准号: 61373136, 61103051)、教育部人文社会科学研究项目(批准号: 12YJAZH120)和南京工业职业技术学院重大项目(批准号: Yk13-02-03)资助的课题.

摘要: 识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.

English Abstract

参考文献 (32)

目录

    /

    返回文章
    返回