Identification of influential spreaders in complex networks

2010/01/28 by Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin +5 · 1 voice · 3,219 citations
Physics and Astronomy · Social Sciences · #Betweenness centrality #Biology #Centrality #Complex Network Analysis Techniques #Complex network #Computer science #Core (optical fiber) #Data science #Ecology #Evolutionary Game Theory and Cooperation #Identification (biology) #Multitude #Network analysis #Opinion Dynamics and Social Influence #Physics #Social media #Social network analysis #Telecommunications #Theoretical computer science #World Wide Web #physics.soc-ph

paper · pdf · doi:10.1038/nphys1746

published in Nature Physics 6(11), 888-893 (Nature Portfolio) · 36 pages, 20 figures

openalex publication_date 2010/08/29 · arxiv created 2011/10/04 · arxiv updated 2015/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society. Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, the most influential spreaders in a social network do not correspond to the best connected people or to the most central people (high betweenness centrality). Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extend of the spreading. Furthermore, we find that-- in the case of infections that do not confer immunity on recovered individuals-- the infection persists in the high k-shell layers of the network under conditions where hubs may not be able to preserve the infection. Our analysis provides a plausible route for an optimal design of efficient dissemination strategies.

Citations

• Error and attack tolerance of complex networks
• The Mathematics of Infectious Diseases

Cited by

