Cascading Behavior In Networks

Motivation: ideas that spread like epidemics

Religions and political movements, agricultural and medical innovations, product hits, celebrities, financial bubbles: all share a pattern. They start with a few early adopters, spread as people see friends adopting, and may sweep the population contagiously, with the dynamics of an epidemic.

Diffusion of innovations became a sociological field in the mid-20th century. It was first empirical (Coleman, Rogers). In the 1970s, Schelling and Granovetter introduced mathematical models. Models matter for three reasons:

1. to understand how spreading works;
2. to predict success or failure early;
3. to shape the process, increasing (or reducing) the chance of success.

The running scenario: an old behaviour $A$ and a new behaviour $B$ competing on a social network. The applications are viral marketing and online communities (LiveJournal).

---

Networked coordination games

Why coordination? The benefit of a new behaviour often grows with how many of your contacts use it: compatible technologies, shared practices, similar opinions. Self-interest then says adopt once enough neighbours have.

Contagion and the contagion threshold

Dynamics. Every node updates simultaneously at $t = 1,2,\dots$, best-responding to its neighbours’ current behaviour. If $S$ is the initial set of $B$-adopters:

• $h_q(S)$ is the set of $B$-adopters after one round;
• $h_q^k(S)$ is the set after $k$ rounds.

This is nonprogressive: nodes may switch back, so $S \not\subseteq h_q(S)$ in general.

graph LR
  A2["-2: A"] --- A1["-1: B"]
  A1 --- Z["0: B"]
  Z --- P1["1: B"]
  P1 --- P2["2: A, next to switch"]

Many simple graphs have threshold $1/2$, and none seems to exceed it. Is there a graph with contagion threshold above $1/2$?

Progressive vs nonprogressive

Intuitively, progressive spread should be easier, because early adopters can’t defect and kill the cascade. Surprisingly, it isn’t:

ProofRun the progressive process until it engulfs the seed’s neighbourhood

Easy direction. A set contagious under $h_q$ is contagious under $\bar h_q$, since progressive dynamics only keep more nodes on $B$.

Step 1: Enlarge the seed. Let $S$ be contagious under $\bar h_q$, and let $\hat S = S\cup N(S)$, which is finite because degrees are finite. Since $\bar h_q^k(S)$ eventually covers everything, some $\ell$ has $\bar h_q^\ell(S)\supseteq \hat S$. Set $T = \bar h_q^\ell(S)$.

Step 2: A useful identity (left as an exercise; induction on $j$): $$\bar h_q^j(X) = X \cup h_q\big(\bar h_q^{j-1}(X)\big). \tag{24.1}$$ Every node that joined $\bar h_q^{j-1}(X)$ after the start did so with at least a $q$ fraction of its neighbours already in, and those neighbours are still in.

Step 3: The "$S\cup$" becomes redundant. Write $S_j = \bar h_q^j(S)$. For $j > \ell$, $S_j = S\cup h_q(S_{j-1})$. But $S_{j-1}\supseteq T\supseteq N(S)$, so every node of $S$ has all neighbours on $B$ and is in $h_q(S_{j-1})$. Hence $S_j = h_q(S_{j-1})$.

The key step: by induction, $h_q^{j-\ell}(T) = S_j$ for all $j > \ell$. So $T$ is contagious under the nonprogressive rule. Once the seed is surrounded, nobody in it ever wants to revert.

∎

No graph beats 1/2

ProofThe cut size is a strictly decreasing potential

By Theorem 24.1 it suffices to consider the progressive process. Fix $q > 1/2$ and a finite $S$, and let $S_j = \bar h_q^j(S)$. For a set $X$, let $d(X)$ be the number of edges leaving $X$. This is a natural number for finite $X$.

Step 1: Each growth step shrinks the cut. Suppose $S_{j-1}\subsetneq S_j$ and $v\in S_j\setminus S_{j-1}$. Then $v$‘s edges into $S_{j-1}$ leave the cut, and its edges into $V\setminus S_j$ join it. Edges between two new nodes are in neither cut. Since $v$ switched with $q > 1/2$, $$e(v, S_{j-1}) > \tfrac12 d_v > e(v, V\setminus S_j).$$ Summing over new nodes, $d(S_j) < d(S_{j-1})$.

Step 2: A natural number can’t decrease forever. So the sets stop growing at some finite $S_k$. The graph is infinite, so $S$ is not contagious.

