A Simple Model of Global Cascades on Random Networks
By Daniel Chen
August 31, 2016
Duncan 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 agentbased simulation. The project is called “MultiAgent 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 realworld 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 selforganized 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.
 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.
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
 $f(\phi)$: distribution where $\phi$ is drawn from
 $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: 10. Update states in random, asynchronous order using the threshold rule 20. 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}$ 10. 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 loglog plot of the cascade size vs cumulative distribution
Fig 4
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC122850/figure/F4/
References
http://www.ncbi.nlm.nih.gov/pubmed/16578874
 Posted on:
 August 31, 2016
 Length:
 5 minute read, 924 words