05 Introduction to

Static Complex Networks (Part I)

By NTU Complexity Institute
The ‘Logic’ of Complex Systems

Lorenz Equation:
dx
—
dt
= 𝜎(y − x)
x
dy
—
dt
= x(p − z) – y

dz
—
dt
= xy =𝛽z

Equation is unknown.
y z
Can still understand a lot!
Definitions

Network/Graph

Self-interaction

x
Node/Vertex

Link/Edge
- Directed
- Undirected

Different types of links

y z
Types of Networks I

Undirected Directed Bipartite

Types of Networks II

Undirected Tree Planar

Types of Networks III

Unweighted Weighted
Measures on Networks

- Nodes
- Degree
- Clustering
- Assortativity
- Paths
- Path length
- Diameter
- Betweenness
Degree of a Node I

Degree of node, k = number of

2
4 neighbours (nodes it is linked)

5 1 kmin = 1
3 4 kmax = 5

5
4

2
2 2
Degree of a Node II

in-degree of node, kin + out-degree of kin = 1,

node, kout kout = 3

kin = 1, kin = 3,
kout = 1 kout = 2
Clustering Coefficient I

Number of neighbours of i that are also neighbours of each other

ci =
Maximum number of mutual neighbours i can have
8 neighbours
i

8(8 – 1)
Max mutual neighbours =
2
= 28 pairs

Mutual neighbours = 0 cij = 0 cij = 1

Clustering Coefficient II

4 neighbours
2 pairs of mutual neighbours

5 neighbours
1 pair of mutual neighbours
Clustering Coefficient II
Assortativity

1-5: 1
2-3: 1, 2-4: 3, 2-5: 3
3-4: 1, 3-5: 1
4-4: 2, 4-5: 3
5-5: 1
Path Length

d(i , j) = 3
—

i d = average path length (over all pairs of nodes)

D = max d(i , j) = diameter of network
(i,j)

3 hops
4 hops

6 hops
j
Betweenness

11 nodes
11(10)/2 = 55 shortest paths

4
bi = —
55

4 shortest paths through node

05 Introduction to
Static Complex Networks (Part II)
By NTU Complexity Institute
Random Networks I

Alfred Rényi
(1921–1970)

Paul Erdös
(1913–1996)
Random Networks II

Retrieved from [Link] Copyright 2016 by Albert-László Barabási. Reproduced with permission.

1
p=—
6
N = 12
Random Networks III

Retrieved from [Link] Copyright 2016 by Albert-László Barabási. Reproduced with permission.

p = 0.03
N = 100
Random Networks IV

 N − 1 k
P(k ) =   p (1 − p) ( N −1)− k
 k 
Select k nodes from Probability of missing (N – 1)–k edges
N–1

Probability of having k edges

< k >= p(N -1)

sk2 = p(1- p)(N -1)
sk é1- p 1 ù1/ 2
1
=ê ú »
Tyler, Asselbergs, Williams and Moore. (2009). Bioessays, 31, 220-7.
< k > ë p (N -1) û (N -1)1/ 2
Random Networks V
Exact result Large N limit
(Binomial distribution) (Poisson distribution)
æ N -1ö k (N -1)-k < k > k
P(k) = ç ÷ p (1- p) P(k) = e-<k>
è k ø k!
Probability Distribution Function
(PDF)

<k>= (N − 1)p <k>= <k>

<k2> = p(1 − p)(N – 1) + p2(N − 1)2 <k2> = <k>(1 + <k>)
𝜎 = (<k2> − <k>2)1/2 = [p(1 − p)(N – 1)]1/2 𝜎k= (<k2> − <k>2)1/2 = <k>1/2
Small-World Networks I

Regular

Random
Duncan Watts
(1971–)
Steve Strogatz
(1959–)
Small-World Networks II

The Watts-Strogatz Model:

- Start with a lattice network
- For every edge, rewire with a probability b

Reprinted by permission from Macmillan Publishers Ltd: Nature Publishing Group

