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.

### Phase 4: Output
Return seed set with expected spread and comparison.

## Output Format

```json
{
  "seeds": [{"node": "user_42", "marginal_gain": 150, "selection_order": 1}],
  "expected_spread": 2500,
  "baselines": {"random": 800, "top_degree": 1900, "greedy": 2500},
  "metadata": {"k": 10, "model": "independent_cascade", "mc_simulations": 10000, "nodes": 50000}
}
```

## Examples

### Sample I/O
**Input:** Social network 10K nodes, k=5 seeds, IC model with p=0.1 per edge
**Expected:** Greedy selects diverse, well-positioned seeds (not all high-degree), expected spread ~500-1000.

### Edge Cases
| Input | Expected | Why |
|-------|----------|-----|
| k=1 | Node with highest individual spread | Single seed, no overlap consideration |
| k > number of communities | One seed per community optimal | Diversity beats concentration |
| Very sparse graph (low p) | Small spread regardless of seeds | Network can't propagate with low probability |

## Gotchas

- **Monte Carlo variance**: With R=1000, spread estimates have ~5% variance. Use R=10,000+ for stable results, especially when comparing close candidates.
- **Diffusion model choice matters**: IC and LT produce different optimal seed sets. IC favors high-degree nodes; LT favors nodes that can trigger cascades.
- **Propagation probability estimation**: Real-world edge probabilities are unknown. Common approaches: uniform (p=0.01-0.1), weighted inverse degree (1/in-degree), or learned from cascade data.
- **Overlap penalty**: Greedy naturally handles overlap (submodularity). Heuristics that independently select top nodes waste seeds on overlapping influence spheres.
- **Scalability**: Even with CELF, millions of nodes require further approximation (sketch-based methods like IMM or TIM+).

## References

- For CELF and CELF++ implementation, see `references/celf-implementation.md`
- For scalable influence maximization (IMM), see `references/scalable-im.md`