logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENTIA SINICA Informationis
Download PDF
SCIENTIA SINICA Informationis, Volume 49 , Issue 10 : 1333-1342(2019) https://doi.org/10.1360/N112019-00041

A novel method to identify multiple influential nodes in complex networks

Mingyang ZHOU 1,2, Xiangyang WU 2, Yang CAO 1, Liao LUO 1, Xiaoyu LI 2, Hao LIAO 1,2,*, Binghong WANG 3
More info
  • ReceivedFeb 21, 2019
  • AcceptedApr 25, 2019
  • PublishedOct 17, 2019
Previous Table of Contents Next
Share
Rating

Abstract


References

[1] Wang X F, Li X, Chen G R. Network Science: An Introduction. Beijing: Higher Education Press, 2012. Google Scholar

[2] Boccaletti S, Latora V, Moreno Y. Complex networks: Structure and dynamics. Phys Rep, 2006, 424: 175-308 CrossRef ADS Google Scholar

[3] Liu Y Y, Barabási A L. Control principles of complex systems. Rev Mod Phys, 2016, 88: 035006 CrossRef ADS arXiv Google Scholar

[4] Lü L, Chen D, Ren X L. Vital nodes identification in complex networks. Phys Rep, 2016, 650: 1-63 CrossRef ADS arXiv Google Scholar

[5] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003. 137--146. Google Scholar

[6] Nowzari C, Preciado V M, Pappas G J. Analysis and Control of Epidemics: A Survey of Spreading Processes on Complex Networks. IEEE Control Syst, 2016, 36: 26-46 CrossRef Google Scholar

[7] Liao H, Mariani M S, Medo M. Ranking in evolving complex networks. Phys Rep, 2017, 689: 1-54 CrossRef ADS arXiv Google Scholar

[8] Morone F, Makse H A. Influence maximization in complex networks through optimal percolation. Nature, 2015, 524: 65-68 CrossRef PubMed ADS arXiv Google Scholar

[9] Goyal A, Lu W, Lakshmanan L V. SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: Proceedings of the 11th International Conference on Data Mining, 2011. 211--220. Google Scholar

[10] Zhang Z K, Liu C, Zhan X X. Dynamics of information diffusion and its applications on complex networks. Phys Rep, 2016, 651: 1-34 CrossRef ADS Google Scholar

[11] Kitsak M, Gallos L K, Havlin S. Identification of influential spreaders in complex networks. Nat Phys, 2010, 6: 888-893 CrossRef ADS arXiv Google Scholar

[12] Szolnoki A, Perc M. Collective influence in evolutionary social dilemmas. EPL, 2016, 113: 58004 CrossRef ADS arXiv Google Scholar

[13] Liu Y, Tang M, Zhou T. Identify influential spreaders in complex networks, the role of neighborhood. Physica A-Statistical Mech its Appl, 2016, 452: 289-298 CrossRef ADS arXiv Google Scholar

[14] Zhou M Y, Xiong W M, Wu X Y. Overlapping influence inspires the selection of multiple spreaders in complex networks. Physica A-Statistical Mech its Appl, 2018, 508: 76-83 CrossRef ADS Google Scholar

[15] Zdeborová L, Krzakala F. Statistical physics of inference: thresholds and algorithms. Adv Phys, 2016, 65: 453-552 CrossRef Google Scholar

[16] Wang W, Tang M, Eugene Stanley H. Unification of theoretical approaches for epidemic spreading on complex networks. Rep Prog Phys, 2017, 80: 036603 CrossRef PubMed ADS arXiv Google Scholar

[17] Pastor-Satorras R, Vespignani A. Epidemic dynamics and endemic states in complex networks. Phys Rev E, 2001, 63: 066117 CrossRef PubMed ADS Google Scholar

[18] Zhou M Y, Xiong W M, Liao H. Analytical connection between thresholds and immunization strategies of SIS model in random networks.. Chaos, 2018, 28: 051101 CrossRef PubMed Google Scholar

[19] Chakrabarti D, Wang Y, Wang C. Epidemic thresholds in real networks. ACM Trans Inf Syst Secur, 2008, 10: 1-26 CrossRef Google Scholar

[20] Lu W, Li X, Rong Z. Global stabilization of complex networks with digraph topologies via a local pinning algorithm. Automatica, 2010, 46: 116-121 CrossRef Google Scholar

