Complex Dynamical Networks: Lecture 5: Spreading Dynamics
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks
Epidemic Spreading
Typically through contact
Diseases Spreading
In Human Society
新冠肺炎
COVID-19 @ Hong Kong
Example
Dengue Fever (登革熱)
Example
Dengue Fever
Example: H1N1
12
H1N1 Flu
Airport network Commuting network
Human Mobility Networks in Europe Data
H1N1 Flu
Human Mobility Networks in USA Data
Spanish Flu
1918 influenza pandemic (Jan. 1918 – Dec. 1920; known as Spanish Flu) was an unusually deadly influenza pandemic, the first of the two pandemics involving H1N1 influenza virus
It infected 500 million people around the world. About 50~100 million (3~5% of world population at the time) died
It was one of the deadliest Epidemics in human history
1920: World population ~ 1900 million
100m/1900m ~ 5% died !
Coming Again?
2015 In Hong Kong …
2016 In Mainland
2017 In Hong Kong
2018 In India
2019 In India
2019 In Hong Kong …
Recall History
Epidemics in Hong Kong
Bubonic Plague 鼠疫 (1894–1929)
H1N1 (1918-1919)
H2N2 (1957-1958)
H3N2 “Hong Kong flu” (1968-1969)
H1N1 Influenza (2009)
SARS (2003)
COVID-19 (2019-2020)
Recall History
Epidemic Spreading
CityU of HK, 2003
SARS — First Major New Infectious Disease of the 21st Century
Severe Acute Respiratory Syndrome (SARS) is a highly infectious and potentially lethal atypical form of pneumonia that begins with deceiving common flu-like symptoms
On 16 November 2002, the first known case of SARS was discovered in Guangdong province in southern China
The number of reported SARS cases has increased exponentially, prompting the World Health Organization (WHO) to issue a global alert on 12 March 2003
Epidemic Spreading
Typically through contact …
Human Travel Map:
Epidemic Spreading
Human Travel Map:
春运
AIDS in USA
Example: AIDS Epidemics
t3 t3 t3
t2
t2
t
exponential
t (years)
Szendroi & Czanyi, Proc. Royal Society of London, B 2004
New York – Hom
New York – Het
San Francisco – Hom
South Africa Kenya
Georgia Latvia
Lithuania
Cumulative number
In China …
In China …
In China … and in the World
Internet
Computer Viruses
Computer Virus Spreading
The first virus capable of infecting PCs was perhaps the Brain virus developed in Pakistan in 1986.
I-Love-YoubugbeganinPhilippinesonMay4,2000,andspreadacross the world in one day (traveling through Hong-Kong to Europe then to USA), infecting more than 78 million computers worldwide in just 4 days, i.e., about 10% of all computers connected to the Internet, and causing about US$5.5 billions in damage.
Itwasestimatedthatthereweremorethan48,000identifiedvirusesonthe Internet worldwide in year 2000 alone.
In 2000-2001, well-known viruses: Lover Letter, Nimda, and Sircam …
It was estimated that more than 80% computers were attacked by viruses in
China in 2004.
Also in 2004, the infamous Worm Sasser attacked several hundred
thousands of computers over the world within just a couple of weeks.
In 2009, Conficker (worm) remotely installs software on infected machines.
…… Many other examples … still today!
Computer Virus Spreading
Hong Kong
10 Most Dangerous Computer Viruses of All Time
More Examples …
In 2008, for example, security software maker “Symantec in Mountain View” in California detected 1.6 million new threats from computer viruses and other malicious software (In 2007, only 600,000 or so)
Such attacks will become more common and more sophisticated in the future
Statistically, unsolicited junk e-mails (‘spams’) accounts for about 90–95% of all e-mails sent
Such trash will become more common and more annoying in the future [Computer Viruses]
Computer Viruses and Worms
Computer viruses are usually referred to as some small computer programs that can reproduce themselves by infecting other programs and computers, which continuously grow and spread out.
When a virus is active inside a computer, it is able to copy itself in many different ways into the codes of some programs of the computer.
When the infected computer program is run into another computer, typically the code of the virus is executed first thus continues to infect other programs in the new computer.
This process repeats endlessly, leading to the collapse of a local or even global network of computers eventually, causing tremendous technological and economical disasters.
Computer Viruses and Worms
Major computer viruses may be roughly classified into:
Boot-sector viruses, which infect the boot sectors of floppies and hardware devices
File viruses, which infect application programs
Macro viruses, which infect data files directly
Hybrid types of viruses, in a certain combination of the above basic ones, which infect some special technologies or applications such as Java, ActiveX, and HTML, etc.
Trojan horses are malicious file or program, which can make copies of themselves, steal information, or harm their host computer systems
Computer Viruses
Malicious Emails and URLs referring to CODVID-19
Data: McAfee Labs report
Trojan
43
“Achilles’ Heel”
Corfu, Greece
2004 film: TROY 特洛伊
Trojan Horse
木马
Story
Robustness and Fragility of Scale-Free Networks
“Achilles’ heel”
R. Albert, H. Jeong, A. L. Barabasi, Nature, 406, 387-482 (2000)
In Greek mythology, when Achilles was a baby, his mother Thetis took him to the River Styx, which was supposed to offer powers of invulnerability, and dipped his body into the water. But as mother held Achilles by the heel, his heel was not washed over by the water of the magical river. Achilles grew up to be a man of war who survived many great battles. On one day, a poisonous arrow shot at him was lodged in his heel, killing him shortly after.
Computer Viruses and Worms
The first computer worm was created in 1988 by the now-infamous Robert Tappan Morris
On November 2, 1988, Robert Morris, Jr., a graduate student in Computer Science at Cornell, wrote an experimental, self-replicating, self-propagating program called a worm and injected it into the Internet.
Computer worms are most aggressive cyber-organisms (larger and more sophisticated programs) with much more powerful abilities to attack computers.
They shut down the Internet e-mail systems that got clogged with infected e-mails propagating from the worm.
A worm is capable of sending itself to all e-mail addresses in the e- mail address book of the computer, which received an infected e- mail. This makes worms very effective in spreading over the Internet.
Incidents on Facebook
Facebook Malware
Incidents on Facebook
网络安全问题
2016 年10月21日，美国东海岸出现了大面积互联网断网事件， 大半个美国的网络服务瘫痪。
据360全球网络攻击实时监测预警系统的跟踪监测显示:导致这 场灾难的原因是黑客入侵，控制了全世界十多万台智能硬件设 备，组成了僵尸网络，对美国互联网域名解析服务商DYN进行 DDoS攻击。
十多万台设备被控制发起的攻击已经让半个美国的互联网瘫痪， 数十亿设备如果被控制则足以让全球互联网瘫痪。
October 21, 2016, USA:
> 100000 computers hacked 1⁄2 Internet down
In China …
In China …
安全报告
In China …
安全报告
In CityU There was an incident before
Another Example
Flame (malware)
Flame, also known as Flamer, sKyWIper, or Skywiper, is modular computer malware discovered in 2012 that attacks computers running the Microsoft Windows operating system.
Reportedly, the program is being used for targeted cyber espionage (spy) in some middle eastern countries.
June 19, 2012, Washington Post published an article that Flame was jointly developed by U.S. National Security Agency, CIA and Israel’s military at least five years ago as part of a classified effort code-named Operation Olympic Games to collect intelligence in preparation for cyber-sabotage aimed at slowing Iranian nuclear efforts.
Typical examples: Milessa (1999)
I-Love-You (2000) Nimda (2001)
Win32/Sircam (2001) Chinese versions:
Worm.Klez.cn.b (2002) Worm.SoBig.c (2003) Worm.Mimail.C (2003) SCO bomb (2004)
……
Node-degree distribution of the email network
Spreading of Email Viruses
in Kiel University, Germany, 2002
N = 59812 k 2.88 Ebel et al (2002)
1.81
Computer Viruses seem to be Decreasing For many good reasons:
• Modern software has embedded virus protection modules
• Operating systems have stronger ability to resist viruses
• Antivirus software becomes much more powerful •……
Epidemic Models
Epidemic Models
(recovered individuals are permanently immune)
Logistic Equation
I(t) 1
0
SIS Model
SIS Model
SIS Model
SIR Model
SIR Model
SEIR Model
SE (with latency)I
more models
Virus Spreading Threshold
Epidemic Threshold on Homogenous Networks
v
(t) t
ki k
(t)
Epidemic Threshold on Homogenous Networks
t
0 c
c c
c
1
k
M. Boguna, R. Pastor-Satorras, A. Vespignani (2003):
“Epidemic spreading in complex networks with degree correlations”.
Epidemic Threshold on Scale-Free Networks The virus spreading equation
is modified to:
Here, k (t) is the probability of an edge connecting to
an infected degree-k node.
Solution: k()
k 1k()
Threshold: k c k2
Higher-degree nodes have higher probabilities to be infected
M. Boguna, R. Pastor-Satorras, A. Vespignani (2003):
“Epidemic spreading in complex networks with degree correlations”.
as N
k c 0
Epidemic Threshold on Scale-Free Networks Random graphs
is the spreading rate c is the threshold
Classical theory: c > 0
Scale-free network: c = 0
(Pastor-Satorras, 2001)
Scale-free networks
Immunization on Scale-Free Networks
Since scale-free networks are fragile to virus attacks, causing wide and serious outbreak, immunization becomes especially important for this type of networks
There are three effective immunization strategies:
Random Immunization (or, Uniform Immunization) Targeted Immunization (or, Selective Immunization) Acquaintance Immunization
Random Immunization
Let the immunity (density of immunized nodes) be denoted by g Random immunization strategy: the immunization threshold is
gc 1c
where c k is the effective epidemic threshold, giving k2
k k2
Clearly, Nk2 c 0gc 1
in order to immune a scale-free network, almost every node
has to be immunized
random immunization for scale-free networks is inefficient and
gc 11
expensive
Satorras and Vespignani (2003)
Targeted Immunization
Targeted immunization strategy: to immune the most highly connected nodes, thereby reducing or completely blocking virus spreading
For BA scale-free networks, the immunization threshold is
2 gc ~e m
a very small immunization threshold can be obtained for a very large range of effective spreading rate
for scale-free networks, targeted immunization has a much smaller immunization threshold than random immunization, hence is more effective
Satorras and Vespignani (2003)
Acquaintance Immunization
Idea: 1.2.3.……
2. immune its biggest neighbor
1. randomly select one node
3. immune its biggest neighbor
Immunization on Scale-Free Networks
Acquaintance immunization strategy:
To randomly select a fraction of nodes from the population, and for each node in the fraction select a biggest one of its neighbors for immunization
empty circles – random
empty triangles – acquaintance
empty diamonds – two-acquaintance empty squares – targeted
BREAK
10 minutes
Power Networks Black Out Cascading Failures …
Domino Effect
DEMO
Cascading Reactions and Failures
Epidemics
Power Grids
Similarities
cascading reactions and spreading
cascading reactions and spreading
Differences
Real Examples of Cascading Failures
Internet
Power grid
October 1986: the first documented Internet collapse due to congestion
August 1996: sag of just one electric line in Oregon USA
August 2003: local failure in Ohio USA
Drop in speed of a factor 100
Largest blackout in the US history
Blackout affected 4 million people in 9 different states
Some Typical Incidents of Power Blackouts Data Source
12 Biggest Power Blackouts in History
Snapshot: 15 August 2003 Power Blackout
Before blackout
Satellite images
Reference
During blackout
A detailed map
black out
Hong Kong ?
Will It Happen Again ?
… 1959, 1961, 1965, 1977, 2003, … … 2019, 2020, 2021 ? Major Power Blackout Records
Unfortunately, the answer is YES
2012 India
Power blackout caused traffic jam
2015 Pakistan
2019 Venezuela
2019 New York
2019 New York
2019 London
2019 Argentina
Why?
Cascading Failures on Scale-Free networks
Power-Law Exponents in some Real Networks
Power Grid Cascading Failures
DEMO
Demo: California
Black – normal Red – crash Blue – failure
Power Network Cascade Modeling
First failed node
It load will be shared by other
Newly overloaded nodes fail
Cascading Failures: Models and Analysis
k x k 1 fk(x) e(x/)k
k and areconstant parameters
Cumulativedistributionfunction: 1e
(x/)k
Recall:
Weibull distribution
Fiber-Bundle Model Built on a BA Network
P(i ) 1e(i )
Power-law distributions of degree-k nodes for small Moreno et al. (2002)
Fiber-Bundle Model
Fraction of connected sub-nets
less severe
(network not collapses unless 40% nodes are disconnected)
more severe
(whole network collapses even when only 10% nodes are disconnected)
= random graph
BA scale-free network: N = 10,000 Moreno et al. (2002)
P(i ) 1e(i )
Completely collapse
Node-Betweenness Model Replace “load capacity” by “node-betweenness”
Motter et al. (2002)
Scale-free network model AS-level real Internet
G is the fraction of remaining connected sub-nets over the whole network [square curves correspond to random node failures, star curves to largest-degree node
failures, and circle curves to biggest-betweenness node failures]
Observation1: smallertolerancemoreseverefailure
Observation 2: largest-degree/betweenness failures is more severe than random failures
Node-Betweenness Model
Comparison of cascading failures on random networks
square – random attack, circles – intentional attack. N = 5,000
Observation 1: For random graphs, both random and intentional attacks perform similarly
k3
Motter et al. (2002)
Node-Betweenness Model
Motter et al. (2002)
Comparison of cascading failures on scale-free networks square – random attack, circles – intentional attack. N = 5,000 k 3
Observation 2: For scale-free networks, intentional attacks are more severe than random attacks
Cascading Failures: Models and Analysis Models Based on Edge Dynamics
Consider loads on edges Let s be the number of
overloaded edges
Let P(s) be the cumulated failures (normalized)
Let be the average edge loading over the whole network
Moreno et al. (2003)
Cascading Failures
A model based on both node and edge dynamics eij [0,1] – efficiency of
edge (i,j), e.g., bandwidth E – average efficiency:
E(G) 1 eij N ( N 1) i j
— loading ii
Li(t)
C L(0)–capacity
1
a) ER network, b) BA network. [squares — random node failures, circles — biggest node failures]
— tolerance Crucitti et al. (2004)
AS-level Internet (Real Data)
Random failures
intentional attacks
Crucitti et al. (2004)
US Power Grid (Real Data)
random failures
intentional attacks
Crucitti et al. (2004)
Interdependent Networks
Interdependent Networks
Network of Networks in the real world
Example: human mobility networks
short-range interconnected flows by cars, trains, ferries, etc. long-range commuting flows like air-flights
communication network flows (phones and the Internet).
Interdependent Networks of human mobility in the North America
blue – short-range brown – long-range
Vespignani, Nature (2010) 464: 984-985
A Real-World Example: Italy Blackout in 2003
a One power station failed (red) a few associated Internet servers failed (red), and some Internet servers are isolated (green)
b The above failed Internet servers (red) and associated edges are removed related power stations failed (red), and some power stations became isolated (green)
c The above failed power stations (red) and Internet servers (red) are removed both networks failed (both red) system collapsed Buldyrev et al. Nature (2010) 464: 1025-1028
Cyber-attack to Power Grids
On 23 December 2015
Cyber-attack to Power Grids
Power Grid Cascading Failures
Models, AnalysisPrevention, Control
Sample Books
End