∎

---

General models of social contagion

The first model has one threshold for everyone and equal weight on every neighbour. Real populations are heterogeneous. From here on:

• graphs may be finite or infinite, and are directed (influence need not be symmetric; $w$ is a neighbour of $v$ if $(w,v)\in E$);
• processes are progressive, with a reduction for the nonprogressive case at the end;
• a node on $B$ is active, and switching to $B$ is being activated.

DerivationThe two translations

Threshold → Cascade. If $X$ has tried and failed, then $\theta_v\in(g_v(X), 1]$, uniformly. $u$ succeeds iff $\theta_v \le g_v(X\cup\{u\})$: $$p_v(u,X) = \frac{g_v(X\cup\{u\}) - g_v(X)}{1 - g_v(X)}.$$

Cascade → Threshold. $v$ survives attempts by $X = \{u_1,\dots,u_k\}$ with probability $\prod_i(1 - p_v(u_i, X_{i-1}))$, where $X_{i-1} = \{u_1,\dots,u_{i-1}\}$. Order-independence makes this well-defined, so $$g_v(X) = 1 - \prod_{i=1}^k\big(1 - p_v(u_i, X_{i-1})\big).$$

Three special cases

Case	Incremental function	Character
(i) $k$-threshold	$p_v(u,X) = 1$ if $\lvert X\rvert = k-1$, else $0$	critical mass: nothing until the $k$-th exposure
(ii) diminishing returns	$p_v(u,X) \ge p_v(u,Y)$ whenever $X\subseteq Y$	each extra exposure is worth less
(iii) Independent Cascade	$p_v(u,X) = p_{uv}$	a special case of (ii)

Nonprogressive via progressive (Kempe et al.)

graph LR
  U1["u in layer 1"] --> V2["v in layer 2"]
  W1["w in layer 1"] --> V2
  U2["u in layer 2"] --> V3["v in layer 3"]
  W2["w in layer 2"] --> V3

---

Finding influential sets of nodes

Applications.

• Viral marketing: use word of mouth to stretch a limited advertising budget. It is especially powerful online, with easy sharing and rich customer data.
• News and blog tracking: stories spread in waves through mainstream outlets and blogs, and online data lets tools follow them in real time.

Component	Detail
Signature	$f : 2^V \to [0, n]$
Domain	a seed set of initial adopters
Codomain	expected final cascade size
Property	monotone, with $f(\emptyset) = 0$

Submodularity and greedy seeding

Local diminishing returns implies global submodularity

The general proof is intricate. The special case is clean:

ProofLive-edge decomposition into size-of-union functions

Step 1: Two facts about submodularity.

• A nonnegative combination $\sum_i c_if_i$ of submodular functions is submodular.
• A size-of-union function $f(X) = |\bigcup_{i\in X} C_i|$ is submodular: adding $C_v$ gains $|C_v\setminus\bigcup_{i\in X}C_i|$, which can only shrink as $X$ grows.

Step 2: Flip all coins in advance. Instead of flipping $u$‘s coin for edge $(u,v)$ when $u$ activates, flip a $p_{uv}$-coin for every edge up front and consult it only if needed. This gives the same distribution. Let $\alpha$ range over the $2^m$ outcomes. Edges whose coin came up heads are live.

Step 3: Fixed coins give reachability. With outcome $\alpha$, a node ends up active iff it is reachable from $S$ by live edges. With $R^\alpha_s$ the set of nodes live-reachable from $s$, $$f_\alpha(S) = \Big|\bigcup_{s\in S} R_s^\alpha\Big|,$$ a size-of-union function, hence submodular.

The key step: $$f(S) = \sum_\alpha \Pr[\alpha]\,f_\alpha(S)$$ is a nonnegative combination of submodular functions, so it is submodular. The trick is to decompose an intractable $f$ into tractable pieces rather than attack it directly.

∎

How far does it generalize?

• Diminishing-returns $p_v$ translate into submodular $g_v$. The converse fails: some submodular $g_v$ translate into $p_v$ without diminishing returns.
• The Linear Threshold Model is such a case. It is not a diminishing-returns cascade, yet its $f$ is still submodular, by a separate analysis.
• So “General Threshold with submodular $g_v$” is strictly more general, and it too gives submodular influence:

Another lever: targeting edges

---

Empirical evidence from online communities

Classical diffusion studies are rich but small: too small to estimate, for example, how adoption probability depends on the structure of one’s neighbourhood. Large online datasets change this.

