Influence maximization in complex networks through optimal percolation

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].

arXiv comment7 pages, 3 figures, Supplementary Information: 52 pages, 10 extended data figs

References in corpus (16)

• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• The spread of epidemic disease on networks
• Identification of influential spreaders in complex networks
• Breakdown of the Internet under intentional attack
• Spectral redemption: clustering sparse networks
• Spectral methods for network community detection and graph partitioning
• Searching for superspreaders of information in real-world social media
• Optimization with Extremal Dynamics
• Percolation on sparse networks
• Spreading dynamics in complex networks
• Multiple percolation transitions in a configuration model of network of networks
• Containing epidemic outbreaks by message-passing techniques
• Predicting percolation thresholds in networks
• Optimizing spread dynamics on graphs by message passing
• A Spectral Approach to Analyzing Belief Propagation for 3-Coloring

Cited by in corpus (219)

• 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
• Computational Socioeconomics
• Local structure can identify and quantify influential global spreaders in large scale social networks
• Finding influential nodes for integration in brain networks using optimal percolation theory
• Network science based quantification of resilience demonstrated on the Indian Railways Network
• Detection of Core-Periphery Structure in Networks Using Spectral Methods and Geodesic Paths
• 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
• Leveraging percolation theory to single out influential spreaders in networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• 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
• $k$-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
• Rare events and discontinuous percolation transitions
• Climate network percolation reveals the expansion and weakening of the tropical component under global warming
• 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
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Fluctuations in percolation of sparse complex networks
• 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 web of federal crimes in Brazil: topology, weaknesses, and control
• The localization of non-backtracking centrality in networks and its physical consequences
• 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
• Distance entropy cartography characterises centrality in complex networks
• Underestimated cost of targeted attacks on 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
• Why are there six degrees of separation in a social network?
• From degree-correlated to payoff-correlated activity for an optimal resolution of social dilemmas
• 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
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Cascading collapse of online social networks
• Heterogeneous micro-structure of percolation in sparse networks
• Bistability and time crystals in long-ranged directed percolation
• Pre-Training Graph Neural Networks for Generic Structural Feature Extraction
• Containing misinformation spreading in temporal social networks
• Influence maximization on temporal networks
• Correlated network of networks enhances robustness against catastrophic failures
• Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
• 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
• Percolation Framework of the Earth's Topography
• A Network Science perspective of Graph Convolutional Networks: A survey
• Modeling social resilience: Questions, answers, open problems
• Forecasting countries' gross domestic product from patent data
• The long-term impact of ranking algorithms in growing networks
• Targeted influence maximization in complex networks
• The price of a vote: diseconomy in proportional elections
• 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
• Dynamic range maximization in excitable networks
• Probing Limits of Information Spread with Sequential Seeding
• Optimal redundancy against disjoint vulnerabilities in networks
• A new design principle of robust onion-like networks self-organized in growth
• 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
• Influence Maximization for Fixed Heterogeneous Thresholds
• Triadic percolation induces dynamical topological patterns in higher-order networks
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Node Immunization with Non-backtracking Eigenvalues
• Extended-range percolation in complex networks
• Emergence of Robustness in Network of Networks
• Modelling indirect interactions during failure spreading in a project activity network
• Controlling percolation with limited resources
• Optimal Stabilization of Boolean Networks through Collective Influence
• Deep-learning-aided dismantling of interdependent networks
• Multilayer modeling of adoption dynamics in energy demand management
• Spectral estimation of the percolation transition in clustered networks
• Optimal cost for strengthening or destroying a given network
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Seeds Buffering for Information Spreading Processes
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Critical phenomena of a hybrid phase transition in cluster merging dynamics
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Towards Quantifying Sampling Bias in Network Inference
• Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time
• Effects of Time Horizons on Influence Maximization in the Voter Dynamics
• The epidemiology of lateral movement: exposures and countermeasures with network contagion models
• Stochastic Dynamic Programming Heuristics for Influence Maximization-Revenue Optimization
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Targeted Recovery as an Effective Strategy against Epidemic Spreading
• Effective submodularity of influence maximization on temporal networks
• Rank the spreading influence of nodes using dynamic Markov process
• Influence maximization in noisy networks
• The optimal edge for containing the spreading of SIS model
• Identifying Influential Brokers on Social Media from Social Network Structure
• Dismantling Efficiency and Network Fractality
• Colored Percolation
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Bounding robustness in complex networks under topological changes through majorization techniques
• Explosive dismantling of two-dimensional random lattices under betweenness centrality attacks
• Centralities in complex networks
• Degree-targeted cascades in modular, degree-heterogeneous networks
• Performance of attack strategies on modular networks
• Efficient network exploration by means of resetting self-avoiding random walkers
• Influence Maximization: Divide and Conquer
• Observability transition in real networks
• Computational Aspects of Optimal Strategic Network Diffusion
• Price graphs: Utilizing the structural information of financial time series for stock prediction
• Weighted cycle-based identification of influential node groups in complex networks
• Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
• Spin-glass model for the C-dismantling problem
• Controllability of the Voter Model: an information theoretic approach
• 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
• Core language brain network for fMRI-language task used in clinical applications
• Detecting and modelling real percolation and phase transitions of information on social media
• Realizing interdependent couplings as thermal or higher-order interactions
• Beyond the Coverage of Information Spreading: Analytical and Empirical Evidence of Re-exposure in Large-scale Online Social Networks
• 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
• Vulnerable Connectivity Caused by Local Communities in Spatial Networks
• Describing the effect of influential spreaders on the different sectors of Indian market: a complex networks perspective
• Universality class of explosive percolation in Barabási-Albert networks
• A Graph-Neural-Network-Entropy model of vital node identification on network attack and propagation
• Optimal shattering of complex networks
• Backtracking activation impacts the criticality of excitable networks
• The wisdom of the few: Predicting collective success from individual behavior
• Finding the proper node ranking method for complex networks
• Triadic percolation on multilayer networks
• Balancing Speed and Coverage by Sequential Seeding in Complex 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
• A weighted planar stochastic lattice with scale-free, small-world and multifractal properties
• Degree distributions under general node removal: Power-law or Poisson?
• On the accuracy of message-passing approaches to percolation in complex networks
• The Mass, Fake News, and Cognition Security
• On the Aggression Diffusion Modeling and Minimization in Online Social Networks
• Identifying influential subpopulations in metapopulation epidemic models using message-passing theory
• D-chain tomography of networks: a new structure spectrum and an application to the SIR process
• Percolation Threshold for Competitive Influence in Random Networks
• New nodes attack strategies for real complex weighted networks
• Maximizing spreading influence via measuring influence overlap for social networks
• Induced Percolation on Networked Systems
• Learning Parameters for Balanced Index Influence Maximization
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Lowest Degree Decomposition of Complex Networks
• Maximizing spreading in complex networks with risk in node activation
• Identifying Central Nodes in Multiplex Networks by Embracing Layer-Specific Heterogeneity via DomiRank
• Effective vaccination strategy using graph neural network ansatz
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Monolingual and bilingual language networks in healthy subjects using functional MRI and graph theory
• The role of susceptible individuals in spreading dynamics
• Integrating behavioral experimental findings into dynamical models to inform social change interventions
• Universal and generalizable restoration strategies for degraded ecological networks
• Approximating nonbacktracking centrality and localization phenomena in large networks
• Exploring the Node Importance Based on von Neumann Entropy
• Identifying early-warning indicators of tipping points in networked systems against sequential attacks
• HyperCI: A Higher Order Collective Influence Measure for Hypernetwork Dismantling
• Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks
• Evaluation of User Dynamics Created by Weak Ties among Divided Communities
• Incentive Compatible Mechanism for Influential Agent Selection
• Local Articulation Points in Complex Networks
• Dismantle a network efficiently during the entire process by a compound algorithm
• Ensemble approach for generalized network dismantling
• A Behavioral Analysis on the Reselection of Seed Nodes in Independent Cascade Based Influence Maximization
• Quantifying Dismantlement in Disconnected Networks