Source-linked AI summary
Maximizing Social Influence in Nearly Optimal Time
Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier
TL;DR
The paper addresses how to choose a limited set of seed nodes to maximize diffusion cascades in massive networks, where runtime is a primary concern. It develops a randomized, quasilinear-time influence-maximization algorithm with near-optimal approximation guarantees and a sublinear-time variant with reduced approximation.
Problem
Influence maximization seeks an appropriate set of k nodes to seed a diffusion process, while massive networks and volatile data make near-linear runtime practically necessary.
Method
The paper develops a randomized polling-based algorithm under the independent cascade model, using influencer sampling rather than directly estimating every node's influence.
Results
O((m + n)kε−2 log n) runtime achieves a near-optimal approximation, with success probability 3/5; the method also supports sublinear execution with reduced approximation.
Takeaways & Limitations
The approach bridges approximation quality and scalability for massive networks, while its limited graph-access requirements support implementation in several sparse-graph access models.
Takeaways & Limitations
The guarantees assume adjacency-list input and access to uniform node sampling, with prior runtime lower bounds stated under these access assumptions.
Abstract
from arXiv · showhide
Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Runtime is a primary consideration for this problem due to the massive size of the relevant input networks. We provide a fast algorithm for the influence maximization problem, obtaining the near-optimal approximation factor of (1 - 1/e - epsilon), for any epsilon > 0, in time O((m+n)k log(n) / epsilon^2). Our algorithm is runtime-optimal (up to a logarithmic factor) and substantially improves upon the previously best-known algorithms which run in time Omega(mnk POLY(1/epsilon)). Furthermore, our algorithm can be modified to allow early termination: if it is terminated after O(beta(m+n)k log(n)) steps for some beta < 1 (which can depend on n), then it returns a solution with approximation factor O(beta). Finally, we show that this runtime is optimal (up to logarithmic factors) for any beta and fixed seed size k.
1 Introduction
Influence maximization seeks a size-k seed set that maximizes expected cascade size under independent cascades, while massive networks make runtime critical. The paper develops a near-optimal approximation algorithm with quasilinear-time preprocessing, early termination, and matching runtime lower bounds.
- 1 Introduction: The influence-maximization problem selects at most k target nodes to maximize the expected magnitude of a diffusion cascade.The paper studies this problem under the standard independent cascade model.
- 1 Introduction: Massive social networks can contain billions of edges, making near-linear influence-maximization runtime practically necessary.Volatile network data and influence parameters also require solutions to be recomputed over time.
- 1 Introduction: Prior simulation-based approaches require runtime Ω(mnk · POLY(ε^-1)), whereas this work targets quasilinear time using limited graph access.The algorithm assumes adjacency-list input and uses uniform vertex sampling and traversal of incident edges.
- 1 Introduction: (1 − 1/e − ε)-approximately optimal seed sets can be found in time O((m + n)kε^-2 log n) on arbitrary directed networks.This approximation is nearly optimal because no polynomial-time algorithm achieves (1 − 1/e + ε) for any ε > 0 unless P = NP.
- 1 Introduction: The algorithm samples reverse influence sets to build a sparse hypergraph whose degrees estimate seed-set influence, then selects the entire seed set from that structure.All sampling is performed up front rather than repeatedly estimating marginal gains during incremental construction.
- 1 Introduction: Early termination after O(β(n + m)k log n) steps returns an O(β)-approximation, with runtime lower bounds showing near-optimality for fixed k.The randomized algorithm succeeds with probability 3/5, and failure is detectable and amplifiable through repetition.
2 Model and Preliminaries
The independent cascade model represents diffusion as stochastic reachability in a random directed graph. The preliminaries define influence, marginal influence, the optimization objective, and the simulation primitive used by the algorithms.
- 2 Model and Preliminaries: In the independent cascade model, each infected node gets one chance to infect each neighbor, with edge weights giving transmission probabilities.The process unfolds in rounds from an initial seed set.
- 2 Model and Preliminaries: Equivalently, independently realize each weighted edge with its transmission probability and define the infected set as nodes reachable from the seeds.This random-graph formulation is used throughout the paper.
- 2 Model and Preliminaries: For a graph g, Cg(S) is the set reachable from S, Ig(S) is its size, and EG[I(S)] is expected influence over the random graph distribution.The notation uses m and n for the numbers of edges and nodes in G.
- 2 Model and Preliminaries: Marginal influence Ig(S|W) counts nodes reachable from S but not W, with expected marginal influence defined by averaging over g ∼ G.This quantity measures the additional influence of S relative to W.
- 2 Model and Preliminaries: Influence maximization finds at most k nodes maximizing EG[I(S)], with a β-approximation satisfying EG[I(S)] ≥ β · OPT.The graph is provided in adjacency-list format.
- 2 Model and Preliminaries: The simulation primitive realizes a random cascade from a vertex by traversing its reachable set, and the implementation follows edges with independent probability tests.The same procedure can be implemented on the transpose graph by following in-links rather than out-links.
3 An Approximation Algorithm for Influence Maximization
The algorithm builds a sparse hypergraph by simulating influence on the transpose graph, then applies greedy seed selection to that representation. With an appropriate runtime bound, it achieves a near-optimal approximation with constant success probability.
- Algorithm construction: The algorithm constructs a sparse hypergraph by repeatedly simulating influence spread from uniformly sampled nodes in the transpose graph.The resulting hypergraph represents the original network and supports subsequent seed-set construction.
- Seed selection: The algorithm applies greedy selection to the hypergraph, repeatedly choosing the highest-degree node and removing its incident edges until k seeds are selected.The formal algorithm takes a directed edge-weighted graph and runtime bound as input, then returns the seed set produced by BuildSeedSet.
- Guarantee: With R = cmkε−2 log(n), the algorithm returns a (1−1/e−ε)-approximation with probability at least 3/5 and runtime Θ(mkε−2 log(n)).The theorem states the same approximation guarantee in O((m+n)kε−2 log n) time for arbitrary directed graphs.
- Influence estimation: The hypergraph estimator relates a seed set’s total degree to its expected influence, enabling influence maximization through the sampled representation.The analysis interprets hypergraph degree as an estimator for expected influence and establishes its accuracy through concentration bounds.
- Analysis: The proof controls estimation error for all seed sets and transfers that guarantee to greedy maximization, yielding an output with expected influence at least (1−1/e−10ε)OPT before rescaling ε.The final success probability is at least 3/5 for n ≥ 20.
4 Approximate Influence Maximization in Sublinear Time
The paper develops a randomized influence-maximization algorithm whose runtime–approximation tradeoff remains effective in sublinear time, and establishes matching lower bounds under the query model.
- Dynamic Runtime: For any β < 1, Algorithm 2 returns an O(β)-approximation in O(β(n + m)k log(n)) time with probability at least 3/5.The algorithm can be terminated after an arbitrary number of steps and return a correspondingly scaled approximation.
- Dynamic Runtime: The modified method constructs fewer hypergraph edges to trade preprocessing time for approximation quality, with quality degrading gracefully as runtime decreases.When sampling is insufficient for the original approach, degree-proportional node selection supplies an alternative high-influence candidate.
- Approximation Guarantee: For k > 1, the algorithm combines the seed set with a degree-proportional sampled node; for k = 1, it chooses between the two procedures using the hypergraph’s maximum degree.The k = 1 decision is supported by concentration when a node appears in sufficiently many hyperedges.
- Approximation Guarantee: If the hypergraph has sufficiently many edges, the selected seed set achieves at least a 1/4 approximation; otherwise, a sampled node achieves at least β · OPT with high probability.The proof combines these two cases, yielding min{1/4, β} · OPT for the returned set.
- Lower Bound: The lower bound requires Ω(βn) queries to obtain approximation factor β with fixed probability under adjacency-list access and uniform node sampling.The construction extends to non-sparse networks, giving an expected-performance lower bound of nd/(24T min{k,T}) for networks with m = nd edges.
A Concentration Bounds
The paper states Chernoff bounds for lower- and upper-tail deviations of sums of independent Bernoulli variables.
- Setup: The bounds apply to n independent and identically distributed Bernoulli variables with common expectation µ.The sum is defined as X in the stated lemma.
- Chernoff Bounds: For 0 < λ < 1, the lower tail satisfies Pr[X < (1 − λ)µn] < exp(−µnλ^2/2).This bounds the probability that the sum falls below its expectation by a multiplicative factor.
- Chernoff Bounds: For 0 < λ < 1, the upper tail satisfies Pr[X > (1 + λ)µn] < exp(−µnλ^2/4).This bounds the probability that the sum exceeds its expectation by a multiplicative factor.