Diffusion models
Independent Cascade: each active node tries to activate neighbors once. Linear Threshold: activate when weighted sum of active neighbors exceeds threshold.
Advertisement
Greedy
Iteratively add node with largest marginal gain. Uses submodularity + monotonicity → (1 - 1/e) ≈ 63% approximation.
Advertisement
Complexity
Estimating influence: #P-hard, but Monte Carlo suffices. Total: O(K · N · Monte Carlo samples).
CELF optimization
Cost-Effective Lazy Forward: reuse marginal gain calculations. 700x speedup in practice.