Computer Science ›› 2015, Vol. 42 ›› Issue (Z11): 296-300.

Previous Articles     Next Articles

Detecting Most Influential Nodes in Complex Networks by KSN Algorithm

TIAN Yan and LIU Zu-gen   

  • Online:2018-11-14 Published:2018-11-14

Abstract: It is very important in theory and practice to detect influential spreaders in networks accurately and efficiently.Recently,scholars from various fields have paid their attention to the study of ranking nodes.The K-shell index is a relatively powerful indicator to estimate the spreading ability of nodes.However,due to only attributes of the node itself being considered,limitation in accuracy and universal applicability will exist for K-shell decomposition.To solve this problem,this paper proposed a novel algorithm called KSN (the K-shell and neighborhood centrality) to estimate the spreading influence of a node by its K-shell value and the K-shell indexes of its nearest and next nearest neighbors.Experimental results demonstrate that this proposed algorithm acts more precisely in detecting the most influential nodes than degree centrality,betweenness centrality,K-shell decomposition and the mixed degree decomposition,et al.

Key words: Complex networks,Influential nodes,Centrality measure,KSN centrality

[1] 马杰良,宋艳,潘贞贞,等.图书漂流网络模型实证研究[J].计算机科学,2015,42(3):51-54
[2] 周涛,傅忠谦,牛永伟,等.复杂网络上传播动力学研究综述[J].自然科学进展,2005,5(5):513-523
[3] 李翔,刘宗华,汪秉宏.网络传播动力学[J].复杂系统与复杂性科学,2010,Z1:41-45
[4] Liu J G,Wang Z T,Dang Y Z.Optimization of scale-free network for random failures[J].Mod.Phys.Lett.B,2006,20:815-820
[5] Brummitt C D,D’Souza R M,Leicht E.Suppressing cascades of load in interdependent networks[J].Proc Natl Acad Sci USA,2012,109:E680-E689
[6] Burt R S,Minor M J,Alba R D.Applied network analysis:A methodological introduction[M].Sage Publications Beverly Hills,1983
[7] Sabidussi G.The centrality index of a graph[J].Psychometrika,1966,31:581-603
[8] Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry,1977, 40:35
[9] Yan G,Zhou T,Hu B,et al.Efficient routing on complex networks[J].Phys Rev E,2006,73:1-5
[10] Freeman L C.Centrality in social networks conceptual clarification[J].Soc Netw,1979,1:215-239
[11] Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nat Phys,2010,6:888-893
[12] Zeng A,Zhang C J.Ranking spreaders by decomposing complex networks[J].Phys.Lett.A,2013,377(14):1031-1035
[13] Liu J G,Ren Z M,Guo Q.Ranking the spreadinginfluencein complex networks[J].Physica A,2013,392:4154-4159
[14] Newman M E J.A measure of betweenness centrality based on random walks[J].Soc.Netw.,2005,27 (1):39-54
[15] Bonacich P.Factoring and weighting approaches to status scores and clique identification[J].J Math Sociol,1972,2:113-120
[16] Hethcote H W.The mathematics of infectious disease[J].Soc.Industr.Appl.Math,2000,42:599-653
[17] Blower S,Bernoulli D.An attempt at a new analysis of the mortality caused by smallpox and of the advantages of inoculation to prevent it[J].Rev.Med.Virol,2004,14:275-288
[18] Anderson R M,Robert M.Infectious Diseases of Humans:Dynamics and Control[M].New York:Oxford University Press,1992:66
[19] Diekmann O,Heesterbeek J A P.Mathematical Epidemiology of Infectious Diseases:Model Building,Analysis and Interpretation[M].New York:Wiley Series in Mathematical & Computational Biology,2001
[20] Kendall M.A new measure of rank correlation[J].Biometrika,1938,30:81-93
[21] Zachary W W.An information flow model for conflict and fission in small groups[J].J.Anthropol.Res.,1977,33:452-473
[22] Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Phys.Rev.E,2006,74 (3):036104
[23] Guimera R,Danon L,Diaz-Guilera A,et al.Self-similar community structure in a network of human interactions[J].Phys.Rev.E,2003,8:065103
[24] Xie N.Social network analysis of blogs[D].UK:University of Bristol,2006

No related articles found!
Full text



No Suggested Reading articles found!