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 = ...