�

Fiona Sloothaak

​

SNAPP seminar, 24 October 2022

Emergence of Heavy Tails in Stochastic Networks through Cascading Failures

Cascading failures

Cascading failures in different application areas

Computer networks

Avalanche dynamics

Material sciences

Power grids

Cascading failures (idea)

Cascading failures (idea)

• Limited capacity

Cascading failures (idea)

• Limited capacity

​

• Loaded components

Cascading failures (idea)

• Limited capacity

​

• Loaded components

​

• Initial disturbance

Cascading failures (idea)

• Limited capacity

​

• Loaded components

​

• Initial disturbance

Cascading failures (idea)

• Limited capacity

​

• Loaded components

​

• Initial disturbance

Key interest: failure size, e.g.

• # failed edges/components
• amount of lost flow/load
• and more….

Heavy tails are undesirable

Problematic when failure sizes are heavy-tailed !

Pareto

Exponential

Large-sized failures are no longer virtually impossible events!

Heavy tails are undesirable

Problematic when failure sizes are heavy-tailed !

Hines, Apt and Talukdar (2009)

Heavy tails are undesirable

Problematic when failure sizes are heavy-tailed !

WHY and HOW?

Remainder of talk

​

• Provide a (non-exhaustive) list of explanations why heavy tails emerge

​

• Illustrate how emerge in stochastic networks through cascading failures�(several examples from literature)

​

• New possible directions

Emergence of Heavy Tails

Explanations why heavy tails emerge

Random walks

Generalized CLT

Generalized CLT

Background:

• Lévy (1924)
• Embrechts, Klüppelberg and Mikosch (Section 2.2, 1997)
• Nair, Wierman and Zwart (Chapter 5, 2022)

First-passage time for RWs

First-passage time for RWs

First-passage time for RWs

Background:

• Donsker (1951), Skorokhod (1957)
• Doney (2012)
• Denisov and Shneer (2013), Aurzada and Kramm (2016)

Explanations why heavy tails emerge

Random walks

Phase transitions

Phase transition (branching process)

Explanations why heavy tails emerge

Kesten’s recursive relation

Random walks

Phase transitions

Explanations why heavy tails emerge

Random walks

Phase transitions

Kesten’s recursive relation

Background:

• Kesten (1973)
• Buraczewski, Damek and Mikosch (2016)

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Background:

• Barabási and Albert (1999)
• Van der Hofstad (2017)

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Exogenous factors

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Background:

Foss, Korshunov and Zachary (2013)

Exogenous factors

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Self-organized criticality

Exogenous factors

Heavy Tails in Cascading (Failure) Models

Self-Organized Criticality (SOC)

Self-Organized Criticality (SOC)

Wikipedia:

“Self-organized criticality (SOC) is a property of dynamical systems that have a critical point as an attractor. Their macroscopic behavior thus displays the spatial or temporal scale-invariance characteristic of the critical point of a phase transition, but without the need to tune control parameters to a precise value, because the system, effectively, tunes itself as it evolves towards criticality.”

​

Initiating work by: Bak, Tang and Wiesenfeld (1987)�

SOC: Abelian sandpile model on rectangular grid

3

1

2

3

2

2

1

3

3

3

2

2

3

1

1

3

2

0

3

2

3

2

2

2

2

Lost grains: 0

Each iteration:

1. Drop one grain u.a.r.

SOC: Abelian sandpile model on rectangular grid

3

1

2

3

2

2

1

3

3

3

2

2

4

1

1

3

2

0

3

2

3

2

2

2

2

Lost grains: 0

SOC: Abelian sandpile model on rectangular grid

3

1

2

3

2

2

1

4

3

3

2

3

0

2

1

3

2

1

3

2

3

2

2

2

2

Lost grains: 0

SOC: Abelian sandpile model on rectangular grid

3

1

2

3

2

2

1

4

3

3

2

3

0

2

1

3

2

1

3

2

3

2

2

2

2

Lost grains: 0

SOC: Abelian sandpile model on rectangular grid

3

1

3

3

2

2

2

0

4

3

2

3

1

2

1

3

2

1

3

2

3

2

2

2

2

Lost grains: 0

SOC: Abelian sandpile model on rectangular grid

3

1

3

4

2

2

2

1

0

4

2

3

1

3

1

3

2

1

3

2

3

2

2

2

2

