# Chapter 19. Cascading Behavior in Networks

[TOC]

## 19.1 Diffusion in Networks
- choice depends on others' choices
- global
- neighbor
- social network
- the diffusion of innovations
- spread of new idea
- behaviors
- opinions
- technologies

## 19.2 Modeling Diffusion through a Network
Let
- $G$ be a simple graph of network
- a game table between neighbors
- strategy for each node

Then the payoff of a node $v$ is sum of the payoff of all game with its neighbors.

### Threshold
Assume node $v$ has $d$ neighbors, a fraction of $p$ of them are $A$, then $v$ prefer $A$ if
$$
pda\geq (1-p)db
$$
That is
$$
p\geq\frac{b}{a+b}
$$

### Cascading Behavior
Assume initially all of nodes are $B$, and especially change some of them into $A$, then some of the other nodes will follow them to be $A$.

### Complete Cascade

Assume $a=3,b=2$, then threshold $q=\frac{2}{5}$.

### Viral Marketing
| Initial | Eventual |
| -------- | -------- |
|  | 

- change $a$ to be $4$
- convince node $12$ and $13$

## 19.3 Cascades and Clusters
:::success
**A cluster of density p**
For a cluster, $p = \min_{each\space node\space n} \{\frac{\sharp ( neighbors\space of\space n\space \in \space cluster)}{\sharp ( neighbors\space of\space n)} \}$
A set of nodes such that each node in the set has at least a fraction $p$ of its network neighbors in the set.

:::

### The Relationship Between Clusters and Cascades.
- $q=\frac25$
- *remaining network*: all nodes other than initial adopters.
- **Claim**: Consider a set of initial adopters of behavior $A$, with a threshold of $q$ for nodes in the remaining network to adopt behavior $A$.
- Remaining network contains a cluster of density $\gt 1 − q\space \Leftrightarrow$ The set of initial adopters will not cause a complete cascade.
- Figure19.7 $1-q=\frac{3}{5}=\frac{9}{15}\lt \frac{10}{15}=\frac{2}{3}$

### Part (i): Clusters Are Obstacles to Cascades
**Show**: Consider behavior $A$ is spreading with threshold $q$. Suppose that the remaining network contains a cluster of density $\gt 1 − q$. We now argue that no node inside the cluster will ever adopt $A$.
**Proof by contradiction**:
- Let node $v$ in the cluster that adopts $A$ at time $t$.(earliest)
- Its decision was based on the set of nodes who had adopted $A$ at time $t − 1$.
- Since no node in the cluster adopted before $v$ did, the only neighbors of $v$ that were using $A$ before $t$ were **outside** the cluster.
- But since the cluster has density $\gt 1 − q$, hence less than a $q$ fraction of $v$’s neighbors are outside the cluster.
- less than a $q$ fraction of $v$’s neighbors are using $A$, a contradiction.
### Part (ii): Clusters Are the Only Obstacles to Cascades
**Show**: Whenever initial adopters fails to cause a complete cascade with threshold $q$, there is a cluster in the remaining network of density $\gt (1 − q)$.
- It stops because there are still nodes using $B$, but none of the nodes in this set want to switch
- Proof:
- Let $S$ denote the set of nodes using $B$ eventually.
- To show: $S$ is a cluster of density $\gt 1 − q$
- Consider any node $w$ in $S$.
- Since $w$ doesn’t want to switch to $A$, it must be that the fraction of its neighbors using $A$ is less than $q$
- Hence, the fraction of its neighbors using $B$ is greater than $1 − q$.
- But all nodes using $B$ belong to the $S$, so the fraction of $w$’s neighbors belonging to $S$ is greater than $1 − q$.
- $S$ is a cluster of density $\gt 1 − q$.
## 19.4 Diffusion, Thresholds, and the Role of Weak Ties
- learn from studying diffusion: learning vs actually adopt
- 
- 
- bridges and local bridges
- good at conveying awareness of new things
- weak at transmitting risky or costly behaviors to adopt
- 
- a joke or an online video vs political mobilization

## 19.5 Extensions of the Basic Cascade Model
### Heterogeneous Thresholds
- 
- If $v$ has $d$ neighbors, of whom a $p$ fraction have behavior $A$ and a $(1 − p)$ fraction have behavior $B$, the payoff from choosing
- $A$: $pda_v$
- $B$: $(1 − p)db_v$
- Thus, $A$ is better if $p ≥ \frac{b_v}{a_v+b_v}$ (threshold)
- 
- blocking cluster
- Each node $v$ has more than a $1 − q_v(threshold)$ fraction of its friends also in the set.
- A set of initial adopters will cause a complete cascade iff the remaining network doesn't contain a blocking cluster.

## 19.6 Knowledge, Thresholds, and Collective Action

### Collective Action and Pluralistic Ignorance
- *collective action*
- An activity produces benefits only if enough people participate
- e.g. public demonstration against the government
- *pluralistic ignorance*
- people have wildly erroneous estimates about the prevalence of certain opinions in the population at large
- e.g.
- a central authority is actively working to restrict information
- 1970 US racial segregation
### A Model for the Effect of Knowledge on Collective Action
- each person knows the thresholds of all her neighbors

- Social networks have the effect not just of transmitting a message, but of making people realize that many others have gotten the message as well(common knowledge).
## 19.7 Advanced Material: The Cascade Capacity

:::info
Definition:
* *Cascades Capacity*: The **largest** value of the threshold for some finite set of early adopters that can cause a complete cascade.
(If threshold is greater *Cascades Capacity* it cannot cause a complete cascade.)
:::

### A. Cascades on Infinite Networks

A network be modeled as a connected graph on an infinite set of nodes,
but each node is only connected to finite number of other nodes.

Examples
It's obvious that the *cascades capacity* is $1 \over 2$
It's obvious that the *cascades capacity* is $3 \over 8$

### B. How Large Can the Cascade Capacity Be?

Claim: There is no network in which the cascade capacity exceeds $1 \over 2$

We are showing that if threshold $q > {1 \over 2}$, then it will not cause a complete cascade.

#### Analyzing the Interface
:::info
Notations.
* $A$-$A$ edge: edge connects two adopter of $A$
* $B$-$B$ edge: edge connects two adopter of $B$
* $A$-$B$ edge: edge connects an adopter of $A$ to an adopter to $B$
* Interface: A set of $A$-$B$ edges
:::
Notice that the size of Interface is finite, because there is some finite set of initial adopters, and each of them has a finite set of neighbors, the set of $A$-$B$ edges is finite.

Example

#### The Size of the Interface Decreases in Each Step

When $q > {1 \over 2}$, consider a node $w$ switches from $B$ to $A$, then
1. The edges to nodes that remain with $B$ change from $B$-$B$ edges to $A$-$B$ edges
2. The edges to nodes that were already with $A$ change from $A$-$B$ edges to $A$-$A$ edges
3. By above two observation and the fact that $q > {1 \over 2}$,
there are more edges changing from $A$-$B$ to $A$-$A$ than changing from $B$-$B$ to $A$-$B$.
(i.e. More edges leaving the interface than joining the interface.)

| Before $w$ and $v$ adopt $A$ | After $w$ and $v$ adopt $A$ |
|:------------------------------------:|:------------------------------------:|
|  |  |

Thus, the size of interface is strictly decreasing.
What's more, since the size of the interface is finite as mentioned above,
the spread of $A$ will eventually be terminated as the size of the interface goes to $0$

### C. Compatibility and its Role in Cascades

Bilingual: Adopting both $A$ and $B$

#### Modeling the Bilingual Option

* Now there are three strategies: $A$, $B$ and $AB$
* Payoff matrix

| | A | B | AB |
|:---:|:----:|:----:|:--------------------:|
| A | a, a | 0, 0 | a, a |
| B | 0, 0 | b, b | b, b |
| AB | a, a | b, b | max(a, b), max(a, b) |

It's easy to see that $AB$ is a dominant strategy.
But now we incorporate the notion that bilinguality come with a cost:
the payoff of a node which choosing strategy $AB$ has to minus a cost $c$

| | A | B | AB |
|:---:|:--------:|:--------:|:----------------------------:|
| A | a, a | 0, 0 | a, a - c |
| B | 0, 0 | b, b | b, b - c |
| AB | a - c, a | b - c, b | max(a, b) - c, max(a, b) - c |

Example.

At last, B will be completely abandoned

#### When do Cascades Happen on an Infinite Path

Recall what Infinite path looks like.

We now interest in with the strategy $AB$ is added, when do Cascades will happen?

First things first, we re-scale the payoff of strategy $B$ to $1$ in order to make it simple.

| Case1. |  |  |
|:-------:|:------------------------------------:|:------------------------------------:|
| Case2. |  |  |

`All in all.`