Vital nodes identification in complex networks

Abstract

Real networks exhibit heterogeneous nature with nodes playing far different roles in structure and function. To identify vital nodes is thus very significant, allowing us to control the outbreak of epidemics, to conduct advertisements for e-commercial products, to predict popular scientific publications, and so on. The vital nodes identification attracts increasing attentions from both computer science and physical societies, with algorithms ranging from simply counting the immediate neighbors to complicated machine learning and message passing approaches. In this review, we clarify the concepts and metrics, classify the problems and methods, as well as review the important progresses and describe the state of the art. Furthermore, we provide extensive empirical analyses to compare well-known methods on disparate real networks, and highlight the future directions. In despite of the emphasis on physics-rooted approaches, the unification of the language and comparison with cross-domain methods would trigger interdisciplinary solutions in the near future.

121Pages, 20 figures

References in corpus (44)

• Evolutionary games on graphs
• Efficient Immunization Strategies for Computer Networks and Populations
• Mitigation of Malicious Attacks on Networks
• Does the h-index have predictive power?
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Leaders in Social Networks, the Delicious Case
• Induced fit, conformational selection and independent dynamic segments: an extended view of binding events
• Cascade control and defense in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• Thresholds for epidemic spreading in networks
• Efficient routing on complex networks
• The Rich-Club Phenomenon In The Internet Topology
• Finding Scientific Gems with Google
• Ranking spreaders by decomposing complex networks
• A message passing approach for general epidemic models
• Searching for superspreaders of information in real-world social media
• Diffusion of scientific credits and the ranking of scientists
• A k-shell decomposition method for weighted networks
• Characterizing the dynamical importance of network nodes and links
• Ranking the spreading influence in complex networks
• Synchronization is optimal in non-diagonalizable networks
• Ranking Scientific Publications Using a Simple Model of Network Traffic
• Epidemic spreading on heterogeneous networks with identical infectivity
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Collective credit allocation in science
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Maximum Performance at Minimum Cost in Network Synchronization
• Epidemic spreading on complex networks with general degree and weight distributions
• Spectral coarse-graining of complex networks
• Communicability Betweenness in Complex Networks
• On network bipartivity
• Finding undetected protein associations in cell signaling by belief propagation
• Lobby index in networks
• Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
• Information filtering via Iterative Refinement
• Identifying effective multiple spreaders by coloring complex networks
• Geographical Coarsegraining of Complex Networks
• The role of clustering and gridlike ordering in epidemic spreading
• Statistical Mechanics of Steiner trees
• Group-based ranking method for online rating systems with spamming attacks
• Statistical Mechanics of the Minimum Dominating Set Problem
• Self-organized Boolean game on networks
• Solving the undirected feedback vertex set problem by local search
• Graph Partitioning Induced Phase Transitions

Cited by in corpus (6)

• Three faces of node importance in network epidemiology: Exact results for small graphs
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Fundamental difference between superblockers and superspreaders in networks
• Underestimated cost of targeted attacks on complex networks
• Topological structure and the H-index in complex networks
• Dynamic range maximization in excitable networks