# A Simple Model of Global Cascades on Random Networks

31 Aug 2016 | complexity science network science scientific paper notes paper reviewDuncan J Watts wrote a paper that was published in 2002 titled “A simple model of global cascades on random networks” in the Proceedings of the National Academy of Sciences (PNAS). It’s a seminal paper in my current work on information diffusion in (social) networks. Watts shows how the interactions between local dependencies, fractional threshold, and heterogeneity relate to information cascades in networks. My work builds on these ideas, so it’s important to have a strong understanding of the terms and model specifications outlined in the paper.

I’ve been working with my Masters and Doctoral advisor, Mark Orr on a simulation platform that incorporates artificial neural networks within an agent-based simulation. The project is called “Multi-Agent Neural Network” (MANN) and it was my first open source project; the code can be found in two parts:

I’m currently working on a refactoring a lot of the old code here:

# The paper

*These are my notes on the paper. In no way shape or form am I claiming the content below as my own work, it all comes from the paper*

*Binary decisions with externalities* is a general class of problems
that can be used to model a wide variety of real-world problems.

- Cascades limited by connectivity
- Connectivity can play a role in global cascades.
Fewer connections mean a lesser chance of information spreading within a network.
The abstract references
- power law
- cluster size distribution in standard percolation theory
- avalanches in self-organized criticality

- Connectivity can play a role in global cascades.
Fewer connections mean a lesser chance of information spreading within a network.
The abstract references
- Cascades limited by local stability
- When a network is highly connected, cascades will occur when a threshold number of connected nodes incorporate the information. Additionally, these types of networks have a bimodal distribution of a global cascade, either one will happen or it will not.
- When the
*threshold*of agent’s to incorporate a bit of information is heterogeneous, the entire system has a higher chance of a global information cascade.- When the agent’s threshold is heterogeneous, the ones who
have a lower threshold are
*more**vulnerable*.

- When the agent’s threshold is heterogeneous, the ones who
have a lower threshold are
- Conversely, when the
*degree*distribution is heterogeneous, the system is less likely to have a information cascade.- When an agent’s degree centrality is heterogeneous, the ones
who have a higher degree will be
*less*vulnerable.

- When an agent’s degree centrality is heterogeneous, the ones
who have a higher degree will be

The model Watts outlines has 3 unique features:

- local dependencies
- fractional thresholds
- heterogeneity

Network heterogeneity and threshold heterogeneity are not equivalent.

Goals of the paper:

- Probability of a global cascade from a single node

# Definitions

**cascade**: event of any size triggered by an initial seed**global cascades**: a cascade that occupies a finite fraction of an infinite network. A sufficiently large cascade. More than a fixed fraction of a large, but finite network.**diffusion****random network****agents**: nodes of a network**neighbors**: all relevant incoming signals to an agent (usually other agents who have a directed edge to the agent in question)**connectivity****power law distribution****cluster size****local stability****$\phi$**: threshold**$f(\phi)$**: distribution where $\phi$ is drawn from- unit interval and normalized such that the area under the distribution is 1

**$n$**: number of agents in the network**$k$**: number of neighbors each agent is connected to**$p_k$**: probability of an agent being connected to $k$ neighbors (degree distribution)**$z$**: average number of neighbors $\langle k \rangle$ (coordination number)

**$\phi_0$**: the number of agents that are seeded with 1 at the start of the simulation- $\phi_0 \ll 1$
- See definition on
*small seed*

**vulnerable vertex**: an agent that has a small threshold ($\phi \le \frac{1}{k}$) or has a degree, $k$ such that $k \le K = [\frac{1}{\phi}]$- $\rho_k$: probability that an agent with degree $k$ is vulnerable
- $\rho_k = P[\phi \le \frac{1}{k}]$

- $\rho_k$: probability that an agent with degree $k$ is vulnerable
**stable vertex**: one that is not vulnerable. Stable vertices do not flip states at the start of a simulation**small seed**: three orders of magnitude less than the system size, $n$**innovator**: an agent that is seeded**early adopter**: a vulnerable agent**early and late majority**: agents who can be influenced if exposed to multiple early adopters

# Model Specification

## How the Simulation runs

- $n$ agents in a network start off with a state of 0
- Individual agents can only have a state that is either 0 or 1
- Each agent has $k$ neighbors
- An agent gets a new state of 1, if a fraction of its neighbors, $\phi$ are also 1.
- Otherwise an agent gets a new state of 0.

- During each time step, the population evolves:
- Update states in random, asynchronous order using the threshold rule
- Once an agent has a state of 1, it will stay at 1 for the remainder of the simulation

## How the model is parameterized

- $\phi$ and $k$
*may*be heterogeneous- To simplify the simulations, the paper has a homogeneous threshold, $\phi$
- $f(\phi) = \delta(\phi - \phi_*)$

- To simplify the simulations, the paper has a homogeneous threshold, $\phi$
- The network is a uniform random graph
- A small seed
- Any pair of vertices is connected with probability $p = \frac{z}{n}$
- in uniform random graphs $p_k = \text{the Poisson distribution}$

- $n = 10,000$
- 100 random runs of each simulation

## Values used in figures

### Fig 1

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/figure/F1/

Shows for a given threshold, $\phi$ and average number of neighbors, $z$, where the cascade condition is satisfied. This is an analytical solution, not a simulated solution

- $\phi$: range from 0.10 to 0.25 in increments of 0.01
- $z$: range from 0 to 15

### Fig 2

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/figure/F2/

Looking at a specific threshold value, $\phi = 0.18$

- $n$ = 10,000
- 1,000 random realizations of the network and initial conditions

### Fig 3

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/figure/F3/

a log-log plot of the cascade size vs cumulative distribution

### Fig 4

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/figure/F4/

## Comments