Influence Maximization in the Independent Cascade Model

Gianlorenzo D'Angelo, Lorenzo Severini, Yllka VelajICTCS 2016 · OpenReview

Introduction

In the study of social networks and information diffusion, the problem of Influence Maximization (IM) has traditionally focused on seed selection: identifying a small set of initial users (seeds) who can trigger the largest possible cascade of information or behavior. However, in many practical scenarios, the seeds are already fixed—such as a specific community leader, a brand ambassador, or a local health official.

This paper explores a different dimension of the problem: network modification. Instead of choosing new seeds, the authors investigate how to maximize the reach of a fixed seed node by strategically adding a limited number of new connections (edges) to it. This approach is particularly relevant for organizations looking to optimize the impact of existing influencers within a network structure.

The Problem: Structural Influence Maximization

The authors analyze this problem under the Independent Cascade Model (ICM). In this model, when a node becomes "active," it has a single chance to activate each of its currently inactive neighbors with a specific probability associated with the connecting edge. The process continues until no more activations are possible.

The primary challenge is that calculating the total expected number of active nodes (the influence) is a #P-complete problem, making it computationally intensive. Furthermore, while seed selection is known to be submodular, many forms of network modification do not share this property, often leaving researchers without formal performance guarantees for their algorithms.

Methodology

The research focuses on the case where the initial set of active nodes is a singleton (a single seed node, $a$). The goal is to select a set of $k$ new edges, all incident to the seed $a$, to maximize the expected influence $\sigma(A, G(S))$.

1. The Greedy Algorithm

To solve this, the authors employ a standard greedy approach:

  1. Start with an empty set of new edges.
  2. Iteratively add the single edge that provides the largest marginal gain in expected influence.
  3. Continue until the budget of $k$ edges is reached.

2. Theoretical Framework: Submodularity

The core of the paper is the mathematical proof that, for a single seed node, the influence function is both monotone (adding edges never decreases influence) and submodular. Submodularity is a "diminishing returns" property: the marginal benefit of adding an edge is greater when the set of existing added edges is small than when it is large.

3. Approximation via Sampling

Because exact influence calculation is intractable, the authors use the "live-edge graph" interpretation of the ICM. By simulating the diffusion process many times (Monte Carlo sampling), they can estimate the marginal gains of potential edges with high accuracy. This allows the greedy algorithm to function effectively in practice.

Key Results

The paper provides two foundational theorems that establish the reliability of the greedy approach for network modification:

  • Theorem 2: Formally proves that the expected influence is a monotonically increasing submodular function with respect to the set of edges added to a single seed node. This is a significant finding, as submodularity often breaks in more complex network modification scenarios.
  • Theorem 3: Establishes that a polynomial-time greedy algorithm can approximate the maximum possible influence within a factor of $(1 - 1/e - \epsilon)$. This provides a rigorous theoretical floor, guaranteeing that the algorithm will achieve approximately 63% of the optimal influence increase.

Discussion and Future Work

While this work provides a strong theoretical foundation for structural influence maximization, it identifies several avenues for further research:

  • Multiple Seeds: The current proof is limited to a singleton seed. Extending these guarantees to scenarios with multiple initial seeds is a primary objective for future study.
  • Edge Deletion: In contexts like epidemiology, the goal is often to minimize spread. The authors intend to explore whether these submodular properties hold when deleting edges to contain a cascade.
  • Empirical Validation: As a theoretical contribution, the paper does not yet include testing on real-world social network topologies. Future work will involve comparing the greedy algorithm against common heuristics on large-scale datasets.
  • Alternative Models: The authors plan to test these principles on the "Decreasing Cascade Model," where infection probabilities change based on previous failed attempts by other neighbors.

Summary updated

BibTeX
@inproceedings{dangelo2016influence,
  author = {Gianlorenzo D'Angelo and Lorenzo Severini and Yllka Velaj},
  title = {{Influence Maximization in the Independent Cascade Model}},
  booktitle = {ICTCS},
  year = {2016},
  url = {https://openreview.net/forum?id=rr1bAMW1kt8},
}
Figure