Rapid identifying high-influence nodes in complex networks

doi:10.1088/1674-1056/24/10/100101

中国物理B ›› 2015, Vol. 24 ›› Issue (10): 100101-100101.doi: 10.1088/1674-1056/24/10/100101

• GENERAL • 下一篇

Rapid identifying high-influence nodes in complex networks

宋波^a, 蒋国平^b, 宋玉蓉^b, 夏玲玲^a

a School of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;
b School of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

收稿日期:2015-02-11 修回日期:2015-04-27 出版日期:2015-10-05 发布日期:2015-10-05
基金资助:
Project supported by the National Natural Science Foundation of China (Grant Nos. 61374180 and 61373136), the Ministry of Education Research in the Humanities and Social Sciences Planning Fund Project, China (Grant No. 12YJAZH120), and the Six Projects Sponsoring Talent Summits of Jiangsu Province, China (Grant No. RLD201212).

Rapid identifying high-influence nodes in complex networks

Song Bo (宋波)^a, Jiang Guo-Ping (蒋国平)^b, Song Yu-Rong (宋玉蓉)^b, Xia Ling-Ling (夏玲玲)^a

a School of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;
b School of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Received:2015-02-11 Revised:2015-04-27 Online:2015-10-05 Published:2015-10-05
Contact: Jiang Guo-Ping E-mail:jianggp@njupt.edu.cn
Supported by:
Project supported by the National Natural Science Foundation of China (Grant Nos. 61374180 and 61373136), the Ministry of Education Research in the Humanities and Social Sciences Planning Fund Project, China (Grant No. 12YJAZH120), and the Six Projects Sponsoring Talent Summits of Jiangsu Province, China (Grant No. RLD201212).

摘要/Abstract

摘要： A tiny fraction of influential individuals play a critical role in the dynamics on complex systems. Identifying the influential nodes in complex networks has theoretical and practical significance. Considering the uncertainties of network scale and topology, and the timeliness of dynamic behaviors in real networks, we propose a rapid identifying method (RIM) to find the fraction of high-influential nodes. Instead of ranking all nodes, our method only aims at ranking a small number of nodes in network. We set the high-influential nodes as initial spreaders, and evaluate the performance of RIM by the susceptible-infected-recovered (SIR) model. The simulations show that in different networks, RIM performs well on rapid identifying high-influential nodes, which is verified by typical ranking methods, such as degree, closeness, betweenness, and eigenvector centrality methods.

关键词: high-influence nodes, dynamic model, complex networks, centrality measures

Abstract: A tiny fraction of influential individuals play a critical role in the dynamics on complex systems. Identifying the influential nodes in complex networks has theoretical and practical significance. Considering the uncertainties of network scale and topology, and the timeliness of dynamic behaviors in real networks, we propose a rapid identifying method (RIM) to find the fraction of high-influential nodes. Instead of ranking all nodes, our method only aims at ranking a small number of nodes in network. We set the high-influential nodes as initial spreaders, and evaluate the performance of RIM by the susceptible-infected-recovered (SIR) model. The simulations show that in different networks, RIM performs well on rapid identifying high-influential nodes, which is verified by typical ranking methods, such as degree, closeness, betweenness, and eigenvector centrality methods.

Key words: high-influence nodes, dynamic model, complex networks, centrality measures

中图分类号: (Science and society)

01.75.+m

89.70.Eg (Computational complexity) 89.75.Fb (Structures and organization in complex systems)

宋波, 蒋国平, 宋玉蓉, 夏玲玲. Rapid identifying high-influence nodes in complex networks[J]. 中国物理B, 2015, 24(10): 100101-100101.

Song Bo (宋波), Jiang Guo-Ping (蒋国平), Song Yu-Rong (宋玉蓉), Xia Ling-Ling (夏玲玲). Rapid identifying high-influence nodes in complex networks[J]. Chin. Phys. B, 2015, 24(10): 100101-100101.

参考文献 32