([Link] 1998.

0 b 1
Watts and Strogatz. (1998). Nature, 393, 440.
Small-World Networks III

The Watts-Strogatz Model:

- It takes a lot of randomness to ruin the
clustering, but a very small amount to
overcome locality

Reprinted by permission from Macmillan Publishers Ltd: Nature Publishing Group

([Link] 1998.
05 Introduction to
Static Complex Networks (Part III)
By NTU Complexity Institute
Albert-László Barabási
Scale-Free Networks I

Reprinted by permission from Macmillan Publishers Ltd: Nature

Publishing Group ([Link] 1998.
Réka Albert
Hawoong Jeong
Scale-Free Networks I

Nodes: WWW documents

Links: URL links
Over three billion documents
ROBOT: Collects all URLs found in a document
and follows them recursively

Copyright 1998 The Regents of the University of California. All Rights Reserved.
Scale-Free Networks II

1
Linear-linear

0.6

0.2

20 40 60 80 100
Scale-Free Networks II

Semi-log
Scale-Free Networks III

Road network Air travel network

Retrieved from [Link] Copyright 2016 by Albert-László Barabási.
Reproduced with permission.
Scale-Free Networks IV

P in(k )  k −2.2
Pout (k )  k −2.2

Archaea Bacteria Eukaryotes

Reprinted by permission from Macmillan Publishers Ltd: Nature Publishing Group ([Link] 2000.
 Scale-Free Networks IV

IMDb Internet Movie Database

Days of Thunder (1990)
- Nodes: Actors
Far and Away (1992)
Eyes Wide Shut (1999)
- Links: Cast
© Electrochris | [Link] © Featureflash | [Link]

- N = 212,250 actors
- k = 28.78

From Barabási, A.-L. and Albert, R. (1999). Emergence of Scaling in Random

Networks. Science, 286(5439), 509-512. doi: 110.1126/science.286.5439.509.
Reprinted with permission from AAAS.
Barabási-Albert Model I

Networks continuously expand with the

addition of new nodes:
- Add a new node with m links.

Barabási and Albert. (1999). Science, 286, 509.

Barabási-Albert Model II

Where will the new node link to?

- According to the Erdös-Rényi and Watts-
Strogatz models, choose randomly.
- New nodes prefer to link to highly connected
nodes (E.g., www, citations, IMDB)
Preferential attachment:
- The probability that a node connects to a
node with k links is proportional to k.
ki
 ( ki ) =
 jk j
Barabási and Albert. (1999). Science, 286, 509.
Barabási-Albert Model III

- Networks continuously expand by the addition of

new nodes
- WWW: Addition of new documents
Growth:
- Add a new node with m links.
- New nodes prefer to link to highly connected
nodes
- WWW: Linking to well-known sites
Preferential attachment:
- The probability that a node connects to a node
with k links is proportional to k.
ki
 ( ki ) =
Barabási and Albert. (1999). Science, 286, 509.  jk j
Barabási-Albert Model III

- Networks continuously expand by the addition of

P(k) ~ k−3 new nodes
- WWW: Addition of new documents
Growth:
- Add a new node with m links.
- New nodes prefer to link to highly connected
nodes
- WWW: Linking to well-known sites
Preferential attachment:
- The probability that a node connects to a node
with k links is proportional to k.
ki
 ( ki ) =
From Barabási, A.-L. and Albert, R. (1999). Emergence of Scaling in Random Networks.
Science, 286(5439), 509-512. doi: 110.1126/science.286.5439.509. Reprinted with
 jk j
permission from AAAS.
05 Introduction to
Static Complex Networks (Part IV)
By NTU Complexity Institute
Robustness of a Network

Could the network structure contribute to robustness?

Node failure

Retrieved from [Link] Copyright 2011 by Barabási A.L., Barzel, B. and Martino, M. Reproduced with permission.

How do we describe the breakdown of a network under node removal in quantitative terms?
Percolation theory
Percolation Transition

remove nodes remove nodes

Unperturbed network Giant component persists Network collapses

Retrieved from [Link] Copyright 2011 by Barabási A.L., Barzel, B. and Martino, M. Reproduced with permission.
Percolation Transition

P P∞ : Probability that a node belongs to the

giant component
f : Fraction of removed nodes
1

fc f
0
Damage to Network as Percolation

S f : Fraction of removed nodes

Component
structure
Graph

fc f
(Inverse percolation phase transition)
Retrieved from [Link] Copyright 2011 by Barabási A.L., Barzel, B. and Martino, M. Reproduced with permission.
Failures vs Attacks

Squares: Random failure

Circles: Targeted attack

Failures: Little effect on the integrity of the

network
Attacks: Fast breakdown

Retrieved from “Statistical Mechanics of Complex Networks” (doi:

[Link] Copyright 2002 by The American Physical Society.
Reprinted with permission.
Real-World Examples

Blue squares: Random failure

Red circles: Targeted attack
Open symbols: S
Filled symbols: l

- Breakdown if 5% of the nodes are eliminated

selectively (always the node with the highest
degree)
- Resilient to the random failure of 50% of the
nodes

Similar results have been obtained for metabolic

networks and food webs.
Retrieved from [Link] Copyright 2011 by Barabási A.L., Barzel, B. and
Martino, M. Reproduced with permission.
Acknowledgements

- Slide 12: Photo of Paul Erdös [Photograph]. Retrieved May 9, 2017, from: [Link] Reproduced with permission.
- Slides 18-19: Albert-László Barabási. (2016). Random Networks [Graph]. Network Science. Retrieved May 8, 2017, from [Link]
- Slide 20: Tyler, A.L., Asselbergs, F.W., Williams, S.M. and Moore, J.H. (2009). Shadows of complexity: what biological networks reveal about epistasis and pleiotropy. Bioessays, 31(2),
440-442. doi: 10.1002/bies.200800022
- Slide 21: Binomial distribution, extracted from Wikimedia Commons: [Link] by Tayste:
[Link] (Public Domain)
- Slide 21: Probability mass function, extracted from Wikimedia Commons: [Link] by Skbkekas:
[Link] under CC-BY-3.0: [Link]
- Slide 23: Photo of Duncan Watts, reproduced with permission from Duncan Watts.
- Slide 24: Photo of Steven Strogatz, reproduced with permission from Steven Strogatz.
- Slides 25-26: Watts, D.J. and Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks. Nature, 393, 440-442. doi: 10.1038/30918
- Slide 28: Photo of Albert-László Barabási, extracted from Wikimedia Commons: [Link]
_Annual_Meeting_of_the_New_Champions_2012.jpg by World Economic Forum from Cologny, Switzerland (Mastering Complexity):
[Link] under CC BY-SA 2.0: [Link]
- Slide 29: Albert, R., Jeong, H. and Barabási, A.-L. (1999). Internet: Diameter of the World-Wide Web. Nature, 401, 130-131. doi:10.1038/43601
- Slide 30: Photo of Réka Albert, reproduced with permission from Réka Albert.
- Slide 31: Photo of Hawoong Jeong, reproduced with permission from Hawoong Jeong.
- Slide 32: The Regents of the University of California. (Copyright owner). Plankton: Visualizing NLANR's Web Cache Hierarchy [Illustration]. Retrieved May 9, 2017, from
[Link]
- Slide 35: Albert-László Barabási. (2016). Random vs. Scale-free Networks. [Graph]. Network Science. Retrieved May 8, 2017, from [Link]
- Slide 36: Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., and Barabási, A.-L. (2000). The large-scale organization of metabolic networks. Nature, 407, 651-654. doi: 10.1038/35036627
- Slide 37: Electrochris (Photographer). (2011). A portrait of actor Tom Cruise [Photograph]. Retrieved May 2, 2017, from [Link]
portrait-image22539562.
- Slide 37: Featureflash (Photographer). (2001). Actress NICOLE KIDMAN at the Cannes Film Festival where her movie Moulin Rouge is opening the Festival 09MAY2001
Paul Smith/Featureflash[Photograph]. Retrieved May 2, 2017, from [Link]
festival-where-her-movie-moulin-rouge-opening-festival-may-paul-smith-featureflash-image36734585.
- Slide 37 and 41: Barabási, A.-L. and Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509-512. doi: 110.1126/science.286.5439.509
- Slides 43-44, 46 and 48: Barabási A.L., Barzel, B. and Martino, M. (2011). Network Science: Robustness Cascades. Retrieved May 8, 2017, from
[Link]
- Slide 47: Albert, R. and Barabási, A-L. (2002). Statistical Mechanics of Complex Networks. Reviews of Modern Physics, 74(1), 47. doi:
[Link]