Search

Article

x

留言板

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

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

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

Su Xiao-Ping Song Yu-Rong

Citation:

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

Su Xiao-Ping, Song Yu-Rong
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • 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.
    • 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] Shen Li-Feng, Wang Jian-Bo, Du Zhan-Wei, Xu Xiao-Ke. Bilayer network spreading dynamics driven by community structure and activity. Acta Physica Sinica, 2023, 72(6): 068701. doi: 10.7498/aps.72.20222206
    [2] Yang Song-Qing, Jiang Yuan, Tong Tian-Chi, Yan Yu-Wei, Gan Ge-Sheng. A method of evaluating importance of nodes in complex network based on Tsallis entropy. Acta Physica Sinica, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [3] Su Zhen, Gao Chao, Li Xiang-Hua. Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [4] Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [5] Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie. Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [6] Yuan Ming. A cascading failure model of complex network with hierarchy structure. Acta Physica Sinica, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
    [7] Wang Xing-Yuan, Zhao Zhong-Xiang. Partitioning community structure in complex networks based on node dependent degree. Acta Physica Sinica, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [8] Ding Yi-Min, Ding Zhuo, Yang Chang-Ping. The network model of urban subway networks with community structure. Acta Physica Sinica, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [9] Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [10] Yang Pu, Zheng Zhi-Gang. Analysis the convergency speed of estimating the network topology based on the dynamical synchronization. Acta Physica Sinica, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [11] Gao Zhong-Ke, Jin Ning-De, Yang Dan, Zhai Lu-Sheng, Du Meng. Complex networks from multivariate time series for characterizing nonlinear dynamics of two-phase flow patterns. Acta Physica Sinica, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [12] LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [13] Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection. Acta Physica Sinica, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [14] Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun. Multi-resolution density modularity for finding community structure in complex networks. Acta Physica Sinica, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [15] Cui Ai-Xiang, Fu Yan, Shang Ming-Sheng, Chen Duan-Bing, Zhou Tao. Emergence of local structures in complex network:common neighborhood drives the network evolution. Acta Physica Sinica, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [16] Shao Fei, Jiang Guo-Ping. Optimal traffic routing strategy based on community structure. Acta Physica Sinica, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
    [17] Shen Yi, Xu Huan-Liang. The evaluation function of weight similarity and its application in community detection in weighted networks. Acta Physica Sinica, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [18] Wang Gao-Xia, Shen Yi. Modularity matrix of networks and the measure of community structure. Acta Physica Sinica, 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
    [19] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] Gao Zhong-Ke, Jin Ning-De. Complex network community structure of two-phase flow pattern and its statistical characteristics. Acta Physica Sinica, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
Metrics
  • Abstract views:  9274
  • PDF Downloads:  1895
  • Cited By: 0
Publishing process
  • Received Date:  19 May 2014
  • Accepted Date:  09 September 2014
  • Published Online:  05 January 2015

/

返回文章
返回