For any node to possibly flip, there must be some nodes that have the disease at \(t = 0\). These nodes are called seeders.
Brings topology into the picture: flip iff \(p\) of your neighbors have flipped.
- Assumes that each node has the same flipping threshold \(p\)
Will the Whole Network Flip?
For a cluster of nodes, let \(d_i\) be the fraction of the neighbors of \(i\) that are in the cluster. The density \(d\) of the cluster is \( min_i d_i \), i.e. the node with the most outside influence. For example:
The whole network flips iff all clusters of state zero (nodes at initialization time) have density \( d < 1 - p \). Otherwise, the cluster with \(d > 1 - p \) has enough inertia from within to resist outside influence.
Which Nodes Do We Seed?
The tradeoff is that more influential nodes will cost us more.
Under a total budget constraint:
- If we can only choose one, the most important one is a good bet.
- If we can choose more than one, the combined influential power matters more. Consider network topology and heterogenous flipping thresholds.