[21] Rong Z H, Li X, Lu W L. Pinning a complex network through the betweenness centrality strategy. In: Proceedings of IEEE International Symposium on Circuits and Systems, 2009. 1689--1692. Google Scholar

[22] Moradi Amani A, Jalili M, Yu X. Finding the Most Influential Nodes in Pinning Controllability of Complex Networks. IEEE Trans Circuits Syst II, 2017, 64: 685-689 CrossRef Google Scholar

[23] Pastor-Satorras R, Vespignani A. Epidemic Spreading in Scale-Free Networks. Phys Rev Lett, 2001, 86: 3200-3203 CrossRef PubMed ADS Google Scholar

[24] Parlett B N. The Rayleigh Quotient Iteration and Some Generalizations for Nonnormal Matrices. Math Computation, 1974, 28: 679 CrossRef Google Scholar

[25] Sarkar C, Jalan S. Spectral properties of complex networks. Chaos, 2018, 28: 102101 CrossRef PubMed ADS arXiv Google Scholar

[26] Bonacich P. Some unique properties of eigenvector centrality. Social Networks, 2007, 29: 555-564 CrossRef Google Scholar

[27] Restrepo J G, Ott E, Hunt B R. Approximating the largest eigenvalue of network adjacency matrices. Phys Rev E, 2007, 76: 056119 CrossRef PubMed ADS arXiv Google Scholar

[28] Krzakala F, Moore C, Mossel E. Spectral redemption in clustering sparse networks. Proc Natl Acad Sci USA, 2013, 110: 20935-20940 CrossRef PubMed ADS arXiv Google Scholar

[29] Leskovec J, Krevl A. SNAP datasets: Stanford large network dataset collection. 2014. Google Scholar

[30] Anonymous. The Koblenz network collection. 2016. Google Scholar

  • Click to view Download high-quality image

    Figure 1

    (Color online) Comparison of the information spread in networks with loops. (a) An artificial network; (b) the back tracking edge (red) that is neglected in Eq. (7); (c) the back path of the information spread in networks with loops.

  • Click to view Download high-quality image

    Figure 2

    (Color online) The principle eigenvalues of the remaining networks that are obtained by removing the edges attached to the influential nodes. (a) Airtraffic network; (b) Bitcoin network; (c) ca-HepTh network; (d) Reactome network.

  • Click to view Download high-quality image

    Figure 3

    (Color online) The evolving paths of the spread as a function of time. In the experiments, every node has a probability of 0.001 to be an infected node initially. The results are the average of 50 independent simulations. (a) Airtraffic network; (b) Bitcoin network; (c) ca-HepTh network; (d) Reactome network.

  • Click to view Download high-quality image

    Figure 4

    (Color online) The average distance between influential nodes. (a) Airtraffic network; (b) Bitcoin network;protect łinebreak (c) ca-HepTh network; (d) Reactome network.

  • Table 1   Structural properties of the different real networks, including network size ($N$), link number ($E$),degree heterogeneity ($H~=~\langle~k^2~\rangle/\langle~k~\rangle^2$), degree assortativity ($r$), average clustering coefficient ($\langle~C~\rangle$), average shortest path length ($\langle~d~\rangle$) and sparsity
    Network $N$ $E$ $H$ $r$ $\langle~C~\rangle$ $\langle~d~\rangle$ Sparsity
    Airtraffic 1225 2399 1.87 $-$0.0177 0.011 5.93 $3.2\times10^{-3}$
    Bitcoin 5880 21228 10.89 $-$0.163 0.022 3.59 $1.2\times10^{-3}$
    ca-HepTh 5039 11346 2.03 0.195 0.101 6.54 $8.9\times10^{-4}$
    Reactome 3851 140106 1.99 0.316 0.508 0.508 $1.9\times10^{-2}$
  •   

    Algorithm 1 The pseudo code to compute the set of influential nodes

    Require:The adjacent matrix $A=(a_{ij})_{N\times~N}$ and the size of influential nodes $L$.

    Data preparation. Extract the giant component of the original network and remove the isolate nodes and other small nodes clusters because nodes located in distinct clusters could not exchange information.

    Initialize the algorithm and calculate the importance of nodes based on Eq. (7).

    Rank nodes based on the importance of nodes and choose the particular node with the largest importance score.

    If the size of influential nodes is smaller than $L$, remove the edges attached to the influential nodes and go to step 2; otherwise go to step 5.

    Return the index of the chosen influential nodes.Output: The index of the selected influential nodes.