Collective influence maximization in threshold models of information cascading with first-order transitions

Sen Pei, Xian Teng, Jeffrey Shaman, Flaviano Morone, Hernán A. MaksearXiv 2016 · arXiv

Introduction

In network science, influence maximization is the critical task of identifying a minimal set of "seed" nodes that can trigger a system-wide cascade. This problem has profound implications across diverse fields, from viral marketing and public health to the prevention of cascading failures in critical infrastructure. While many models assume a gradual, second-order transition in information spread, real-world systems often exhibit first-order transitions. In these scenarios, a system remains stable until it reaches a tipping point, at which it abruptly "snaps" into a new state.

The Challenge of First-Order Transitions

Identifying influencers in discontinuous, first-order processes is an NP-hard problem. Traditional heuristics like PageRank or High Degree often fail because they are designed for gradual spread. While exact solutions exist, they are computationally intensive and do not scale to modern "big-data" networks containing millions or billions of nodes.

The CI-TM Algorithm

To address these challenges, researchers developed the Collective Influence in Threshold Model (CI-TM), a scalable $O(N \log N)$ algorithm. The algorithm is built upon the Linear Threshold Model (LTM), where a node $i$ activates only if a specific number of its neighbors ($m_i$) are already active.

The CI-TM framework: (a-b) defining subcritical conditions, (c-d) mapping paths of length $L$, and (e-f) identifying influential clusters.

The CI-TM approach focuses on "subcritical nodes"—those that are exactly one neighbor away from activation ($m_i - 1$ active neighbors). The algorithm's logic follows several key steps:

  1. Identify Subcritical Nodes: Flag nodes that are "primed" and waiting for a single nudge.
  2. Map Subcritical Paths: The algorithm identifies chains of these primed nodes. Activating a seed at the start of such a path creates a domino effect that propagates through the chain.
  3. Linearization: By linearizing non-linear message-passing equations, the authors defined a node's influence based on the number of subcritical paths of length $L$ emanating from it.
  4. Adaptive Greedy Selection: The algorithm iteratively selects the node with the highest CI-TM score and updates the network state to avoid overlapping influence.

Experimental Validation and Results

The authors validated CI-TM using both synthetic networks (Erdős-Rényi and Scale-Free) and massive real-world datasets, including the YouTube friendship network (~3.2M nodes) and the Internet Autonomous System network (~1.4M nodes).

Key Findings:

  • Lower Critical Thresholds: CI-TM consistently triggered global cascades with a significantly smaller fraction of seeds ($q_c$) compared to High Degree (HD), PageRank (PR), or K-core (KsA) strategies. On ER networks, CI-TM required a seed fraction of ~0.105, whereas random selection required ~0.220.
  • Bridges over Hubs: In first-order transitions, the most influential nodes are often not the most connected "hubs" but rather "bridges" that connect different subcritical clusters. At the tipping point, CI-TM's selected influencers differed by 80% from those chosen by simple degree-based methods.
  • Extreme Scalability: By limiting the search radius to $L$, the algorithm maintains $O(N \log N)$ complexity. It can process a network of $10^8$ nodes in approximately 27 hours ($10^5$ seconds), a feat impossible for previous non-linearized approaches.

Conclusion

CI-TM represents a significant advancement in identifying "superspreaders" in networks prone to abrupt transitions. By focusing on the "primed" state of subcritical nodes, the algorithm provides a computationally efficient way to manage or trigger large-scale cascades in massive, real-world systems. Future work may extend this model to dynamic topologies or networks with high clustering where the "tree-like" assumption of the current derivation may be challenged.

Summary updated

BibTeX
@misc{pei2016collective,
  author = {Sen Pei and Xian Teng and Jeffrey Shaman and Flaviano Morone and Hernán A. Makse},
  title = {{Collective influence maximization in threshold models of information cascading with first-order transitions}},
  year = {2016},
  eprint = {1606.02739},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.02739},
}
Figure