• Detecting bias in algorithms used to disseminate information in social networks and mitigating it using multiobjective optimization
• Node importance estimation in complex networks based on entropic Modularity-Perturbed gravity model
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• How does stock market reflect the change in economic demand? A study on the industry-specific volatility spillover networks of China's stock market during the outbreak of COVID-19
• Graph eigenvectors, fundamental weights and centrality metrics for nodes in networks
• Centrality Measures in Complex Networks: A Survey
• Towards the cycle structures in complex network: A new perspective
• Maximizing spreading in complex networks with risk in node activation
• Maximizing spreading influence via measuring influence overlap for social networks
• SSCF-CD: structural-similarity based core-first label propagation community detection
• Core language brain network for fMRI-language task used in clinical applications
• Competitive Dynamics on Complex Networks
• Node Immunization with Non-backtracking Eigenvalues
• Empirical determination of the optimum attack for fragmentation of modular networks
• Spreaders in the Network SIR Model: An Empirical Study
• Identifying influential nodes in complex networks: Effective distance gravity model
• α-Indirect Control in Onion-like Networks
• A Graph-Neural-Network-Entropy model of vital node identification on network attack and propagation
• Computational Socioeconomics
• Characterizing cycle structure in complex networks
• Group interactions modulate critical mass dynamics in social convention
• A key node identification method based on neighborhood-derived cluster method
• A General Framework for Complex Network Applications
• Weighted H-index for identifying influential spreaders
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
• Social Resilience in Online Communities: The Autopsy of Friendster
• An Efficient Network-aware Direct Search Method for Influence Maximization
• Evaluating the performance of geographical locations in scientific networks with an aggregation - randomization - re-sampling approach (ARR)
• Linking Multi-Site Sex Ad Data at the Individual Level to Aid Counter-Trafficking Efforts
• Identify influential nodes in directed networks: A neighborhood entropy-based method
• Model of Opinion Spreading in Social Networks
• Control contribution identifies top driver nodes in complex networks
• Computational Human Dynamics
• The Robustness of Graph k-shell Structure under Adversarial Attacks
• Latent Viral Marketing, Concepts and Control Methods
• Dissecting the Meme Magic: Understanding Indicators of Virality in Image Memes
• WEM: A Node Importance Algorithm in Weighted Networks
• Dynamics of information diffusion and its applications on complex networks
• Coevolution spreading in complex networks
• Growth-induced percolation on complex networks
• Dynamics of center-periphery patterns in knowledge networks - the case of China's biotech science and technology system
• Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applications
• Patterns, Models, and Challenges in Online Social Media: A Survey
• A universal assortativity measure for network analysis
• Assessing the Impact of Social Network Structure on the Diffusion of Coronavirus Disease (COVID-19): A Generalized Spatial SEIRD Model
• Predicting Critical Nodes in Temporal Networks by Dynamic Graph Convolutional Networks
• Calibratable Hetero-NodeRank for measuring node influence
• Practical and Accurate Local Edge Differentially Private Graph Algorithms
• On the Geometry and Extremal Properties of the Edge-Degeneracy Model
• Promotion and resignation in employee networks
• Machine learning applications in preventive healthcare: A systematic literature review on predictive analytics of disease comorbidity from multiple perspectives
• Beyond the Coverage of Information Spreading: Analytical and Empirical Evidence of Re-exposure in Large-scale Online Social Networks
• A heuristic optimization method for mitigating the impact of a virus attack
• Lowest Degree Decomposition of Complex Networks
• A combined network and machine learning approaches for product market forecasting
• Identifying and ranking influential spreaders in complex networks by neighborhood coreness
• Modeling Epidemic Spreading through Public Transit using Time-Varying Encounter Network
• Discussion of Parameters Setting for A Distributed Probabilistic Modeling Algorithm
• Surgical immunization strategies against lateral movement in Active Directory environments
• Enhancing speed of pinning synchronizability: low-degree nodes with high feedback gains
• K-Core Minimization: A Game Theoretic Approach
• The anatomy of urban social networks and its implications in the searchability problem
• On Rich Clubs of Path-Based Centralities in Networks
• A novel method based on node correlation to evaluate the important nodes in complex networks
• Inferring General Relations between Network Characteristics from Specific Network Ensembles
• Strategy to suppress epidemic explosion in heterogeneous metapopulation networks
• Studying information recurrence, gatekeeping, and the role of communities during internet outages in Venezuela
• Percolation on complex networks: Theory and application
• Ranking in interconnected multilayer networks reveals versatile nodes
• Interplay Between Hierarchy and Centrality in Complex Networks
• Efficient and trustworthy methods for knowledge discovery
• A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks
• Identifying Influential Nodes in Bipartite Networks Using the Clustering Coefficient
• Sufficient conditions of endemic threshold on metapopulation networks
• The Anatomy of a Scientific Rumor
• Dynamics of epidemic spreading with vaccination: Impact of social pressure and engagement
• The jamming transition is a k-core percolation transition
• The Message or the Messenger? Inferring Virality and Diffusion Structure from Online Petition Signature Data
• Tricritical Point in Heterogeneousk-Core Percolation
• Identifying influential spreaders by weighted LeaderRank
• Immunization strategies in networks with missing data
• Predicting epidemic outbreak from individual features of the spreaders
• Understanding the influence of all nodes in a network
• Consistency and differences between centrality measures across distinct classes of networks
• Computational models for commercial advertisements in social networks
• Towards User Engagement Dynamics in Social Networks
• The structured backbone of temporal social ties
• Identifying influential spreaders in complex networks based on gravity formula
• Influential spreaders for recurrent epidemics on networks
• Insights from graph theory on the morphologies of actomyosin networks with multilinkers
• Model-free hidden geometry of complex networks
• Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian
• Detection of core–periphery structure in networks using spectral methods and geodesic paths
• The core decomposition of networks: theory, algorithms and applications
• Rumor propagation with heterogeneous transmission in social networks
• Ranking the Importance of Nodes of Complex Networks by the Equivalence Classes Approach
• The k-core as a predictor of structural collapse in mutualistic ecosystems
• Personal vs. know-how contacts: which matter more in wiki elections?
• Ranking of critical species to preserve the functionality of mutualistic networks using the k -core decomposition
• Network-based ranking in social systems: three challenges
• Impact of network assortativity on epidemic and vaccination behaviour

Discussions

• Identifying influential spreaders in complex networks [hn, 16 points, 2 comments]

Related

• Maximizing spreading in complex networks with risk in node activation
• The role of centrality for the identification of influential spreaders in complex networks
• The role of susceptible individuals in spreading dynamics
• Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition
• Spreaders in the Network SIR Model: An Empirical Study