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