Efficient collective influence maximization in cascading processes with first-order transitions

Abstract

In social networks, the collective behavior of large populations can be shaped by a small set of influencers through a cascading process induced by "peer pressure". For large-scale networks, efficient identification of multiple influential spreaders with a linear algorithm in threshold models that exhibit a first-order transition still remains a challenging task. Here we address this issue by exploring the collective influence in general threshold models of behavior cascading. Our analysis reveals that the importance of spreaders is fixed by the subcritical paths along which cascades propagate: the number of subcritical paths attached to each spreader determines its contribution to global cascades. The concept of subcritical path allows us to introduce a linearly scalable algorithm for massively large-scale networks. Results in both synthetic random graphs and real networks show that the proposed method can achieve larger collective influence given same number of seeds compared with other linearly scalable heuristic approaches.

14 pages, 7 figures

References in corpus (21)

• Error and attack tolerance of complex networks
• Catastrophic cascade of failures in interdependent networks
• Identification of influential spreaders in complex networks
• Influence maximization in complex networks through optimal percolation
• Searching for superspreaders of information in real-world social media
• Localization and centrality in networks
• Network dismantling
• Avoiding catastrophic failure in correlated networks of networks
• Spreading dynamics in complex networks
• Bootstrap Percolation on Complex Networks
• Understanding the spreading power of all nodes in a network: a continuous-time perspective
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Identifying optimal targets of network attack by belief propagation
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Leveraging percolation theory to single out influential spreaders in networks
• Optimizing spread dynamics on graphs by message passing
• Exploring the complex pattern of information spreading in online blog communities
• Large deviations of cascade processes on graphs
• The diminishing role of hubs in dynamical processes on complex networks
• Minimal contagious sets in random regular graphs
• Identification of highly susceptible individuals in complex networks

Cited by in corpus (12)

• Optimal percolation on multiplex networks
• Targeted influence maximization in complex networks
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Dynamic range maximization in excitable networks
• Influence Maximization for Fixed Heterogeneous Thresholds
• Optimal Stabilization of Boolean Networks through Collective Influence
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Critical behaviors of high-degree adaptive and collective-influence percolation
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Backtracking activation impacts the criticality of excitable networks
• Control of cascading failures using protective measures
• Learning Parameters for Balanced Index Influence Maximization