A Novel Method Based on Node's Correlation to Evaluate Important Nodes in Complex Networks

doi:10.1007/s12204-021-2373-6

Abstract

Abstract: Finding the important nodes in complex networks by topological structure is of great significance to network invulnerability. Several centrality measures have been proposed recently to evaluate the performance of nodes based on their correlation, showing that the interaction between nodes has an influence on the importance of nodes. In this paper, a novel method based on node’s distribution and global influence in complex networks is proposed. The nodes in the complex networks are classified according to the distance matrix; then the correlation coefficient between pairs of nodes is calculated. From the whole perspective in the network, the global similarity centrality (GSC) is proposed based on the relevance and the shortest distance between any two nodes. The efficiency, accuracy, and monotonicity of the proposed method are analyzed in two artificial datasets and eight real datasets of different sizes. Experimental results show that the performance of GSC method outperforms those current state-of-the-art algorithms.

Key words: node importance, network topology, global similarity centrality (GSC), distribution vector, susceptible-infected-recovered (SIR) model

CLC Number:

TP273.3

LU Pengli1∗ (卢鹏丽), DONG Chen1,2 (董晨), GUO Yuhong3 (郭育红). A Novel Method Based on Node's Correlation to Evaluate Important Nodes in Complex Networks[J]. J Shanghai Jiaotong Univ Sci, 2022, 27(5): 688-698.

References 50

