Exact greedy influence maximization runs in linear time on simple graphs
Exact Greedy Influence Maximization in Linear Time on Bounded-Treewidth Graphs
Data Structures and Algorithms
Summary
Finding the best places to start spreading something in a network is usually very hard. The authors focus on networks that have a simple structure called bounded treewidth and show how to calculate exactly how influence spreads much faster than before. They develop a method that calculates all the necessary increases in influence at once, speeding up a classic greedy algorithm for selecting these starting points. Their approach is efficient for networks with certain structures and works well in experiments with synthetic data.
What this means in practice
- •For social media platform engineers: Optimize influential user selection in networks with limited complexity to improve viral marketing campaigns with exact computations instead of approximate sampling.
- •For network security teams: Precisely identify key nodes to protect or monitor in structured communication networks by efficiently simulating contagion or attack spread.
Tested on simulated data.
Authors
Matic Požar
Abstract
Computing influence spread under the Independent Cascade (IC) model is #P-hard, and influence maximization is commonly approached using Monte Carlo or reverse-reachable-set sampling. We study IC diffusion on bounded-treewidth graphs. Using probability distributions over separator reachability relations, we obtain exact influence evaluation in $O(n2^{O(w^2)}\operatorname{poly}(w))$ time for a graph with $n$ nodes and treewidth $w$. Our main contribution is an exact all-marginal-gains algorithm. We introduce variable artificial source edges and show that, at a deterministic seed set, the derivative with respect to each source-edge probability equals the corresponding greedy marginal gain. Reverse-mode differentiation therefore computes all marginal gains simultaneously with the same asymptotic complexity as one exact influence evaluation. This yields an exact implementation of classical greedy influence maximization in $O(Kn2^{O(w^2)}\operatorname{poly}(w))$ time, linear in graph size for fixed $w$ and seed budget $K$. We also show that the separator-relation representation has tight $2^{Θ(w^2)}$ state complexity within exact context-independent compositional separator summaries. This contrasts with the NP-hardness of globally optimal IC influence maximization already on graphs of treewidth one and pathwidth two. Experiments on synthetic bounded-treewidth networks are consistent with linear scaling for fixed width and show that runtime is largely insensitive to propagation and seed-activation probabilities. In demanding diffusion regimes, the method substantially outperforms reverse-reachable-set and optimized Monte Carlo greedy baselines while computing greedy marginal gains exactly.