Lost grains: 0

SOC: Abelian sandpile model on rectangular grid

3

1

3

4

3

2

2

1

1

0

2

3

1

3

2

3

2

1

3

2

3

2

2

2

2

Lost grains: 1

SOC: Abelian sandpile model on rectangular grid

3

1

4

0

4

2

2

1

2

0

2

3

1

3

2

3

2

1

3

2

3

2

2

2

2

Lost grains: 2

SOC: Abelian sandpile model on rectangular grid

3

2

0

1

4

2

2

2

2

0

2

3

1

3

2

3

2

1

3

2

3

2

2

2

2

Lost grains: 3

SOC: Abelian sandpile model on rectangular grid

3

2

0

2

0

2

2

2

2

1

2

3

1

3

2

3

2

1

3

2

3

2

2

2

2

Lost grains: 5

SOC: sandpile models

Heavy Tails in Cascading Failure Models

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Self-organized criticality

Exogenous factors

Heavy Tails in Cascading Failure Models

Relation to Random Walks

A basic cascading failure model

Background:

• CASCADE model (Dobson, Carreras and Newman, 2005)
• Sloothaak, Borst, Zwart (2018)

A basic cascading failure model

A basic cascading failure model

A basic cascading failure model

A basic cascading failure model

A basic cascading failure model

A basic cascading failure model

Background:

• Sloothaak, Wachtel, Zwart (2018)

First-passage time tail of a RW bridge

prefactor

Power-law exponent

First-passage time tail of a RW bridge

Normally distributed

First-passage time tail of a RW bridge

Additional note

Heavy Tails in Cascading Failure Models

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Self-organized criticality

Exogenous factors

Heavy Tails in Cascading Failure Models

Relation to Critical Branching Processes

Branching processes

• Classical setting well-understood

​

• Strand of literature that uses branching models with statistical analysis of historical and simulated blackout data (caused by cascading failures):
• Dobson, Carreras, Newman (2004)
• Kim and Dobson (2010)
• Kim, Wierzbicki, Dobson and Hardiman (2012)
• Qi, Dobson and Mei (2013)

Heavy Tails in Cascading Failure Models

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Self-organized criticality

Exogenous factors

Heavy Tails in Cascading Failure Models

Driven by exogenous factors

Scale-free behavior driven by exogenous factors

• Well-understood in certain areas (e.g. queueing, finance, etc.)

​

• Surprisingly, (relatively) unexplored in cascading failure analysis (e.g. blackout analysis)

Background:

• Nesti, Sloothaak, Zwart (2020)

SNAPP seminar by Bert Zwart

The cascading failure model

Model requires:

• Design stage (edge capacity limits)
• Operational stage (node supplies, flows)
• Emergency stage (initial disturbance, redirection of flow)

In our paper

Example (emergency stage)

Example (emergency stage)

Example (emergency stage)

Example (emergency stage)

Example (emergency stage)

Example (emergency stage)

Example (emergency stage)

Main result

Idea of proof

Heavy Tails in Cascading Failure Models

Explanations why heavy tails emerge

Kesten’s recursive relation

Network topology (e.g. preferential attachment)

Random walks

Phase transitions

Self-organized criticality

Exogenous factors

Another note

Naturally, many more cascading failure models exist:

• Epidemics models, e.g. (Pastor-Satorras and Vespignani, 2001), (Watts, 2002), (Morone and Makse, 2015) or (Hindes and Schwartz, 2016)
• Transportation systems, e.g. (Chakrabarti, 2006) or (Zheng, Gao, Zhao and Fu, 2008)
• Power transmission systems, see (Sun, Hou, Sun and Qi, 2019) for a textbook overview
• And many more notable works, e.g. (Motter and Lai, 2002), (Motter, 2004) or (Korkali, Veneman, Tivnan, Bagrow and Hines, 2017)

Key message: Despite the deceptively simple nature of cascading failures, these models capture essential features of failure processes in many settings that allows for a wide range of application areas. They can be used to study a vast collection of possible behaviors, and currently, many questions and directions remain unexplored.

Possible new directions

Possible new directions for final CF model

Key message: Scale-free nature of the input drives the scale-free tail behavior of the failure size. Internal dynamics only affects the prefactor.

​

​

​

How does it work for “scalable" graphs?

What if more constraints or dependencies exist?

What can we do to prevent large-scaled failures?