[1]	HEIDEMANN J, KLIER M, PROBST F. Online social networks: A survey of a global phenomenon [J]. Computer Networks, 2012, 56(18): 3866-3878.
[2]	BOZORGI A, HAGHIGHI H, SADEGH ZAHEDI M, et al. INCIM: A community-based algorithm for influence maximization problem under the linear threshold model [J]. Information Processing & Management, 2016, 52(6): 1188-1199.
[3]	CHEN W, WANG C, WANG Y J. Scalable influence maximization for prevalent viral marketing in large-scale social networks [C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining-KDD’10. Washington, DC, USA. New York: ACM Press, 2010: 1029-1038.
[4]	YU Z,WANG C, BU J J, et al. Friend recommendation with content spread enhancement in social networks [J]. Information Sciences, 2015, 309: 102-118.
[5]	SHEIKHAHMADI A, NEMATBAKHSH M A, SHOKROLLAHI A. Improving detection of influential nodes in complex networks [J]. Physica A: Statistical Mechanics and Its Applications, 2015, 436: 833-845. [6] SHEIKHAHMADI A, NEMATBAKHSH M A, ZAREIE A. Identification of influential users by neighbors in online social networks [J]. Physica A: Statistical Mechanics and Its Applications, 2017, 486: 517-534.
[7]	BOND R M, FARISS C J, JONES J J, et al. A 61- million-person experiment in social influence and political mobilization [J]. Nature, 2012, 489(7415): 295- 298.
[8]	ROSSI M E G, MALLIAROS F D, VAZIRGIANNIS M. Spread it good, spread it fast: Identification of influential nodes in social networks [C]//Proceedings of the 24th International Conference on World Wide Web. Florence Italy. New York, NY, USA: ACM, 2015: 101-102.
[9]	FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks, 1978, 1(3): 215-239.
[10]	FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35.
[11]	SABIDUSSI G. The centrality index of a graph [J]. Psychometrika, 1966, 31(4): 581-603.
[12]	KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks [J]. Nature Physics, 2010, 6(11): 888-893.
[13]	ZHAO Y X, LI S H, JIN F. Identification of influential nodes in social networks with community structure based on label propagation [J]. Neurocomputing, 2016, 210: 34-44.
[14]	PU J, CHEN X W, WEI D J, et al. Identifying influential nodes based on local dimension [J]. EPL(Europhysics Letters), 2014, 107(1): 10010.
[15]	L¨U L Y, ZHOU T, ZHANG Q M, et al. The H-index of a network node and its relation to degree and coreness [J]. Nature Communications, 2016, 7: 10168.
[16]	LIU Q, ZHU Y X, JIA Y, et al. Leveraging local hindex to identify and rank influential spreaders in networks [J]. Physica A: Statistical Mechanics and Its Applications, 2018, 512: 379-391.
[17]	LU P L, DONG C. Ranking the spreading influence of nodes in complex networks based on mixing degree centrality and local structure [J]. International Journal of Modern Physics B, 2019, 33(32): 1950395.
[18]	WANG J Y, HOU X N, LI K Z, 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.
[19]	ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks [J]. Physics Letters A, 2013, 377(14): 1031-1035.
[20]	QI X Q, FULLER E, WU Q, et al. Laplacian centrality: A new centrality measure for weighted networks [J]. Information Sciences, 2012, 194: 240-253.
[21]	MA Y, CAO Z L, QI X Q. Quasi-Laplacian centrality: A new vertex centrality measurement based on Quasi- Laplacian energy of networks [J]. Physica A: Statistical Mechanics and Its Applications, 2019, 527: 121130.
[22]	MA L L, MA C, ZHANG H F, et al. Identifying influential spreaders in complex networks based on gravity formula [J]. Physica A: Statistical Mechanics and Its Applications, 2016, 451: 205-212.
[23]	WANG J, LI C, XIA C Y. Improved centrality indicators to characterize the nodal spreading capability in complex networks [J]. Applied Mathematics and Computation, 2018, 334: 388-400.
[24]	NAMTIRTHA A, DUTTA A, DUTTA B. Identifying influential spreaders in complex networks based on kshell hybrid method [J]. Physica A: Statistical Mechanics and Its Applications, 2018, 499: 310-324.
[25]	NAMTIRTHA A, DUTTA A, DUTTA B. Weighted kshell degree neighborhood: A new method for identifying the influential spreaders from a variety of complex network connectivity structures [J]. Expert Systems With Applications, 2020, 139: 112859.
[26]	DAI Z, LI P, CHEN Y, et al. Influential node ranking via randomized spanning trees [J]. Physica A: Statistical Mechanics and Its Applications, 2019, 526: 120625.
[27]	QI X Q, FULLER E, LUO R, et al. A novel centrality method for weighted networks based on the Kirchhoff polynomial [J]. Pattern Recognition Letters, 2015, 58: 51-60.
[28]	SILVA F N, COSTA L D F. Local dimension of complex networks [EB/OL]. (2012-09-12). https://arxiv.org/abs/1209.2476.
[29]	BRIN S, PAGE L. The anatomy of a large-scale hypertextualWeb search engine [J]. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7): 107-117.
[30]	ZHANG X H, ZHU J, WANG Q, et al. Identifying influential nodes in complex networks with community structure [J]. Knowledge-Based Systems, 2013, 42: 74- 84.
[31]	ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[32]	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.
[33]	KARL H. Election 2004: How Bush won and what you can expect in the future [J]. Library Journal, 2005, 130(3): 147-148.
[34]	GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. PNAS, 2002, 99(12): 7821-7826.
[35]	GLEISER P M, DANON L. Community structure in jazz [J]. Advances in Complex Systems, 2003, 6(4): 565-573.
[36]	BATAGELJ V, MRVAR A. Pajek data sets [EB/OL]. [2020-07-07]. http://vlado.fmf.unilj. si/pub/networks/data/.
[37]	GUIMER`A R, DANON L, D′IAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions [J]. Physical Review E, 2003, 68: 065103.
[38]	JEONG H, MASON S P, BARAB′ASI A L, et al. Lethality and centrality in protein networks [J]. Nature, 2001, 411(6833): 41-42.
[39]	WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998, 393(6684): 440-442.
[40]	BAPAT R B, GUTMANA I, XIAO W J. A simple method for computing resistance distance [J]. Zeitschrift F¨ur Naturforschung A, 2003, 58(9/10): 494-498.
[41]	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.
[42]	SHILGALIS T W. Cumulative distribution functions [J]. Teaching Statistics, 1988, 10(3): 82-86.
[43]	ZHOU J, CHUNG N N, CHEW L Y, et al. Epidemic spreading induced by diversity of agents’ mobility [J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2012, 86: 026115.
[44]	NEWMAN M E J. Spread of epidemic disease on networks [J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2002, 66: 016128.
[45]	ZHOU T, L¨U L, ZHANG Y C. Predicting missing links via local information [J]. The European Physical Journal B, 2009, 71(4): 623-630.
[46]	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.
[47]	JALILI M, PERC M. Information cascades in complex networks [J]. Journal of Complex Networks, 2017, 5(5): 665-693.
[48]	BUSCARINO A, FORTUNA L, FRASCA M, et al. Disease spreading in populations of moving agents [J]. EPL (Europhysics Letters), 2008, 82(3): 38002.
[49]	PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics and endemic states in complex networks [J]. Physical Review E, 2001, 63(6): 066117.
[50]	ZHAO J,WANG Y C, DENG Y. Identifying influential nodes in complex networks from global perspective [J]. Chaos, Solitons & Fractals, 2020, 133: 109637.