[1]	Wu X D, Li Y and Li L 2014 Chin. J. Comput. 37 735 (in Chinese)
[2]	Wang L, Wang J, Shen H W and Cheng X Q 2013 Chin. Phys. B 22 108903
[3]	Konstantin K, Ángeles S M and San M M 2012 Sci. Rep. 2 292
[4]	Yı ldı rı m M A, Goh K I, Cusick M E, Barabási A L and Vidal M 2007 Nat. Biotechnol. 25 1119
[5]	Ren X L and Lü L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese)
[6]	Bonacich P 1972 J. Math. Sociol. 2 113
[7]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E and Makse H A 2010 Nat. Phys. 6 888
[8]	Freeman L C 1977 Sociometry 40 35
[9]	Freeman L C 1979 Social Networks 1 215
[10]	Callaway D, Newman M, Strogatz S and Watts D 2000 Phys. Rev. Lett. 85 5468
[11]	Brin S and Page L 1998 Computer Networks and ISDN Systems 30 107
[12]	Kleinberg J M 1999 JACM 46 604
[13]	Li P X, Ren Y Q and Xi Q M 2004 Systems Engineering 22 13 (in Chinese)
[14]	Tan Y J, Wu J and Deng H Z 2006 Systems Engineering: Theory & Practice 26 79( in Chinese)
[15]	Chen D B, Lü L Y and Shang M S, Zhang Y C and Zhou T 2012 Physica A 391 1777
[16]	Lü L, Zhang Y C, Yeung C H and Zhou T 2011 PLoS ONE 6 e21202
[17]	Zhao Z Y, Yu H, Zhu Z L and Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese)
[18]	Hu Q C, Yin Y S and Ma P F 2013 Acta Phys. Sin. 62 140101 (in Chinese)
[19]	Ren Z M, Liu J G, Shao F, Hu Z L and Guo Q 2013 Acta Phys. Sin. 62 108902(in Chinese)
[20]	Yang X, Huang D C and Zhang Z K 2015 Acta Phys. Sin. 64 050502(in Chinese)
[21]	Su X P and Song Y R 2015 Acta Phys. Sin. 64 020101(in Chinese)
[22]	Pei S, Muchnik L, Andrade J S Jr and Zheng Z 2014 Sci. Rep. 4 5547
[23]	Iyer S, Killingback T, Sundaram B and Wang Z 2013 PLoS ONE 8 e59613
[24]	Gross T, D'Lima C J D and Blasius B 2006 Phys. Rev. Lett. 96 208701
[25]	Pastor-Satorras R and Vespignani A 2001 Phys. Rev. Lett. 86 3200
[26]	Floyd R W 1962 Commun. ACM 5 345
[27]	Johnson and Donald B 1977 J. ACM 24 1
[28]	Brandes U 2001 J. Math. Sociol. 25 163
[29]	Zachary W W 1977 J. Anthropol. Res. 33 452
[30]	Guimerá R, Danon L, Díz-Guilera A, Giralt F and Arenas A 2003 Phys. Rev. E 68 065103
[31]	Watts D J and Strogatz S H 1998 Nature 393 440
[32]	Newman M E J 2002 Phys. Rev. Lett. 89 208701

Rapid identifying high-influence nodes in complex networks

Rapid identifying high-influence nodes in complex networks

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 32

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[2]	Guangbao Lu(陆广宝), Jun Liu(刘俊), Chuanguo Zhang(张传国), Yang Gao(高扬), and Yonggang Li(李永钢). Dynamic modeling of total ionizing dose-induced threshold voltage shifts in MOS devices[J]. 中国物理B, 2023, 32(1): 18506-018506.
[3]	Guang-Han Peng(彭光含), Chun-Li Luo(罗春莉), Hong-Zhuan Zhao(赵红专), and Hui-Li Tan(谭惠丽). A novel lattice model integrating the cooperative deviation of density and optimal flux under V2X environment[J]. 中国物理B, 2023, 32(1): 18902-018902.
[4]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.
[5]	Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Characteristics of vapor based on complex networks in China[J]. 中国物理B, 2022, 31(4): 49201-049201.
[6]	Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks[J]. 中国物理B, 2022, 31(2): 20503-020503.
[7]	Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control[J]. 中国物理B, 2022, 31(10): 100504-100504.
[8]	Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks[J]. 中国物理B, 2021, 30(8): 88901-088901.
[9]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[10]	Yuansheng Chen(陈元盛) and Fei Tong(仝飞). Stability analysis of hydro-turbine governing system based on machine learning[J]. 中国物理B, 2021, 30(12): 120509-120509.
[11]	Geng Zhang(张埂) and Da-Dong Tian(田大东). Stability analysis of multiple-lattice self-anticipative density integration effect based on lattice hydrodynamic model in V2V environment[J]. 中国物理B, 2021, 30(12): 120201-120201.
[12]	杨远志, 胡敏, 黄泰愚. Influential nodes identification in complex networks based on global and local information[J]. 中国物理B, 2020, 29(8): 88903-088903.
[13]	闫小丽, 崔亚鹏, 倪顺江. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. 中国物理B, 2020, 29(4): 48902-048902.
[14]	石勇, 李博, 龙文. Pyramid scheme model for consumption rebate frauds[J]. 中国物理B, 2019, 28(7): 78901-078901.
[15]	朱世钊, 王玉青, 汪秉宏. Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms[J]. 中国物理B, 2019, 28(10): 108901-108901.