# Sketch-based Influence Maximization and Computation: Scaling up with Guarantees

arXiv: https://arxiv.org/abs/1408.6282 · HTML: https://mlsanity.com/paper/1408.6282/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2014.

## Built on by (most cited first, 9 of 9)

- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Learning of networked spreading models from noisy and incomplete data](https://mlsanity.com/paper/2401.00011/) (2023)
- [Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2309.07153/) (2023)
- [Influence Estimation and Maximization via Neural Mean-Field Dynamics](https://mlsanity.com/paper/2106.02608/) (2021)
- [XFlow: Benchmarking Flow Behaviors over Graphs](https://mlsanity.com/paper/2308.03819/) (2023)
- [GNN-Based Candidate Node Predictor for Influence Maximization in Temporal Graphs](https://mlsanity.com/paper/2503.23713/) (2025)
- [Budgeted Online Influence Maximization](https://mlsanity.com/paper/2604.19672/) (2026)
- [Network World Models as Environments for Algorithm Design on Complex Systems](https://mlsanity.com/paper/2610.01048/) (2026)

## Abstract (arXiv)

Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a probabilistic model, such as Independent Cascade (IC), or captured by a set of representative traces. Basic computational problems in the study of diffusion are influence queries (determining the potency of a specified seed set of nodes) and Influence Maximization (identifying the most influential seed set of a given size). Answering each influence query involves many edge traversals, and does not scale when there are many queries on very large graphs. The gold standard for Influence Maximization is the greedy algorithm, which iteratively adds to the seed set a node maximizing the marginal gain in influence. Greedy has a guaranteed approximation ratio of at least (1-1/e) and actually produces a sequence of nodes, with each prefix having approximation guarantee with respect to the same-size optimum. Since Greedy does not scale well beyond a few million edges, for larger inputs one must currently use either heuristics or alternative algorithms designed for a pre-specified small seed set size. We develop a novel sketch-based design for influence computation. Our greedy Sketch-based Influence Maximization (SKIM) algorithm scales to graphs with billions of edges, with one to two orders of magnitude speedup over the best greedy methods. It still has a guaranteed approximation ratio, and in practice its quality nearly matches that of exact greedy. We also present influence oracles, which use linear-time preprocessing to generate a small sketch for each node, allowing the influence of any seed set to be quickly answered from the sketches of its nodes.