基于标签传播动力学提出了一种识别网络关键节点的算法,主要思想是把每个节点接收到不同标签的数量作为判断节点重要性的指标。应用两种不同的传播模型,在不同网络上与其它中心性指标作比较。结果表明:基于标签传播的中心性指标比其它的中心性方法可以更好地识别网络中的关键节点。基于标签传播的中心性指标还具有以下优势:不需要利用网络的结构信息,因此可以推广到大规模网络上;揭示了一种现象——好的接收者往往也是好的传播者。
In this paper, based on the label spreading dynamics, we propose a centrality index to identify influential nodes in complex networks, where the influence of a node is measured by how many different labels who have received. Under different spreading models, we compare our index with several traditional centrality indices in different networks, our results indicate that the performance of our index is better than others. Moreover, there are two typical advantages: 1), our algorithm does not use the structure information of networks, so which can be generalized to large-scale networks; 2), our algorithm implies a conclusion-a good receiver is also a good spreader.
[1] Newman M E J. Networks: an Introduction[M].Oxford: Oxford University Press, 2010.
[2] 吕琳媛, 陆君安, 张子柯, 等. 复杂网络观察[J].复杂系统与复杂性科学, 2010, 7(2): 173-186.
Lü LinYuan, Lu JunAn, Zhang ZiKe, et al. Looking into complex networks[J].Complex Systems and Complexity Science, 2010, 7(2): 173-186.
[3] 刘建国,任卓明,郭强,等.复杂网络中节点重要性排序的研究进展[J].物理学报,2013,62(17):178901.
Liu JianGuo, Ren ZhuoMing, Guo Qiang, et al. Node importance ranking of complex networks[J].Acta Phys Sin, 2013, 62(17): 178901.
[4] 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014, 59(13):1175-1197.
Ren XiaoLong, Lü Lin Yuan. Review of ranking nodes in complex networks[J].Chin Sci Bull (Chin Ver), 2014, 59: 1175-1197.
[5] Lü L Y, Chen D B, Ren X L, et al. Vital nodes identification in complex networks[J].Physics Reports, 2016, 650: 1-63.
[6] Bonacich P. Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972, 2(1): 113-120.
[7] Freeman L C. A set of measures of centrality based on betweenness[J].Sociometry, 1977, 40: 35-41.
[8] Freeman L C. Centrality in social networks conceptual clarification[J].Soc Netw, 1979, 1: 215-239.
[9] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J].Nat Phys, 2010, 6: 888-893.
[10] Chen D B, Lü L, Shang M S, et al. Identifying influential nodes in complex networks[J].Physica A, 2012, 391: 1777-1787.
[11] Ma L L, Ma C, Zhang H F, et al. Identifying influential spreaders in complex networks based on gravity formula[J].Physica A, 2016, 45: 1205-1212.
[12] Liu Y, Tang M, Zhou T, et al. Improving the accuracy of the k-shell method by removing redundant links: from a perspective of spreading dynamics[J].Scientific Reports, 2015, 5: 13172.
[13] Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J].Physics Letters A, 2013, 377(14): 1031-1035.
[14] 舒盼盼, 王伟, 唐明, 等. 花簇分形无标度网络中节点影响力的区分度[J].物理学报, 2015, 64(20): 208901.
Shu Panpan, Wang Wei, Tang Ming, et al. Discriminability of node influence in flower fractal scale-free networks[J].Acta Physica Sinica, 2015, 64(20): 208901.
[15] Kai Z, Lei Y. Information source detection in the SIR model: a sample path based approach[J].IEEE/ACM Transactions on Networking, 2016, 24(1): 408-421.
[16] Liao H, Zeng A. Reconstructing propagation networks with temporal similarity[J].Scientific Reports, 2015, 5: 11404.
[17] 李睿琪,王伟,舒盼盼, 等. 复杂网络上流行病传播动力学的爆发阈值解析综述[J].复杂系统与复杂性科学, 2016, 13(1): 1-39.
Li RuiQi, Wang Wei, Shu PanPan, et al. Review of threshold theoretical analysis about epidemic spreading dynamics on complex networks[J].Complex Systems and Complexity Science, 2016, 13(1): 1-39.
[18] Borge-Holthoefer Y, Moreno Y. Absence of influential spreaders in rumor dynamics[J].Physical Review E, 2012, 85(2): 026116.
[19] Zhou T, Lü L Y, Zhang Y C. Predicting missing links via local Information[J].The European Physical Journal B, 2009, 71(4): 623-630.
[20] 吕琳媛,周涛. 链路预测[M].上海:高等教育出版社,2014.
[21] Erdos P, Renyi A. On the evolution of random graphs[J].Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 1960, 5: 17-61.
[22] Barabasi A L, Albert R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.
