Vital nodes identification in complex networks
arXiv:1607.01134 · doi:10.1016/j.physrep.2016.06.007
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 (124)
- Emergence of scaling in random networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- An index to quantify an individual's scientific research output
- Community detection in graphs
- Error and attack tolerance of complex networks
- Efficient Behavior of Small-World Networks
- Assortative mixing in networks
- The architecture of complex weighted networks
- The large-scale organization of metabolic networks
- The spread of epidemic disease on networks
- Identification of influential spreaders in complex networks
- Multilayer Networks
- Evolutionary games on graphs
- Temporal Networks
- Who is the best connected scientist? A study of scientific coauthorship networks
- Analysis of weighted networks
- Spatial Networks
- Resilience of the Internet to random breakdowns
- The Dynamics of Viral Marketing
- Cascade-based attacks on complex networks
- Attack vulnerability of complex networks
- Self-similarity of complex networks
- Breakdown of the Internet under intentional attack
- Structural Vulnerability of the North American Power Grid
- The Web of Human Sexual Contacts
- Subgraph Centrality in Complex Networks
- Influence maximization in complex networks through optimal percolation
- Universal Behavior of Load Distribution in Scale-free Networks
- Efficient Immunization Strategies for Computer Networks and Populations
- How to project a bipartite network?
- Mitigation of Malicious Attacks on Networks
- Detecting rich-club ordering in complex networks
- Recommender Systems
- Solving the apparent diversity-accuracy dilemma of recommender systems
- Does the h-index have predictive power?
- Epidemics and percolation in small-world networks
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- 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
- The Bethe lattice spin glass revisited
- Cascade control and defense in complex networks
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Thresholds for epidemic spreading in networks
- k-core organization of complex networks
- Voter Model on Heterogeneous Graphs
- Spectral redemption: clustering sparse networks
- Efficient routing on complex networks
- The Rich-Club Phenomenon In The Internet Topology
- The Dynamics of Protest Recruitment through an Online Network
- Universal behavior in a generalized model of contagion
- Statistical Analysis of Airport Network of China
- Finding Scientific Gems with Google
- Ranking spreaders by decomposing complex networks
- Journal Status
- Ising Model on Networks with an Arbitrary Distribution of Connections
- Characterization and Modeling of weighted networks
- A message passing approach for general epidemic models
- Searching for superspreaders of information in real-world social media
- Epidemic threshold in structured scale-free networks
- Optimization with Extremal Dynamics
- Diffusion of scientific credits and the ranking of scientists
- Localization and centrality in networks
- A k-shell decomposition method for weighted networks
- Resilience to damage of graphs with degree correlations
- Characterizing the dynamical importance of network nodes and links
- Ranking the spreading influence in complex networks
- Synchronization is optimal in non-diagonalizable networks
- Spreading dynamics in complex networks
- Absence of influential spreaders in rumor dynamics
- Identifying Influential Spreaders by Weighted LeaderRank
- General Dynamics of Topology and Traffic on Weighted Technological Networks
- Ranking Scientific Publications Using a Simple Model of Network Traffic
- Spectral Measures of Bipartivity in Complex Networks
- Bayesian inference of epidemics on networks via Belief Propagation
- Epidemic spreading on heterogeneous networks with identical infectivity
- Epidemic spread in weighted scale-free networks
- Small world yields the most effective information spreading
- Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
- Collective credit allocation in science
- A measure of individual role in collective dynamics
- Who is the best player ever? A complex network analysis of the history of professional tennis
- Google matrix analysis of directed networks
- 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
- Finding undetected protein associations in cell signaling by belief propagation
- On network bipartivity
- Lobby index in networks
- Empirical analysis of web-based user-object bipartite networks
- Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
- Global efficiency of local immunization on complex networks
- Information filtering via Iterative Refinement
- Quantifying the influence of scientists and their publications: Distinguish prestige from popularity
- Synchronization in large directed networks of coupled phase oscillators
- Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
- Spin glass approach to the feedback vertex set problem
- Optimizing spread dynamics on graphs by message passing
- A robust ranking algorithm to spamming
- Efficient routing strategies in scale-free networks with limited bandwidth
- Identifying effective multiple spreaders by coloring complex networks
- Geographical Coarsegraining of Complex Networks
- Ranking users, papers and authors in online scientific communities
- Spatial Structure of the Internet Traffic
- Reinforcement-Driven Spread of Innovations and Fads
- The role of clustering and gridlike ordering in epidemic spreading
- Large deviations of cascade processes on graphs
- Statistical Mechanics of Steiner trees
- Group-based ranking method for online rating systems with spamming attacks
- Statistical Mechanics of the Minimum Dominating Set Problem
- Epidemic centrality - is there an underestimated epidemic impact of network peripheral nodes?
- Self-organized Boolean game on networks
- Comment on ``Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality"
- Network Marketing on a Small-World Network
- Credit Default Swaps Drawup Networks: Too Tied To Be Stable?
- Nodes having a major influence to break cooperation define a novel centrality measure: game centrality
- Impact of individual nodes in Boolean network dynamics
- Solving the undirected feedback vertex set problem by local search
- Finding influential spreaders from human activity beyond network location
- Synchronization on Effective Networks
- Graph Partitioning Induced Phase Transitions
Cited by in corpus (118)
- Random walks and diffusion on networks
- Percolation on complex networks: Theory and application
- Coevolution spreading in complex networks
- Nestedness in complex networks: Observation, emergence, and implications
- Generalized Network Dismantling
- Ranking in evolving complex networks
- On community structure in complex networks: challenges and opportunities
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- Link prediction via linear optimization
- Centrality in Modular Networks
- Estimation of Regional Economic Development Indicator from Transportation Network Analytics
- M-Centrality: identifying key nodes based on global position and local degree variation
- Early identification of important patents through network centrality
- Centrality-based identification of important edges in complex networks
- Leveraging local h-index to identify and rank influential spreaders in networks
- Fast influencers in complex networks
- Cost-efficient vaccination protocols for network epidemiology
- Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
- Vector Centrality in Hypergraphs
- Identifying influential nodes based on fuzzy local dimension in complex networks
- Comparative evaluation of community-aware centrality measures
- Interacting discovery processes on complex networks
- Totally Homogeneous Networks
- Three faces of node importance in network epidemiology: Exact results for small graphs
- Revealing spatial spillover effect in high-tech industry agglomeration from a high-skilled labor flow network perspective
- Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
- Measuring Road Network Topology Vulnerability by Ricci Curvature
- Fundamental difference between superblockers and superspreaders in networks
- Current Flow Group Closeness Centrality for Complex Networks
- A message-passing approach to epidemic tracing and mitigation with apps
- Spectral dimension reduction of complex dynamical networks
- Systematic comparison between methods for the detection of influential spreaders in complex networks
- Spatial super-spreaders and super-susceptibles in human movement networks
- Interplay Between Hierarchy and Centrality in Complex Networks
- Message-passing theory for cooperative epidemics
- Beyond ranking nodes: Predicting epidemic outbreak sizes by network centralities
- Emergence of Hierarchy in Networked Endorsement Dynamics
- Influence Maximization in Social Networks: A Survey of Behaviour-Aware Methods
- Optimal interlayer structure for promoting spreading of SIS model in two-layer networks
- Top influencers can be identified universally by combining classical centralities
- A general centrality framework based on node navigability
- Underestimated cost of targeted attacks on complex networks
- Random walks on complex networks with first-passage resetting
- Identifying significant edges via neighborhood information
- Identifying vital nodes by Achlioptas process
- Random walks on complex networks under node-dependent stochastic resetting
- Temporal Gravity Model for Important Nodes Identification in Temporal Networks
- Centrally Administered State-Owned Enterprises' Engagement in China's Public-Private Partnerships: A Social Network Analysis
- Containing misinformation spreading in temporal social networks
- Impacts of Opinion Leaders on Social Contagions
- Influence maximization on temporal networks
- Random walks on complex networks under time-dependent stochastic resetting
- Beyond network centrality: Individual-level behavioral traits for predicting information superspreaders in social media
- History-dependent percolation on multiplex networks
- Topological structure and the H-index in complex networks
- Influential spreaders for recurrent epidemics on networks
- A centrality measure for quantifying spread on weighted, directed networks
- Simple bots breed social punishment in humans
- Randomizing growing networks with a time-respecting null model
- Identifying edges that facilitate the generation of extreme events in networked dynamical systems
- Influencers identification in complex networks through reaction-diffusion dynamics
- Percolation Framework of the Earth's Topography
- Network Alignment
- A Network Science perspective of Graph Convolutional Networks: A survey
- Lower bound of assortativity coefficient in scale-free networks
- Forecasting countries' gross domestic product from patent data
- Targeted influence maximization in complex networks
- Modelling Competitive marketing strategies in Social Networks
- The long-term impact of ranking algorithms in growing networks
- Ranking influential spreaders is an ill-defined problem
- Random walks on complex networks with multiple resetting nodes: a renewal approach
- Network connectivity under a probabilistic node failure model
- Dynamic range maximization in excitable networks
- Optimal networks for dynamical spreading
- Two-stage Information Spreading Evolution on The Control Role of Announcements
- Network-based ranking in social systems: three challenges
- From spatio-temporal data to chronological networks: An application to wildfire analysis
- Influence Maximization for Fixed Heterogeneous Thresholds
- Containing rumors spreading on correlated multiplex networks
- Regional economic status inference from information flow and talent mobility
- Fast asynchronous updating algorithms for k-shell indices
- Minimum Long-Loop Feedback Vertex Set and Network Dismantling
- Effect of network clustering on mutually cooperative coinfections
- Collective dynamics behind success
- Critical behaviors of high-degree adaptive and collective-influence percolation
- Effective submodularity of influence maximization on temporal networks
- The optimal edge for containing the spreading of SIS model
- Investigating Centrality Measures in Social Networks with Community Structure
- Identifying Influential Brokers on Social Media from Social Network Structure
- Comparing Community-aware Centrality Measures in Online Social Networks
- Dismantling Efficiency and Network Fractality
- Identifying Influential Nodes Using Overlapping Modularity Vitality
- A novel similarity measure for mining missing links in long-path networks
- The Bow-Tie Centrality: A Novel Measure for Directed and Weighted Networks with an Intrinsic Node Property
- Weighted cycle-based identification of influential node groups in complex networks
- Impact of shocks to economies on the efficiency and robustness of the international pesticide trade networks
- Optimizing spreading dynamics in interconnected networks
- Spin-glass model for the C-dismantling problem
- Model-free hidden geometry of complex networks
- Who is the best coach of all time? A network-based assessment of the career performance of professional sports coaches
- A sampling-guided unsupervised learning method to capture percolation in complex networks
- Economy importance and structural robustness of the international pesticide trade networks
- Predicting Nodal Influence via Local Iterative Metrics
- Power Network Uniqueness and Synchronization Stability from a Higher-order Structure Perspective
- Potential gain as a centrality measure
- How Correlated are Community-aware and Classical Centrality Measures in Complex Networks?
- Improving the performance of reputation evaluating by combining the structure of network and nonlinear recovery
- Influence of individual nodes for continuous-time Susceptible-Infected-Susceptible dynamics on synthetic and real-world networks
- K-core attack, equilibrium K-core, and kinetically constrained spin system
- How to choose the most appropriate centrality measure? A decision tree approach
- Network Diffusion -- Framework to Simulate Spreading Processes in Complex Networks
- Non-equilibrium random walks on multiplex networks
- The role of susceptible individuals in spreading dynamics
- Controlling centrality: The Inverse ranking problem for spectral centralities of complex networks
- Integrating behavioral experimental findings into dynamical models to inform social change interventions
- Influence Prediction in Collaboration Networks: An Empirical Study on arXiv
- Impacts of bridging nodes on the epidemic activation mechanisms
- Multiplex mobility network and metapopulation epidemic simulations of Italy based on Open Data