---

Quick reference

Object	Statement	Note
Coordination game	payoffs $q$ ($AA$), $1-q$ ($BB$), $0$ (mismatch)	summed over edges
Threshold rule	adopt $B$ iff $d_v^B \ge q\,d_v$	small $q$ spreads easily
Contagious set	converts every node eventually	countably infinite graph, finite degrees
Contagion threshold	max $q$ with a finite contagious set	topology only
Infinite path	threshold $1/2$; seed $\{0,1\}$ works	$\{0\}$ dies out
Progressive step	$\bar h_q(Y) = Y\cup h_q(Y)$	no reverting
Thm 24.1	finite contagious set: progressive ⟺ nonprogressive	engulf the seed’s neighbourhood
Identity (24.1)	$\bar h^j(X) = X\cup h(\bar h^{j-1}(X))$	exercise
Thm 24.2	contagion threshold $\le 1/2$	cut size strictly decreases
Linear Threshold	activate if $\sum_{\text{active}} b_{vw}\ge\theta_v$, $\theta_v\sim U[0,1]$	$\sum_w b_{vw}\le1$
General Threshold	activate if $g_v(\text{active})\ge\theta_v$	$g_v$ monotone
Cascade Model	one attempt; success $p_v(u,X)$	order-independent
Threshold → Cascade	$p_v(u,X) = \frac{g_v(X+u)-g_v(X)}{1-g_v(X)}$
Cascade → Threshold	$g_v(X) = 1 - \prod(1 - p_v(u_i,X_{i-1}))$
$k$-threshold	$p_v = 1$ iff $\lvert X\rvert = k-1$	critical mass
Diminishing returns	$p_v(u,X)\ge p_v(u,Y)$ for $X\subseteq Y$
Independent Cascade	$p_v(u,X) = p_{uv}$
Time-layered graph	$T$ copies; edges $u^{i-1}\to v^i$	nonprogressive → progressive
Influence max	$\max_{\lvert S\rvert = k} f(S)$	NP-hard; $n^{1-\epsilon}$-inapproximable in general
Submodularity	marginal gains shrink as the set grows
Thm 24.3	greedy $\ge(1-1/e)$ OPT	monotone submodular
Thm 24.4	diminishing-returns $p_v$ ⇒ $f$ submodular	local → global
Thm 24.5	Independent Cascade ⇒ $f$ submodular	live edges; size-of-union
Linear Threshold	$f$ submodular (separate proof)	not a DR cascade
Thm 24.6	submodular $g_v$ ⇒ $f$ submodular	Mossel–Roch
Recommendation incentives	target edges, not nodes	theory open
LiveJournal $P(k)$	$\approx\epsilon\log k$; $P(2) > 2P(1)$	diminishing returns plus a small critical-mass bump
Friend connectedness	denser friend sets raise joining	unmodelled

Facts to keep to hand

• Critical mass versus diminishing returns is the axis of the chapter. It separates the $n^{1-\epsilon}$-hard knife-edge instances from the $(1-1/e)$-approximable ones. It is also the question the LiveJournal data answer: mostly diminishing returns, with a small critical-mass bump at $k = 2$.
• Local rules decide global properties. Majority thresholds cap contagion at $1/2$. Diminishing returns at every node give submodular influence for the whole network. Both results turn a per-node condition into a network-wide guarantee.
• Potential arguments again. Theorem 24.2 is a potential-function proof: the cut size strictly decreases, just like the potentials in network-formation-games and the routing chapter.
• Decompose the intractable into the tractable. $f$ can’t be evaluated exactly, but fixing randomness in advance (live edges) writes it as an average of reachability functions, each obviously submodular.
• Submodularity recurs across these notes. Submodular games make Shapley shares cross-monotone (cost-sharing). Submodular welfare gives utility games PoA 2 (network-formation-games). Submodular influence makes greedy seeding $(1-1/e)$-optimal. In each case diminishing returns is what makes local or greedy reasoning safe.
• Surround the seed. Theorem 24.1’s trick: once the adopters include every neighbour of the original seed, no one inside has a reason to revert, so nonprogressive spread behaves like progressive spread.
• Scale buys smoothness, not meaning. Online data give clean aggregate curves at the cost of knowing what links mean or when decisions happen. Connecting snapshot aggregates to operational node rules is open.

References

• Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 24 (Kleinberg)