Same underlying model as the 3D version, drawn flat: a Barabási–Albert social network (44 accounts, preferential attachment — a few "influencer" hubs, most accounts have few links), laid out in 2D by the same spring/repulsion force layout. Drag the graph to pan, scroll/pinch to zoom.
A post starts active at the seed set S and spreads by the Independent Cascade model: each newly-activated node u gets exactly one chance to activate every inactive neighbor v, independently, with probability p.
σ(S) = E[ |nodes ever activated, seeded from S| ]
Each edge (u→v) fires once, independently, w.p. p, only when u is active.
σ(S) is estimated by Monte-Carlo: simulate the cascade many times from the same seed set and average the number of activated nodes.
Greedy algorithm — build S one node at a time. At each step add the node v that maximizes the marginal gain Δ(v|S) = σ(S∪{v}) − σ(S), estimated by rerunning Monte-Carlo with each candidate added:
for i = 1..k:
v* = argmax_v σ(S ∪ {v}) − σ(S)
S = S ∪ {v*}
Because σ is monotone and submodular (each additional seed helps, with diminishing returns), this greedy rule is provably within a factor (1 − 1/e) ≈ 63% of the true optimum — a classical result (Kempe, Kleinberg & Tardos, 2003) that underlies real influence-maximization / viral-marketing systems. The strip chart under the graph plots each step's marginal gain so the diminishing-returns curve — the visual signature of submodularity — is visible directly.
- Greedy / High-Degree / Random — three seed-picking strategies to compare; High-Degree just takes the k highest-degree hubs, Random samples k accounts uniformly.
- Compute Seed Set — runs the chosen algorithm and reports its Monte-Carlo expected spread, plotting per-step marginal gain (greedy only) in the strip chart.
- Simulate Cascade — animates one concrete random realization of the Independent Cascade process from the current seeds, wave by wave; the strip chart switches to plotting cumulative activated count per wave.