Influence maximization in complex networks through optimal percolation
arXiv:1506.08326 · doi:10.1038/nature14604
Abstract
The whole frame of interconnections in complex networks hinges on a specific set of structural nodes, much smaller than the total size, which, if activated, would cause the spread of information to the whole network [1]; or, if immunized, would prevent the diffusion of a large scale epidemic [2,3]. Localizing this optimal, i.e. minimal, set of structural nodes, called influencers, is one of the most important problems in network science [4,5]. Despite the vast use of heuristic strategies to identify influential spreaders [6-14], the problem remains unsolved. Here, we map the problem onto optimal percolation in random networks to identify the minimal set of influencers, which arises by minimizing the energy of a many-body system, where the form of the interactions is fixed by the non-backtracking matrix [15] of the network. Big data analyses reveal that the set of optimal influencers is much smaller than the one predicted by previous heuristic centralities. Remarkably, a large number of previously neglected weakly-connected nodes emerges among the optimal influencers. These are topologically tagged as low-degree nodes surrounded by hierarchical coronas of hubs, and are uncovered only through the optimal collective interplay of all the influencers in the network. Eventually, the present theoretical framework may hold a larger degree of universality, being applicable to other hard optimization problems exhibiting a continuous transition from a known phase [16].
7 pages, 3 figures, Supplementary Information: 52 pages, 10 extended data figs
References in corpus (3)
Cited by in corpus (218)
- Vital nodes identification in complex networks
- Influence of fake news in Twitter during the 2016 US presidential election
- Random walks and diffusion on networks
- Robustness and resilience of complex networks
- Statistical physics of inference: Thresholds and algorithms
- Measuring user influence on Twitter: A survey
- Unification of theoretical approaches for epidemic spreading on complex networks
- Percolation on complex networks: Theory and application
- Network dismantling
- Coevolution spreading in complex networks
- Generalized Network Dismantling
- Ranking in evolving complex networks
- Explosive Phenomena in Complex Networks
- Identifying optimal targets of network attack by belief propagation
- Statistical physics approaches to the complex Earth system
- Identify influential spreaders in complex networks, the role of neighborhood
- Fast and simple decycling and dismantling of networks
- The k-core as a predictor of structural collapse in mutualistic ecosystems
- Machine learning dismantling and early-warning signals of disintegration in complex systems
- Immunization and targeted destruction of networks using explosive percolation
- Leaders should not be conformists in evolutionary social dilemmas
- A Survey on Centrality Metrics and Their Implications in Network Resilience
- Articulation Points in Complex Networks
- Shifting Polarization and Twitter News Influencers between two U.S. Presidential Elections
- Optimal percolation on multiplex networks
- Local structure can identify and quantify influential global spreaders in large scale social networks
- Computational Socioeconomics
- Finding influential nodes for integration in brain networks using optimal percolation theory
- Network science based quantification of resilience demonstrated on the Indian Railways Network
- Disrupting Resilient Criminal Networks through Data Analysis: The case of Sicilian Mafia
- Inferring Personal Economic Status from Social Network Location
- Collective influence in evolutionary social dilemmas
- Recent advances of percolation theory in complex networks
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
- Leveraging percolation theory to single out influential spreaders in networks
- M-Centrality: identifying key nodes based on global position and local degree variation
- The influence of the broadness of the degree distribution on network's robustness: comparing localized attack and random attack
- -core percolation on complex networks: Comparing random, localized and targeted attacks
- Stability of a Giant Connected Component in a Complex Network
- Fast influencers in complex networks
- Cost-efficient vaccination protocols for network epidemiology
- The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
- Climate network percolation reveals the expansion and weakening of the tropical component under global warming
- Rare events and discontinuous percolation transitions
- Efficient collective influence maximization in cascading processes with first-order transitions
- Beyond the locally tree-like approximation for percolation on real networks
- Strength of weak layers in cascading failures on multiplex networks: case of the international trade network
- Vector Centrality in Hypergraphs
- Model of Brain Activation Predicts the Neural Collective Influence Map of the Brain
- Identifying an influential spreader from a single seed in complex networks via a message-passing approach
- Fluctuations in percolation of sparse complex networks
- Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
- Data-driven strategies for optimal bicycle network growth
- Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
- Controlling the uncertain response of real multiplex networks to random damage
- Fundamental difference between superblockers and superspreaders in networks
- The localization of non-backtracking centrality in networks and its physical consequences
- The web of federal crimes in Brazil: topology, weaknesses, and control
- 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
- Optimal Allocation of Resources for Suppressing Epidemic Spreading on Networks
- Nonbacktracking expansion of finite graphs
- Efficient network immunization under limited knowledge
- Inequality and Inequity in Network-based Ranking and Recommendation Algorithms
- Optimal interlayer structure for promoting spreading of SIS model in two-layer networks
- Large deviation theory of percolation on multiplex networks
- Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
- Emergence of scale-free blackout sizes in power grids
- Targeted Damage to Interdependent Networks
- Underestimated cost of targeted attacks on complex networks
- Distance entropy cartography characterises centrality in complex networks
- Diverse types of percolation transitions
- Promoting information spreading by using contact memory
- Percolation on feature-enriched interconnected systems
- Identifying vital nodes by Achlioptas process
- Spreading dynamics of information on online social networks
- Superspreading k-cores at the center of COVID-19 pandemic persistence
- From degree-correlated to payoff-correlated activity for an optimal resolution of social dilemmas
- Why are there six degrees of separation in a social network?
- Group based Centrality for Immunization of Complex Networks
- On the topologic structure of economic complex networks: Empirical evidence from large scale payment network of Estonia
- The Unfolding and Control of Network Cascades
- Temporal Gravity Model for Important Nodes Identification in Temporal Networks
- Rumor propagation with heterogeneous transmission in social networks
- Pre-Training Graph Neural Networks for Generic Structural Feature Extraction
- Cascading collapse of online social networks
- Bistability and time crystals in long-ranged directed percolation
- Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
- Containing misinformation spreading in temporal social networks
- Heterogeneous micro-structure of percolation in sparse networks
- Correlated network of networks enhances robustness against catastrophic failures
- Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
- Influence maximization on temporal networks
- A centrality measure for quantifying spread on weighted, directed networks
- The wisdom of networks: A general adaptation and learning mechanism of complex systems: The network core triggers fast responses to known stimuli; innovations require the slow network periphery and are encoded by core-remodeling
- Influencers identification in complex networks through reaction-diffusion dynamics
- A Network Science perspective of Graph Convolutional Networks: A survey
- Percolation Framework of the Earth's Topography
- Modeling social resilience: Questions, answers, open problems
- Forecasting countries' gross domestic product from patent data
- The price of a vote: diseconomy in proportional elections
- Targeted influence maximization in complex networks
- The long-term impact of ranking algorithms in growing networks
- Ranking influential spreaders is an ill-defined problem
- Surges of collective human activity emerge from simple pairwise correlations
- Optimal percolation in correlated multilayer networks with overlap
- Color-avoiding percolation
- Probing Limits of Information Spread with Sequential Seeding
- Dynamic range maximization in excitable networks
- A new design principle of robust onion-like networks self-organized in growth
- Optimal redundancy against disjoint vulnerabilities in networks
- Localization, epidemic transitions, and unpredictability of multistrain epidemics with an underlying genotype network
- Network-based ranking in social systems: three challenges
- Rapid decay in the relative efficiency of quarantine to halt epidemics in networks
- Triadic percolation induces dynamical topological patterns in higher-order networks
- Modelling indirect interactions during failure spreading in a project activity network
- Influence Maximization for Fixed Heterogeneous Thresholds
- Extended-range percolation in complex networks
- Emergence of Robustness in Network of Networks
- Node Immunization with Non-backtracking Eigenvalues
- Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
- Controlling percolation with limited resources
- Deep-learning-aided dismantling of interdependent networks
- Spectral estimation of the percolation transition in clustered networks
- Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
- Optimal cost for strengthening or destroying a given network
- Optimal Stabilization of Boolean Networks through Collective Influence
- Multilayer modeling of adoption dynamics in energy demand management
- Fragmenting networks by targeting collective influencers at a mesoscopic level
- Towards Quantifying Sampling Bias in Network Inference
- Effects of Time Horizons on Influence Maximization in the Voter Dynamics
- Critical phenomena of a hybrid phase transition in cluster merging dynamics
- Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time
- Seeds Buffering for Information Spreading Processes
- The epidemiology of lateral movement: exposures and countermeasures with network contagion models
- Minimum Long-Loop Feedback Vertex Set and Network Dismantling
- Stochastic Dynamic Programming Heuristics for Influence Maximization-Revenue Optimization
- Rank the spreading influence of nodes using dynamic Markov process
- Targeted Recovery as an Effective Strategy against Epidemic Spreading
- The optimal edge for containing the spreading of SIS model
- Critical behaviors of high-degree adaptive and collective-influence percolation
- Effective submodularity of influence maximization on temporal networks
- Influence maximization in noisy networks
- Identifying Influential Brokers on Social Media from Social Network Structure
- Dismantling Efficiency and Network Fractality
- Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
- Colored Percolation
- Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks
- Centralities in complex networks
- Degree-targeted cascades in modular, degree-heterogeneous networks
- Bounding robustness in complex networks under topological changes through majorization techniques
- Performance of attack strategies on modular networks
- Weighted cycle-based identification of influential node groups in complex networks
- Influence Maximization: Divide and Conquer
- Controllability of the Voter Model: an information theoretic approach
- Computational Aspects of Optimal Strategic Network Diffusion
- Price graphs: Utilizing the structural information of financial time series for stock prediction
- Spin-glass model for the C-dismantling problem
- Observability transition in real networks
- Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
- Efficient network exploration by means of resetting self-avoiding random walkers
- Beyond the Coverage of Information Spreading: Analytical and Empirical Evidence of Re-exposure in Large-scale Online Social Networks
- Design of endurable networks in the presence of aging
- Vital Spreaders Identification in Complex Networks with Multi-Local Dimension
- Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
- Detecting and modelling real percolation and phase transitions of information on social media
- Optimization of robustness based on reinforced nodes in a modular network
- Redefinition of site percolation in light of entropy and the second law of thermodynamics
- Realizing interdependent couplings as thermal or higher-order interactions
- Core language brain network for fMRI-language task used in clinical applications
- Vulnerable Connectivity Caused by Local Communities in Spatial Networks
- Backtracking activation impacts the criticality of excitable networks
- Universality class of explosive percolation in Barabási-Albert networks
- Triadic percolation on multilayer networks
- Modeling resource consumption in the US air transportation system via minimum-cost percolation
- Prestige bias drives the viral spread of content reposted by influencers in online communities
- Optimal shattering of complex networks
- Balancing Speed and Coverage by Sequential Seeding in Complex Networks
- A Graph-Neural-Network-Entropy model of vital node identification on network attack and propagation
- Degree distributions under general node removal: Power-law or Poisson?
- Finding the proper node ranking method for complex networks
- The wisdom of the few: Predicting collective success from individual behavior
- Describing the effect of influential spreaders on the different sectors of Indian market: a complex networks perspective
- A weighted planar stochastic lattice with scale-free, small-world and multifractal properties
- Identifying influential subpopulations in metapopulation epidemic models using message-passing theory
- The Mass, Fake News, and Cognition Security
- Maximizing spreading influence via measuring influence overlap for social networks
- On the accuracy of message-passing approaches to percolation in complex networks
- K-core attack, equilibrium K-core, and kinetically constrained spin system
- New nodes attack strategies for real complex weighted networks
- Induced Percolation on Networked Systems
- Localization of nonbacktracking centrality on dense subgraphs of sparse networks
- On the Aggression Diffusion Modeling and Minimization in Online Social Networks
- D-chain tomography of networks: a new structure spectrum and an application to the SIR process
- Percolation Threshold for Competitive Influence in Random Networks
- Learning Parameters for Balanced Index Influence Maximization
- Effective vaccination strategy using graph neural network ansatz
- The role of susceptible individuals in spreading dynamics
- Lowest Degree Decomposition of Complex Networks
- Monolingual and bilingual language networks in healthy subjects using functional MRI and graph theory
- Identifying Central Nodes in Multiplex Networks by Embracing Layer-Specific Heterogeneity via DomiRank
- Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
- Maximizing spreading in complex networks with risk in node activation
- Local Articulation Points in Complex Networks
- Universal and generalizable restoration strategies for degraded ecological networks
- Dismantle a network efficiently during the entire process by a compound algorithm
- A Behavioral Analysis on the Reselection of Seed Nodes in Independent Cascade Based Influence Maximization
- HyperCI: A Higher Order Collective Influence Measure for Hypernetwork Dismantling
- Approximating nonbacktracking centrality and localization phenomena in large networks
- Incentive Compatible Mechanism for Influential Agent Selection
- Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks
- Evaluation of User Dynamics Created by Weak Ties among Divided Communities
- Identifying early-warning indicators of tipping points in networked systems against sequential attacks
- Integrating behavioral experimental findings into dynamical models to inform social change interventions
- Exploring the Node Importance Based on von Neumann Entropy
- Quantifying Dismantlement in Disconnected Networks
- Ensemble approach for generalized network dismantling