x

## 留言板

A new approach to identify influential spreaders in complex networks

## A new approach to identify influential spreaders in complex networks

Hu Qing-Cheng, Yin Yan-Shen, Ma Peng-Fei, Gao Yang, Zhang Yong, Xing Chun-Xiao
• #### Abstract

In the research of the propagation model of complex network, it is of theoretical and practical significance to detect the most influential nodes. Global metrics such as degree centrality, closeness centrality, betweenness centrality and K-shell centrality can be used to identify the influential spreaders. Each of these approaches is simple but has a low accuracy. We propose K-shell and community centrality (KSC) model. This model considers not only the internal properties of nodes but also the external properties, such as the community which these nodes belong to. The susceptible-infected-recovered model is used to evaluate the performance of KSC model. The experimental result shows that our method is better to detect the most influential nodes. This paper comes up with a new idea and method for the study in this field.

#### Authors and contacts

• Funds: Project supported by National Basic Research Program of China (Grant No. 2011CB302302) and the National High Technology Research and Development Program of China (Grant No. 2012AA09A408).

#### References

 [1] Watts D J, Strogatz S H 1998 Nature 393 440 [2] Barabási A L, Albert R 1999 Science 286 509 [3] Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a [4] Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104 [5] Kempe D, Kleinberg J, Tardos E 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137 [6] Gomez-Rodriguez M, Leskovec J, Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington, DC, USA, July 25-28, 2010 p1019 [7] Budak C, Agrawal D, El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad, India, March 28-April 1, 2011 p665 [8] Mislove A, Marcon M, Gummadi K P, Druschel P, Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications Kyoto, Japan, August 27-31, 2007 p29 [9] Yuan W G, Liu Y, Cheng J J 2013 Acta Phys. Sin. 62 038901 (in Chinese) [苑卫国, 刘云, 程军军 2013 物理学报 62 038901] [10] Weng J, Lim E P, Jiang J, He Q 2010 Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010 New York, NY, USA, February 4-6, 2010 p261 [11] Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313] [12] Naveed N, Gottron T, Kunegis J, Alhadi A C 2011 Proceedings of the 20th ACM International Conference on Information and Knowledge Management Koblenz, Germany, June 14-17, 2011 p1 [13] Gu Y R, Xia L L 2012 Acta Phys. Sin. 61 238701 (in Chinese) [顾亦然, 夏玲玲 2012 物理学报 61 238701] [14] Swamynathan G, Wilson C, Boe B, Almeroth K, Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York, USA, August 18, 2008 p1 [15] Mislove A, Marcon M, Krishna P G, Druschel P, Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC'07) ACM New York, USA, October 24-26, 2007 p29 [16] Albert R, Jeong H, Barabasi A L 2000 Nature 406 378 [17] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200 [18] Freeman L C 1977 Sociometry 40 35 [19] Brin S, Page L 1998 Comput. Netw. ISDN Syst. 30 107 [20] Opsahl T, Agneessens F, Skvoretz J 2010 Soc. Networks 32 245 [21] Sabidussi G 1966 Psychometrika 31 581 [22] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Tech. Rep. Phys. Soc. 1001 5285 [23] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 p1150 [24] Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821 [25] Fortunato S 2010 Phys. Rep. 486 75 [26] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113 [27] Freeman L C 1979 Social Networks 1 215 [28] Sabidussi G 1966 Psychometrika 31 581 [29] Lin K 1970 Bell Syst. Tech. J. 49 291 [30] Newman M E J 2004 Phys. J. B 38 321 [31] Newman M E J 2004 Phys. Rev. E 69 066133 [32] Guimera R, Amaral L A N 2005 Nature 433 7028 [33] Burt R 2004 Am. J. Soc. 110 349 [34] Granovetter M 1973 Am. J. Soc. 78 1360 [35] Roy M Anderson, Robert M May 1992 Infectious Diseases of Humans: Dynamics and Control. (New York: Oxford University Press) p66 [36] Diekmann O, Heesterbeek J A P 2001 Mathematical Epidemiology of Infectious Diseases: Model Building, Analysis and Interpretation (New York: Wiley Series in Mathematical & Computational Biology) [37] Hethcote H W 2000 Soc. Industr. Appl. Math. 42 599 [38] Bernoulli D, Blower S 2004 Rev. Med. Virol. 14 275 [39] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777 [40] Xie N 2006 M. S. Dissertation (Bristo: University of Bristol) [41] Newman M E J 2006 Phys. Rev. E 74 36104 [42] Spring N, Mahajan R, Wetherall D, Anderson T 2004 Acm. Sigcomm. Comp. Commu. Rev. 32 3 [43] Guimerá R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

#### Cited By

•  [1] Watts D J, Strogatz S H 1998 Nature 393 440 [2] Barabási A L, Albert R 1999 Science 286 509 [3] Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a [4] Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104 [5] Kempe D, Kleinberg J, Tardos E 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137 [6] Gomez-Rodriguez M, Leskovec J, Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington, DC, USA, July 25-28, 2010 p1019 [7] Budak C, Agrawal D, El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad, India, March 28-April 1, 2011 p665 [8] Mislove A, Marcon M, Gummadi K P, Druschel P, Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications Kyoto, Japan, August 27-31, 2007 p29 [9] Yuan W G, Liu Y, Cheng J J 2013 Acta Phys. Sin. 62 038901 (in Chinese) [苑卫国, 刘云, 程军军 2013 物理学报 62 038901] [10] Weng J, Lim E P, Jiang J, He Q 2010 Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010 New York, NY, USA, February 4-6, 2010 p261 [11] Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313] [12] Naveed N, Gottron T, Kunegis J, Alhadi A C 2011 Proceedings of the 20th ACM International Conference on Information and Knowledge Management Koblenz, Germany, June 14-17, 2011 p1 [13] Gu Y R, Xia L L 2012 Acta Phys. Sin. 61 238701 (in Chinese) [顾亦然, 夏玲玲 2012 物理学报 61 238701] [14] Swamynathan G, Wilson C, Boe B, Almeroth K, Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York, USA, August 18, 2008 p1 [15] Mislove A, Marcon M, Krishna P G, Druschel P, Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC'07) ACM New York, USA, October 24-26, 2007 p29 [16] Albert R, Jeong H, Barabasi A L 2000 Nature 406 378 [17] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200 [18] Freeman L C 1977 Sociometry 40 35 [19] Brin S, Page L 1998 Comput. Netw. ISDN Syst. 30 107 [20] Opsahl T, Agneessens F, Skvoretz J 2010 Soc. Networks 32 245 [21] Sabidussi G 1966 Psychometrika 31 581 [22] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Tech. Rep. Phys. Soc. 1001 5285 [23] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 p1150 [24] Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821 [25] Fortunato S 2010 Phys. Rep. 486 75 [26] Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113 [27] Freeman L C 1979 Social Networks 1 215 [28] Sabidussi G 1966 Psychometrika 31 581 [29] Lin K 1970 Bell Syst. Tech. J. 49 291 [30] Newman M E J 2004 Phys. J. B 38 321 [31] Newman M E J 2004 Phys. Rev. E 69 066133 [32] Guimera R, Amaral L A N 2005 Nature 433 7028 [33] Burt R 2004 Am. J. Soc. 110 349 [34] Granovetter M 1973 Am. J. Soc. 78 1360 [35] Roy M Anderson, Robert M May 1992 Infectious Diseases of Humans: Dynamics and Control. (New York: Oxford University Press) p66 [36] Diekmann O, Heesterbeek J A P 2001 Mathematical Epidemiology of Infectious Diseases: Model Building, Analysis and Interpretation (New York: Wiley Series in Mathematical & Computational Biology) [37] Hethcote H W 2000 Soc. Industr. Appl. Math. 42 599 [38] Bernoulli D, Blower S 2004 Rev. Med. Virol. 14 275 [39] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777 [40] Xie N 2006 M. S. Dissertation (Bristo: University of Bristol) [41] Newman M E J 2006 Phys. Rev. E 74 36104 [42] Spring N, Mahajan R, Wetherall D, Anderson T 2004 Acm. Sigcomm. Comp. Commu. Rev. 32 3 [43] Guimerá R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103
•  [1] Dong Zheng-Qiong, Zhao Hang, Zhu Jin-Long, Shi Ya-Ting. Influence of incident illumination on optical scattering measurement of typical photoresist nanostructure. Acta Physica Sinica, 2020, 69(3): 030601. doi: 10.7498/aps.69.20191525 [2] . The influence of the secondary electron emission characteristic of dielectric materials on the microwave breakdown. Acta Physica Sinica, 2020, (): . doi: 10.7498/aps.69.20200026 [3] Wang Lin, Wei Lai, Wang Zheng-Xiong. Effect of out-of-plane driving flow on formation of plasmoids in current sheet system. Acta Physica Sinica, 2020, 69(5): 059401. doi: 10.7498/aps.69.20191612 [4] Liu Jia-He, Lu Jia-Zhe, Lei Jun-Jie, Gao Xun, Lin Jing-Quan. Effect of ambient gas pressure on characteristics of air plasma induced by nanosecond laser. Acta Physica Sinica, 2020, 69(5): 057401. doi: 10.7498/aps.69.20191540 [5] Ren Xian-Li, Zhang Wei-Wei, Wu Xiao-Yong, Wu Lu, Wang Yue-Xia. Prediction of short range order in high-entropy alloys and its effect on the electronic, magnetic and mechanical properties. Acta Physica Sinica, 2020, 69(4): 046102. doi: 10.7498/aps.69.20191671 [6] . Effect of Swift Heavy Ions Irradiation on the Microstructure and Current-Carrying Capability in YBa2Cu3O7-δ High Temperature Superconductor Films. Acta Physica Sinica, 2020, (): . doi: 10.7498/aps.69.20191914 [7] Liang Jin-Jie, Gao Ning, Li Yu-Hong. Surface effect on \begin{document}${\langle 100 \rangle }$\end{document} interstitial dislocation loop in iron. Acta Physica Sinica, 2020, 69(3): 036101. doi: 10.7498/aps.69.20191379
•  Citation:
##### Metrics
• Abstract views:  1706
• Cited By: 0
##### Publishing process
• Received Date:  25 January 2013
• Accepted Date:  25 March 2013
• Published Online:  20 July 2013

## A new approach to identify influential spreaders in complex networks

• 1. Research Institute of Information Technology Tsinghua National Laboratory for Information Science and Technology Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Fund Project:  Project supported by National Basic Research Program of China (Grant No. 2011CB302302) and the National High Technology Research and Development Program of China (Grant No. 2012AA09A408).

Abstract: In the research of the propagation model of complex network, it is of theoretical and practical significance to detect the most influential nodes. Global metrics such as degree centrality, closeness centrality, betweenness centrality and K-shell centrality can be used to identify the influential spreaders. Each of these approaches is simple but has a low accuracy. We propose K-shell and community centrality (KSC) model. This model considers not only the internal properties of nodes but also the external properties, such as the community which these nodes belong to. The susceptible-infected-recovered model is used to evaluate the performance of KSC model. The experimental result shows that our method is better to detect the most influential nodes. This paper comes up with a new idea and method for the study in this field.

Reference (43)

/