Influence Maximization in Big Networks: An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation

Weixue Lu, Peng Zhang, Chuan Zhou, Chun-Yi Liu, Li GaoIJCAI 2015

Introduction

Influence Maximization (IM) aims to identify a small set of "seed" nodes that triggers the largest possible information cascade within a social network. While essential for viral marketing, IM faces two significant challenges: computational complexity and the static nature of existing algorithms. Estimating influence spread is #P-hard, typically requiring thousands of Monte Carlo (MC) simulations that do not scale to millions of nodes. Furthermore, real-world networks are dynamic, yet most algorithms require a full re-run whenever the graph structure changes. This paper introduces an incremental algorithm designed to handle massive, streaming network data by decomposing graphs into manageable subgraphs.

Methodology

The authors propose a "divide-and-conquer" strategy to estimate influence spread efficiently.

Network Decomposition and Snapshot Simulation

The process begins by breaking a large graph $G$ into $N$ edge-disjoint subgraphs. These subgraphs are treated as a data stream. Instead of simulating the entire network, "coin flip" simulations are performed under the Independent Cascade model on each small subgraph to create "snapshots." To optimize memory and speed, these snapshots are converted into Strongly Connected Components (SCCs). If node A can reach node B and vice versa within a snapshot, they are treated as a single unit, significantly reducing the data dimensionality.

Decomposition of the original graph into edge-disjoint subgraphs.

The Join Operator ($\oplus$) and Incremental Estimation

The core innovation is the "join" operator, which reconstructs global reachability by combining SCC results from different subgraphs. By joining a polynomial number of subgraph snapshots ($M^2$ joins), the algorithm estimates global influence spread. The authors utilize Hoeffding’s Inequality to prove that this incremental approach converges to the true expected influence spread faster than traditional methods, even with fewer total simulations.

Illustration of different join groups used to reconstruct global reachability across snapshot stages.

Parallelism and Redundancy Reduction

Because the network is partitioned, snapshot generation and SCC extraction can be performed in parallel. Additionally, by maintaining and incrementally updating snapshots, the algorithm avoids redundant simulations when the seed set changes or the network evolves.

Experimental Evaluation

The algorithm was evaluated using four real-world datasets from the SNAP repository:

  • ego-Facebook: A social network of 4,039 nodes.
  • ca-HepPh: A collaboration network of 12,008 High Energy Physics researchers.
  • ca-CondMat: A collaboration network for Condensed Matter physics (23,133 nodes).
  • email-Enron: A communication network of 36,692 nodes.

Results and Discussion

In all tested datasets, the incremental algorithm achieved a higher influence spread than common heuristics such as DegreeDiscount, PMIA, and PageRank. In terms of efficiency, it matched the speed of StaticGreedy while providing superior accuracy and was orders of magnitude faster than the standard CELF algorithm. Notably, the authors demonstrated that using only $M=100$ snapshots per subgraph was sufficient to outperform traditional methods requiring $M=10,000$ full-graph simulations.

Despite these strengths, the current approach assumes edges are split into disjoint sets across subgraphs. While SCCs compress data, maintaining a high number of snapshot joins could lead to memory overhead in extremely large deployments. Future work may further explore the latency costs of real-time updates in dynamic networks.

Conclusion

This paper presents a scalable, incremental framework for Influence Maximization. By leveraging subgraph decomposition and a novel join operator, the proposed algorithm bridges the gap between theoretical complexity and the practical needs of massive, dynamic social networks.

Summary updated

BibTeX
@inproceedings{lu2015influence,
  author = {Weixue Lu and Peng Zhang and Chuan Zhou and Chun-Yi Liu and Li Gao},
  title = {{Influence Maximization in Big Networks: An Incremental Algorithm for Streaming Subgraph Influence Spread Estimation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure