Complex Dynamical Networks: Lecture 6b: Network Robustness
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks
Percolation Theory
Percolation (渗流) theory studies clustering in complex networks
Example: Consider a cellular material (多孔材料). Can liquid flow from the top through to the bottom?
Describe the material by a 3D lattice
Percolation Theory
Mathematical framework: On an n × n × n lattice, for each pair of adjacent vertices (nodes), with a probability p connect them together (namely, with probability (1 − 𝑝), do not connect them).
Assume that all connection events are mutually independent.
Percolation Theory
Bond percolation (边渗流): as 𝑛 → ∞, for what values of p , there exists at least one path that allows the liquid to flow through?
The lower bound of 𝑝, denoted pc , is the percolation threshold
𝑝 < 𝑝𝑐 𝑝 = 𝑝𝑐 𝑝 > 𝑝𝑐
Random operation: Connect adjacent nodes with probability p (namely, not connecting with probability 1 − 𝑝)
Bond percolation: for what values of p , there exists at least one path that allows the liquid to flow through?
1D: Chain: 𝑝𝑐 = 1 2D: Lattice: 𝑝𝑐 = 0.5
1⁄2 are connected horizontally 1⁄2 are connected vertically
Inverse Problem: Given a lattice network
Edge-attack: with probability p , remove an edge (namely, with probability (1 − 𝑝), not remove it), such that the liquid cannot flow through the network
Robustness Problem 1:
For what range of p values, there exists at least one path?
Inverse Problem: Given a lattice network
Edge-attack: with probability p remove an edge (namely, with probability
(1 − 𝑝), not remove it), such that the liquid cannot flow through the network
Robustness Problem 2: For what range of
p values, the lattice remains to be connected
after being attacked?
Robustness Problem 3: After an attack, what is the size of the largest cluster (community)?
Example: (Erdos-Renyi random graph) 50 nodes, 116 edges, 𝑘 = 4.64
𝑝𝑐 = 0.25 Removed 29 edges (on average)
Above Graph: Even after removed 40 edges, the network remains to be connected, 𝑘 = 3.04
(Lada Adamic)
Site Percolation (点渗流 ):
Every node is “occupied” with probability p (namely, “not occupied”
with probability 1 − 𝑝). [“occupied”allowing liquid to pass]
If two adjacent nodes are both occupied, then connect them together by an edge.
Site Percolation (点渗流 ):
Problem 1:
For what range of 𝑝 values, there exist at least one path?
𝑝 < 𝑝𝑐 𝑝 = 𝑝𝑐
𝑝 > 𝑝𝑐
Giant Cluster appears
Problem 1:
For what range of 𝑝 values, there exist at least one path?
𝑝 < 𝑝𝑐 𝑝 = 𝑝𝑐 𝑝 > 𝑝𝑐
(Giant Cluster appears)
(Lada Adamic)
Percolation of General Complex Networks
Percolation concept can be extended to general complex networks
A network percolates if giant cluster(s) are emerged
A scale-free network always has giant cluster(s), so it always percolates
Average Degree can be used as a measure Example: Random Graph
ave deg = 0.99
ave deg = 1.18 ave deg = 3.96
Dual Lattice can be used as a framework Original Lattice Dual Lattice (Green color)
Dual Lattice can be used as a framework
Inverse Problem: Given a lattice network
Node-attack: With probability p remove a node (namely, with probability
(1 − 𝑝 ), not remove it), such that the liquid cannot flow through the network Robustness Problem 1:
For what range of 𝑝 values, there exist at least one path? Robustness Problem 2:
For what range of 𝑝 values, the lattice remains to be connected?
Robustness Problem 3:
After an attack, what is the size of the largest cluster?
Average size of giant clusters:
𝑠 ~|𝑝−𝑝𝑐|−𝛾 Constant 𝛾 is determined
by the network
𝑝 far from 𝑝𝑐 𝑠 small 𝑝near𝑝𝑐𝑠 large
(Barabasi, 2016 book)
Size of the largest cluster 𝑆∞ versus lattice size 𝐿 at 𝑝 = 𝑝𝑐
𝐷
𝐷 − dimension of lattice
𝑆~𝐿 ∞
Order Parameter:
Probability of a randomly picked cluster is a giant one:
𝑃 ~ ൝ 𝑝 − 𝑝𝑐 𝛽 𝑝 > 𝑝𝑐
∞
𝑝 = probability of occupying a
node
Constant 𝛽 > 0 is determined by the network
𝑝 ≫ 𝑝 𝑃 large(1) 𝑐∞
𝑝 ≪ 𝑝 𝑃 small(≈ 0) 𝑐∞
≈ 0 𝑝 ≤ 𝑝𝑐
Complementary Lattices
𝑝 1−𝑝
Order Parameter
(for Inverse Percolation) :
Probability of a randomly picked cluster is a giant one:
𝑓−𝑓 𝛽 𝑓<𝑓 𝑐𝑐
≈0 𝑓≥𝑓 𝑐
𝑓 = attacked nodes (𝑓 = 1 − 𝑝) Constant 𝛽 > 0 is determined
by the network 𝑓≪𝑓𝑃 large(1)
𝑃~൝ ∞
𝑐∞
𝑓≫𝑓𝑃 small(≈0) 𝑐∞
𝑃~𝑓−𝑓𝛽 ∞𝑐
Example: Wild fire spreads on a forest
Suppose a forest is a lattice, where each square has at most one tree. With probability 𝑝 ∈ 0,1 , place a tree into a square
One tree is on fired at random. This tree spreads fire to its neighboring trees (assuming the fire cannot spread over an empty square)
There exists a threshold value 𝑝𝑐
𝑝 < 𝑝𝑐 not many treesnot many threes were burn (black squares)
𝑝 = 𝑝𝑐
𝑝 > 𝑝𝑐 many trees many threes were burn (black squares)
(Barabasi, 2016 book)
Molloy-Reed Index
Condition for existence of giant cluster: 𝜅: = 𝑘2 > 2 𝑘
Interpretation: Consider a cluster of 𝑘 nodes, almost fully connected. Thus, everynodehasdegreeabout 𝑘−1,sotheclusterhas 1𝑘(𝑘−1)≈𝑘2 edges
Consider the average of all such large clusters, which has 𝑘2 edges 2
Define Ratio:
(Average total edge of a large cluster) / (Average total edge of a node in the cluster)
22
𝜅′:=
𝑘2 2
𝑘
(next page)
Molloy-Reed Index
Define a Ratio:
(Average total edge of a giant cluster) / (Average total edge of a node in the cluster)
𝑘2 2
𝑘
𝜅′:=
If 𝜅’ > 1, then 𝜅: = 𝑘2 𝑘
Because:
> 2condition for giant cluster to exist
= 2 𝑘 𝑘 ≈ 2 ring-shaped or chain-shaped
If 𝜅’ = 1, then 𝑘2
(far from being “almost fully connected” giant cluster)
If 𝜅’ < 1, then 𝑘 < 2star-shaped or broken pieces
(far from being “almost fully connected” giant cluster)
Random Graphs:
𝑘2 =𝑘(𝑘+1)
Interpretation:
Every node has degree 𝑘 , and every neighbor has degree 𝑘 total increasing degree is 𝑘2 − 𝑘
𝑘2 − 𝑘 𝑘
Since this is a linear growth: 𝑘2 − 𝑘 ~ 𝑘 𝑘
𝑘2 =𝑘(𝑘+1)
Increasing rate of total degree:
Molloy-Reed Index
Condition for existence of giant cluster:
For random networks 𝑘2 =𝑘(𝑘+1)
𝜅: = 𝑘2 𝑘
> 2
𝑘2 𝑘(𝑘 +1)
𝜅:= 𝑘 = 𝑘 = 𝑘 +1>2
𝑘>1
This is a (necessary) condition for giant cluster to exist
General Complex Networks
Molloy-Reed Index 𝑓=1−1
(R. Cohen, K. Erez, D. ben-Avraham and S. Havlin. Phys. Rev. Lett., 2000)
𝑐 𝑘2 −1 𝑘
where 𝑓 = attacked nodes, 𝑓 = threshold 𝑐
RandomNetworks: 𝑘2 =𝑘(𝑘+1)
Giant cluster
1 𝑘
𝑓→1 as𝑘→∞ 𝑐
𝑓=1− 𝑐
Giant clusters disappear
𝑓→1 as𝑘→∞ 𝑐
Scale-free Networks:
1
𝑘
𝑃 𝑘 𝑁
~ 𝑘−𝛾
𝑓=1−
𝑐 𝑘2 −1
(Barabasi, 2016 book)
Giant cluster
𝑓→1 as𝑘→∞ 𝑐
Giant Cluster
Scale-free networks has big nodes. If big nodes are attacked (removed), giant clusters will crash (disappear)
Random networks are relatively uniform, giant clusters will crash (disappear) gradually
Random network
𝑓𝑟𝑛
Scale-free network
(with different 𝛾)
Comparison
𝑠𝑓
𝑓𝑐 𝑐
Comparing Two Typical Attacks
Giant Cluster
Random attacks
(Random failures)
Targeted attacks
(Intentional removals)
𝑓𝑓 𝑐𝑐
Targeted attack Random attack
Attack Strategies
Summary
Random
Targeted
Random Networks
Low cost
High cost Low effect
Scale-free Networks
Low cost Low effect
High cost High effect
Network Topologies
(a) Centralized: Low cost, Fragale (b) Decentralized: Trade-off
(c) Distributed: High cost, Robust
(Barabasi Book)
Building Robust Networks
* Power grid * Internet service denials * Financial crisis * Traffic jams * … …
Power failures Data jams on Tritter Earthquakes
How to build robust power grid, Internet, transportation systems, … … ?
Criterion: Make its threshold as large as possible Recall:
Criterion: 𝑓𝑠𝑓 > 𝑓𝑟𝑛 𝑐𝑐
When designing a scale-free network, try to make its threshold larger than that of a random network
Giant Cluste r
𝑓𝑠𝑓 𝑐
𝑓𝑟𝑛 𝑐
Which One is Better?
Constraint: Low cost
min𝑓𝑡𝑜𝑡 =𝑓𝑟𝑎𝑛𝑑 +𝑓𝑡𝑎𝑟
𝑐𝑐𝑐
(tot = total, rand = random, tar = targeted)
This is an Optimization problem
Example: Optimization (of Robustness vs Cost)
More robust but More costly
END