-
Evaluating influential spreaders in networks is of great significance for promoting the dissemination of beneficial information or inhibiting the spreading of harmful information. Currently, there are some central indices that can be used to evaluate spreading influence of {nodes}. However, most of them ignore the spreading probability and take into consideration only the network topology or the location of source node, so the excellent results can be achieved only when the spreading probability is in a specified range. For example, the degree centrality is appropriate for a minor spreading probability, but to ensure the accuracy, semi-local and closeness centralities are more suitable for a slightly larger one. To solve the sensitivity problem of spreading probability, a novel algorithm is proposed based on the extension of degree. In this algorithm, the coverage area of degree is recursively extended by the overlapping of degree of neighbors, which makes different extension levels correspond to different spreading probabilities. For a certain spreading probability, the proper level index is calculated by finding the most correlate ranking sequences of sampling {nodes}, which is obtained by matching the results of different spreading levels and SIR simulation. In this paper, the relationship between extension level and spreading probability is explained by the theory of fitting the weight and infected possibility of {nodes}, and the feasibility of the sampling method is verified by the computational experiments. The experimental results on both real and computer-generated datasets show that the proposed algorithm can effectively evaluate the spreading influences of {nodes} under different spreading probabilities, and the performance is close or even superior to that evaluated by using other central indices.
-
Keywords:
- complex network /
- spread influence /
- extension degree
[1] Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136
[2] Newman M E J 2003 SIAM Rev. 45 167
[3] Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[4] Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101
[5] Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527
[6] Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904
[7] Freeman L C 1978-1979 Soc. Networks 1 215
[8] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[10] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150
[11] Bae J, Kim S 2014 Physica A 395 549
[12] Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130
[13] Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57
[14] Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]
[15] Ren X L, L L Y 2014 Chin. Sci. Bul. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[16] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[17] Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]
[18] Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097
[19] Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803
[20] Newman M E J 2002 Phys. Rev. E 66 016128
[21] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
[22] Kendall M G 1938 Biometrika 30 81
[23] 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]
[24] Xie N 2006 M. S. Dissertation (Bristol: University of Bristol)
[25] Newman M E J 2006 Phys. Rev. E 74 036104
[26] Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814
[27] Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103
[28] Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122
[29] Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701
[30] Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110
-
[1] Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136
[2] Newman M E J 2003 SIAM Rev. 45 167
[3] Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47
[4] Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101
[5] Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527
[6] Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904
[7] Freeman L C 1978-1979 Soc. Networks 1 215
[8] Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[9] Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[10] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150
[11] Bae J, Kim S 2014 Physica A 395 549
[12] Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130
[13] Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57
[14] Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]
[15] Ren X L, L L Y 2014 Chin. Sci. Bul. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[16] Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031
[17] Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]
[18] Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097
[19] Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803
[20] Newman M E J 2002 Phys. Rev. E 66 016128
[21] Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200
[22] Kendall M G 1938 Biometrika 30 81
[23] 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]
[24] Xie N 2006 M. S. Dissertation (Bristol: University of Bristol)
[25] Newman M E J 2006 Phys. Rev. E 74 036104
[26] Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814
[27] Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103
[28] Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122
[29] Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701
[30] Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110
Catalog
Metrics
- Abstract views: 8544
- PDF Downloads: 658
- Cited By: 0