-
在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法.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.
-
Keywords:
- complex networks /
- influential node /
- community detecting /
- centrality
[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] 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
计量
- 文章访问数: 7893
- PDF下载量: 2252
- 被引次数: 0
下载:
