-
对网络中节点的传播影响力进行评估具有十分重要的意义, 有助于促进有益或抑制有害信息的传播. 目前, 多种中心性指标可用于对节点的传播影响力进行评估, 然而它们一般只有当传播率处于特定范围时才能取得理想的结果. 例如, 度值中心性指标在传播率较小时较为合适, 而半局部中心性和接近中心性指标则适用于稍大一些的传播率. 为了解决各种评估指标对传播率敏感的问题, 提出了一种基于扩展度的传播影响力评估算法. 算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展, 使不同的扩展层次对应于不同的传播率, 并通过抽样测试确定了适合于特定传播率的层次数. 真实和模拟数据集上的实验结果表明, 通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估, 其准确性能够达到或优于利用其他中心性指标进行评估的结果.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
计量
- 文章访问数: 7756
- PDF下载量: 656
- 被引次数: 0