Efficient Influence Maximization: The Power of Shortest Paths in Social Networks

TL;DR

The classic Influence Maximization (IM) problem is often bottlenecked by the need for thousands of Monte Carlo simulations to estimate "spread." This paper proposes the SPM (Shortest-Path Model) and SP1M, which approximate the Independent Cascade Model by focusing on the most efficient propagation routes. This allows for exact mathematical calculation of influence, reducing computation time from hours to minutes while maintaining high selection accuracy.

Background & Motivation: The Simulation Bottleneck

In the context of viral marketing, we want to pick $k$ seeds that trigger the largest "word-of-mouth" cascade. Since the Independent Cascade Model (ICM) is stochastic, calculating the expected number of active nodes $\sigma (A)$ is the core challenge.

The landmark work by Kempe et al. (2003) proved that a greedy algorithm yields a $(1-1/e)$ approximation. However, because $\sigma (A)$ cannot be solved analytically for general ICM, researchers have relied on brute-force simulations. On a network of just 12,000 nodes, selecting a small seed set can take an hour of CPU time—rendering it impractical for real-time applications or massive web-scale graphs.

Methodology: Pruning the Long Tail of Diffusion

The authors' core insight is that in many social networks, propagation probabilities ($p$) are small. When probabilities are low, the likelihood of a node being activated by a very long, circuitous path is virtually zero.

1. Shortest-Path Model (SPM)

In SPM, a node $v$ can only be activated at time $t=d(A,v)$, where $d$ is the shortest distance from the seed set $A$. Effectively, we only consider the most direct "efficiency" paths.

2. SP1M (The Extended Model)

SP1M relaxes this by allowing activation at $t=d(A,v)$ and $t=d(A,v)+1$. This captures slightly more complex chain reactions while remaining computationally tractable.

Mathematically Exact Calculation

Unlike the standard ICM, the influence in these models can be computed recursively. For a node $v$, the probability of activation depends on its parents who were activated in the previous step:

$P_t(v;A)=1-{\prod }_{u\in PA(v)}(1-p_{u,v}{P}_{t-1}(u;A))$

This formula allows the algorithm to sweep through the graph's distances and compute the exact expected spread without rolling the dice a single time.

Experimental Results: Performance and Speed

The authors tested their methods on a trackback network of 12,047 blogs.

• Computation Time:
  • Standard ICM (10,000 sims): ~60 minutes.
  • SP1M (Proposed): ~3 minutes.
  • SPM (Proposed): ~1 minute.
• Accuracy (F-measure): Using the greedy set from the standard ICM as the "Ground Truth," the SP1M achieved a remarkably high overlap, significantly outperforming the "Only-Listen-Once" model and low-fidelity simulations.

In the figure above, the squares (SP1M) track the optimal performance much closer than the diamonds (OLOM) or triangles (low-iteration ICM).

Critical Analysis & Takeaways

The beauty of this work lies in its principled simplification. Instead of trying to speed up the simulation, the authors changed the underlying model to one that is analytically solvable yet physically representative of low-probability diffusion.

Key Takeaways:

1. Inductive Bias Matters: In social networks with low link weights, the "shortest path" is a dominant feature. Exploiting this bias yields an order-of-magnitude speedup.
2. Theoretical Safety: The paper proves that SPM and SP1M maintain submodularity, meaning the greedy algorithm still provides its famous theoretical guarantees.
3. Limitations: The model assumes small propagation probabilities ($p\approx 1\%$). If $p$ is high (e.g., $p>10\%$), the "long paths" ignored by SPM would become significant, and the approximation quality would likely degrade.

Future Outlook

This approach paves the way for "Tractable Influence Maximization." Future research could look into Dynamic SPM, where the path lengths are adjusted based on the community structure of the network, or applying these models to heterogeneous graphs where different link types have varying propagation "speeds."