algo-net-influence

Influence Maximization

Overview

Influence maximization selects k seed nodes in a network to maximize expected spread under a diffusion model (Independent Cascade or Linear Threshold). NP-hard, but the greedy algorithm achieves (1-1/e) ≈ 63% approximation guarantee due to submodularity. Practical for networks up to millions of nodes with CELF optimization.

When to Use

Trigger conditions:

• Selecting k influencers/users to seed a viral marketing campaign
• Maximizing information spread under a fixed budget (k seeds)
• Comparing seeding strategies (degree-based vs greedy vs random)

When NOT to use:

• When measuring existing influence (use centrality metrics)
• For community structure analysis (use community detection)

Algorithm

IRON LAW: Greedy With Lazy Evaluation (CELF) Is the Practical Standard
The naive greedy algorithm requires O(k × n × R) simulations where
R = Monte Carlo runs (10,000+). CELF exploits submodularity to skip
unnecessary evaluations, achieving 700x speedup. Always use CELF
over naive greedy. Simple heuristics (top-k by degree) are fast
but can perform 50%+ worse than greedy.

Phase 1: Input Validation

Build network graph. Choose diffusion model: Independent Cascade (probability per edge) or Linear Threshold (threshold per node). Set k (number of seeds) and propagation probabilities. Gate: Graph loaded, diffusion model selected, k defined.

Phase 2: Core Algorithm

Greedy with CELF:

1. Initialize: seed set S = ∅
2. For each candidate node, estimate marginal gain: σ(S∪{v}) - σ(S) via Monte Carlo simulation (R=10,000 runs)
3. Select node with highest marginal gain, add to S
4. CELF optimization: reuse previous marginal gains, only re-evaluate when a node's upper bound exceeds current best
5. Repeat until |S| = k

Phase 3: Verification

Compare greedy result against baselines: random seeds, top-k degree, top-k PageRank. Greedy should significantly outperform. Gate: Greedy spread > degree heuristic spread, difference is meaningful.