An evaluation method of critical nodes in complex network based on accurate k-shell

Abstract

Abstract: Critical nodes are the core elements of complex networks and can play a critical role in maintaining structural stability and information transmission. The k-shell is a common measure index of node importance. But due to its shortcomings such as destroying the overall structure information of the network and ignoring the influence of neighboring nodes, it is difficult to ensure that each node can be quantitatively distinguished. In order to improve the accuracy of node identification, this paper firstly improves the decomposition process of k-shell and proposes the Ak (accurate k-shell). Considering the influence of local feature information and global structure information on nodes in the network, the Ak is applied to the gravity centrality and the AGC (accurate gravity centrality) is proposed, subsequently. Because of the good expansibility for Shannon entropy in informatics has good expansibility in the identification of key nodes in the network,the MC (mixed centrality) is finally proposed to evaluate the importance of nodes pluralistically by combining Shannon entropy of neighborhood centrality, neighborhood Ak and AGC. Under 7 kinds of real networks, a series of experiments on the monotonicity and accuracy of MC and other node evaluation indexes in terms of monotonicity and accuracy were conducted. The experimental results show that MC has better performance in identifying key nodes.

Key words: complex network, k-shell decomposition method, accurate k-shell, mixed centrality, node importance

CLC Number:

TP393

LU Peng-li, XU Xing-zhou. An evaluation method of critical nodes in complex network based on accurate k-shell[J]. Journal of Lanzhou University of Technology, 2022, 48(4): 90-98.

References

[1] ALBERT R.Emergence of scaling in random networks [J].Science,1999,286(5439):509-512.
[2] WASHIO T,MOTODA H.State of the art of graph-based data mining [J].ACM SIGKDDExplorations Newsletter,2003,5(1):59-68.
[3] ZHANG K,ZHUANG K C,TAN G X.Research review on invulnerability measure of complex network [J].Computer Era,2010,5:4-7.
[4] PAN X,LIM S.City-scale traffic estimation from a roving sensor network [J].Proceedings of the 10th ACM Conference on Embedded Network Sensor Systems,2012(10):141-154.
[5] VIDAL M,CUSICK M E,BARABASI A L.Interactome networks and human disease [J].Cell,2011,144(6):986-998.
[6] YANG B,LIU D,LIU J,et al.Complex network clustering algorithms [J].Journal of Software,2009,20(1):201-212.
[7] FREEMAN L C.Centrality in social networks conceptual clarification [J].Social Network,1978,1(3):215-239.
[8] FREEMAN L C.A set of measures of centrality based on betweenness [J].Sociometry,1977,40(1):35-41.
[9] KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks [J].Natural Physics,2010,6(11):888.
[10] LV L,ZHOU T,ZHANG Q M,et al.The H-index of a network node and its relation to degree and coreness [J].Nature Communication,2016,7:10168.
[11] ZHAO Y,LI S,JIN F.Identification of influential nodes in social networks with community structure based on label propagation [J].Neurocomputing,2016,210:34-44.
[12] WANG J,HOU X,LI K,et al.A novel weight neighborhood centrality algorithm for identifying influential spreaders in complex networks [J].Physica A:Statistical Mechanics and its Applications,2017,475:88-105.
[13] MA L L,MA C,ZHANG H F,et al.Identifying influential spreaders in complex networks based on gravity formula [J].Physica A,2016,451:205-212.
[14] 卢鹏丽,于洲.基于度与H指数扩展的复杂网络节点排序方法 [J]. 兰州理工大学学报,2020,46(5):106-112.
[15] WANG M,LI W C.Identifying influential spreaders in complex networks based on improved k-shell method [J].Physica A:Statistical Mechanics and its Applications,2020,554:124229.
[16] NIE T,GUO Z,ZHAO K.Using mapping entropy to identify node centrality in complex networks [J].Physica A,2016,453:290-297.
[17] LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations [J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[18] THOMAS E.Election 2004:how bush won and what you can expect in the future [J].Library Journal,2005,56(97):207-208.
[19] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].Proceedings of the National Academy Science of the United States of America,2002,99:7821-7826.
[20] GLEISER P M,DANON L.Community structure in jazz [J].Advances in Complex Systems,2003,6(4):565-573.
[21] BATAGELI V,MRVAR A.Ajek data sets [DB/OL].[2020-09-15].http://vladowiki.fmf.uni-lj.si/doku.php?id=pajek:data:pajek:vlado.
[22] GUIMERA R,DANON L,DIAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions [J].Physical Review E,2003,68:065103.
[23] Hamsterster full network dataset[DB/OL].[2020-09-15].http://konect.uni-koblenz.de/networks/petster-hamster.
[24] ZHOU J,CHUNG N N,CHEW L Y,et al.Epidemic spreading induced by diversity of agents’ mobility [J].Physical Review E,2012,86(2):026115.
[25] NEWMAN M E.Spread of epidemic disease on networks [J].Physical Review E,2002,66(1):016128.
[26] ZHOU T,LV L,ZHANG Y C.Predicting missing links via local information [J].Europen Physical Journal B,2009,71(4):623-630.
[27] KNIGHT W R.A computer method for calculating Kendall’s tau with ungrouped data [J].Journal of the American Statistical Association,1966,61(314):436-439.
[28] BAE J,KIM S.Identifying and ranking influential spreaders in complex networks by neighborhood coreness [J].Physica A:Statistical Mechanics and its Applications,2014,395:549-559.
[29] SHILGALIS T W.Cumulative distribution functions [J].Teaching Statistics,1988,10(3):82-86.
[30] JALILI M,PERC M.Information cascades in complex networks [J].Journal of Complex Networks,2017,5(5):665-693.
[31] BUSCARINO A,FORTUNA L,FRASCA M,et al.Disease spreading in populations of moving agents [J].Europhysics Letters,2008,82(3):38002.
[32] PASTOR-SATORRAS R,VESPIGNANI A.Epidemic dynamics and endemic states in complex networks [J].Physical Review E,2001,63(6):066117.