Processes on A Network: Diffusion
IV124
Josef Spurný & Eva Výtvarová
Faculty of Informatics, Masaryk University
May 12, 2023
Diffusion
Processes on Networks: Diffusion
Similar principles in different contexts
Technical networks: cascading failures
Biological networks: epidemics
Social networks: opinion formation, information spreading
Today: models of these processes.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 2 / 31
Diffusion
Diffusion: Basic Concepts and Principles
Components of the model
What is spreading: infection, information, choice, etc.
Time-point of spread: change of choice, infection, failure, etc.
Outcome: epidemic, group-decision, excluded nodes, etc.
We consider a discrete time domain – the model evolves in iterative
steps. We model a dynamic process on a static network.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 3 / 31
Diffusion
Cascade on a Network
One run of the model on a network forms a directed graph –
a cascade.
1
1
Leskovec CS224W: Machine Learning with Graphs
http://web.stanford.edu/class/cs224w/
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 4 / 31
Diffusion
Forms of Diffusion/Infection
Simple spreading
Each node infects its neighbors with a certain probability at each
step
Complex spreading
Spreading occurs only if a certain fraction of neighboring nodes
are infected
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 5 / 31
Complex Spreading
Coordination Game on a Network
Task:
Choose between A and B (e.g., VHS vs. Betamax, iPhone vs.
Samsung)
Rewards for neighboring nodes u and v:
Both A: payoff a > 0
Both B: payoff b > 0
Disagreement: no payoff
Each node plays on its own. Spreading is monotonic (nodes do not
take their decision back).
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 6 / 31
Complex Spreading
Threshold for Changing Decision
2
2
Kleinberg, ch. 19.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 7 / 31
Complex Spreading
Threshold for Changing Decision
A is a better choice if
pda ≥ (1 − p)db
Thus:
p ≥
b
a + b
= q
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 8 / 31
Complex Spreading
Coordination Game - Properties
Equilibrium states:
Everyone chooses A
Everyone chooses B
Incomplete cascade
The initiation of a cascade depends on the topology of the network,
initial conditions, and the value of q.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 9 / 31
Complex Spreading
Cascades vs. Clusters
Clusters represent an obstacle for cascades
dense internal connectivity
small number of edges to the rest of the graph
Density ρ of cluster C ⊆ G:
each node u ∈ C has at least fraction ρ of edges in C
Cascades vs. density:
cascades cannot propagate to clusters with ρ > (1 − q)
conversely: if the cascade stops, there is a cluster in the graph
with ρ > (1 − q)
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 10 / 31
Complex Spreading
Cascades vs. Weak Ties
Reminder: weak ties are bridges between communities
Role in cascades
key for information diffusion (e.g. awareness of innovation)
impenetrable to higher threshold phenomena (e.g. actual
adoption of innovation)
e.g. rapid global dynamics of sharing on social networks vs. slow
and local dynamics of political mobilization
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 11 / 31
Complex Spreading
Extensions to Coordination Game
Bilingual nodes
a node can choose state AB
reward AB-A: a
reward AB-B: b
reward AB-AB: max(a, b)
nodes choosing AB additionally pay fixed cost c
Heterogeneous thresholds
allows to incorporate differences in susceptibility
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 12 / 31
Complex Spreading
Netlogo Demo
...
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 13 / 31
Models of Spreading
Models of Spreading: Epidemics
So far: Complex spreading
Spreading via the majority of neighbors
Sociological applications
Now: Simple spreading
Stochastic model
Applications in biological and technical networks
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 14 / 31
Simple Spreading
Note on Stochastic Models
Simple deterministic models can be made more complex (by adding
rules)
Increases the range of possible behaviors
Analysis becomes more demanding
At some point, it becomes easier to summarize a large number of
real-world events into a single variable
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 15 / 31
Simple Spreading
Branching Processes
The simplest tree model
Patient zero enters population and meets k individuals
Probability of transmission upon meeting is p
k and p remain constant in every subsequent wave
Results in a tree of contacts between potentially infected
individuals and the subtree of actual infection
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 16 / 31
Simple Spreading
3
3
Easley and Kleinberg 2010
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 17 / 31
Simple Spreading
Branching Processes
Possible outcomes
Infection stops after a while (dies out)
Large epidemic
Reproduction number R0
Expected number of new infections caused by a single individual
Describes the viability and aggressiveness of the infection
Here, R0 = pk
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 18 / 31
Simple Spreading
Branching Processes
Development depending on R0:
R0 ≪ 1: rapid end of spread
R0 ≫ 1: aggressive epidemic
R0 ≈ 1: the extent of the infection can vary significantly between
runs; even small changes in the spread mechanism determine
the outbreak of the epidemic
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 19 / 31
Simple Spreading
SIR Model
Three consecutive states of a node:
1. Susceptible: susceptible to infection from neighbors
2. Infectious: infected node spreading the disease for tI steps
3. Removed (Recovered): immune/dead node
In each step, nodes in state I transmit the disease to all their
neighbors with probability p.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 20 / 31
Simple Spreading
Classic Epidemiological Models: SIR model
Assumes possible contact between subject and any other population
member. Defined by differential equations:
a
a
Luz, P., et al (2010)
dS
dt
= −
βSI
N
dI
dt
=
βSI
N
− γI
dR
dt
= γI
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 21 / 31
Simple Spreading
SIR vs. Networks4
4
Keeling & Eames 2005
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 22 / 31
Simple Spreading
SIR vs. Networks5
5
Keeling & Eames 2005
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 23 / 31
Simple Spreading
SIR Model: Extensions
The dynamics are simple (branching process on a network)
Possible extensions:
Weighted graph: non-homogeneous transmission probability p
Non-homogeneous It
Division of I into more detailed categories: infectious incubation,
less infectious period with symptoms, ...
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 24 / 31
Simple Spreading
SIS Model
We allow for repeated infection.
1. Susceptible: susceptible to infection from neighbors
2. Infectious: infected node spreading infection for tI steps
3. Susceptible
Compared to the SIR model, SIS allows for very long runs on a finite
network.
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 25 / 31
Simple Spreading
SIRS Model
In the occurrence of real diseases, we observe significant oscillations,
which are not captured even by the SIS model.
We add time-limited immunity.
1. Susceptible: susceptible to infection from neighbors
2. Infectious: infected node spreading infection for tI steps
3. Recovery: recovered and immune node for tR steps
4. Susceptible
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 26 / 31
Simple Spreading
Global vs. Local Oscillations
SIRS exhibits local oscillations on a general network.
Global oscillations
require homophilic (local) links and long-range shortcuts
correspond to the characteristic of small worlds
the specific dynamics is closely related to the network topology
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 27 / 31
Simple Spreading
SIRS and Small Worlds
Small-world Watts-Strogatz network model (reminder):
ring with local connections; with probability c, the edges are
rewired to a random target
SIRS dynamics
global oscillations (synchronization) depend on the number of
shortcuts – weak links
small c – local infection, large c – global oscillations
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 28 / 31
Simple Spreading
SIRS and Small Worlds
6
6
Kiperman et al. 2001
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 29 / 31
Simple Spreading
Demos
...
J. Spurný, E. Výtvarová ·Diffusion ·May 12, 2023 30 / 31