Complex Dynamical Networks: Lecture 2: Network Topologies
— Basic Models and Properties EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks
Regular Networks
(a) Fully-connected network
(b) Ring-shaped coupled network
(c) Star-shape coupled network
Regular Networks
Fractal Network
Lattice
Basic Properties of Regular Networks:
(a) Fully-connected networks: Average path length:
Lfull 1
Clustering coefficient:
Cfull 1
Degree distribution:
delta
k = 0
1
k = 99 Example: N = 100
k = 200
Basic Properties of Regular Networks:
(b) Ring-shaped coupled networks Clustering Coefficient:
Note: This is an asymptotic formula: the bigger the K (hence N), the more
accurate the formulas
Basic Properties of Regular Networks:
(c) Star-shaped coupled networks: Average Path Length:
Lstar 2 2 2 (N) N
Verifying:
(N1)1[(N2)(N3)21]22 2 (N 1)[(N 2)(N 3)21] N
Clustering Coefficient: Cstar 0 Degree Distribution: delta-like
Example: N = 3
There are 3 different paths with lengths 1, 1, 2 L = (1+1+2) / 3 = 4 / 3 or L = 2 – [2 / (N=3)] = 4 / 3
Fractal Networks
Example:
Random Graph Theory
Paul Erdös Alfred Rényi
(1913-1996) (1921-1970)
Erdös-Rényi Random Graph Theory Given N isolated nodes
Add an edge between every possible pair of nodes with probability p
Statistically, the expected number of edges is pN(N-1)/2
Example
Random-Graph Networks
k p(N 1) pN C p k / N
Theorem:
Average Degree:
Clustering Coefficient: Degree Distribution: AveragePathLength:
nodes. Each next node can connect to roughly n ~ k n k 2 nodes, and
k P(k) k! e
(Poisson)
L~ lnN/ lnk Verifying: For any node, it can connect to roughly n ~ k
so on. Thus, because the average distance between each pair of nodes is L there are roughly n N ~ k L nodes in the network,
21
1
yielding
L ~ ln N / ln k
Poisson Distribution:
The probability of a node connecting to k nodes among other N 1 nodes (but not connected to the rest N 1 k nodes) is given by
whereN’N1
Let pN ‘ (referred to as expectation value) and fix it as constant
N ‘
N’ k N’k P(k|N’)kp (1p)
Thus, P (k|N’) N’! k1 N’k k!(N’k)! N’ N’
P(k) lim P (k|N’)
lim N'(N’1)(N’k1)k 1N’1k
N’ N’k k! N’ N’
k P(k) k!e
1k e 1 k!
ER Random Graph Models
Features:
Connectivity
node degree distribution – Poisson
Homogeneity
all nodes have about the same number of edges
Non-growing
Random Graph and Poisson Degree Distribution
Small
“Collective dynamics of ‘small-world’ networks” — Nature, 393: 440-442, 1998
D. J. Watts S. H. Strogatz
(Cornell University)
–
World Networks
A Historical Remark
Small-World Networks
Features:
Connectivity Poisson distribution
Homogeneous nature: each node has roughly the same number of edges
Small average path length but large clustering coefficient
Not growing
WS Small-World Network Model Algorithm (rewiring):
Start from a ring-shaped network with N nodes, in which each node is connected to its 2K neighbors, where K is a (usually small) positive integer.
Go around the ring-shaped network clockwise (or counterclockwise). Pick a node and operate on its connections to the K neighbors one by one: an edge connecting this node to its neighbor will be kept unchanged; another end of the edge will be disconnected with probability p and then be re- connected to a randomly-picked node from the network (ignore self-loops and multiple edges).
More precisely …
WS Small-World Network formation
D.J. Watts and S.H. Strogatz:
Collective dynamics of ‘small-world’ networks Nature 393, 440-442 (4 June 1998)
Continuing …
p
Small-world features:
Large clustering
coefficient C
Small average path-length L
NW Small-World Network Model
Algorithm (adding edges):
Start from a ring-shaped network with N nodes, in which each node is connected to its 2K neighbors, where K is a (usually small) positive integer.
With a (small) probability p, add an edge to each pair of nodes in the
network.
Mark E J Newman
Univ of Michigan
Two Small-World Network Models
a) WS small-world network model b) NW small-world network model
Small-World Networks
Theorem: For large enough N,
Clustering Coefficient of the WS small-world network model:
C( p) 3(K 2) (1 p)3 4(K 1)
Clustering Coefficient of the NW small-world network model: C( p) 3(K 2)
4(K 1)4Kp(p2)
M.E.J. Newman, The structure and function of networks, Computer Physics Communications,
147: 40-45, 2002
M.E.J. Newman, The structure and function of complex networks, SIAM Review, 45: 167-256, 2003.
Theorem:
Small-World Networks
Average Path Length of WS small-world network model: L(p)2N f(NKp/2)
K
f ( x ) c x 1 lnx/x x1
(c — constant)
Average Path Length of NW small-world network model:
L(p)2N f(NKp/2) K
f (x) 1 tanh1 x
2 x22x
x2
M.E.J. Newman and D.J. Watts, Randomization group analysis of the small-world network model, Phys. Lett. A, 253: 341-346, 1999.
A. Barrat and M. Weigt, On the properties of small world networks, European Phys. Journal B, 13: 547-560, 2000
Theorem:
Small-World Networks
Degree Distribution of WS small-world network model:
( pK / 2)k iK / 2
epK/2
min{k K / 2,K / 2} K / 2
P(k) (1p)i p(K/2)i
kK/2 Degree Distribution of NW small-world network model:
N KpkK KpNkK P(k)kKN 1N kK
P(k) 0
M.E.J. Newman, The structure and function of networks, Computer Physics Communications, 147: 40-45, 2002 M.E.J. Newman, The structure and function of complex networks, SIAM Review, 45: 167-256, 2003.
i0 i P(k)0 kK/2
(kNK/2)!
kK
Navigable Small-World Networks
International Congress of Mathematics (ICM)
22-28 August 2006, Madrid, Spain
Jon M Kleinberg (Cornell Univ.) received the Nevanlinna Prize for Applied Mathematics
He gave a 45-minute talk – “Complex Networks and Decentralized Search Algorithms”
J M Kleinberg, “Navigation in a small world,” Nature, 2000
J M Kleinberg, The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000: 163-170
Kleinberg’s Navigable Networks
Problem –
To deliver a message from a source to a destination
on a network, in as few steps as possible
Suppose that
1. Given a lattice network
2. Add m long-range edges anywhere in the network
Kleinberg’s Navigable Networks
Assumption: The probability of a new edge connecting a node u to any other node v in the given lattice:
P(u,v) d uv
where duv is the distance between u and v with parameters 0, 0satisfying d 1 as a probability measure.
(u,v)
u,v
When , the new edge-addition probability is a constant,
0
so every node has the same probability to receive the new
edge; in this case, the model reduces to the original NW small-word network model.
Kleinberg’s Navigable Networks
poly(logN) time-steps to deliver a message from any source to any
A network is navigable if it requires at most destination on the network.
Kleinberg Theorem:
For 2 , the lattice is navigable in O(log N )2 time-steps at a rate depending on m, but for all 0 it is not navigable.
For 02,ittakesatleast O(N(2)/3) time-stepstodelivera message from any source to any target.
For 2, it will take at least O(N(2)/(1) ) time-steps.
For the Kleinberg problem and solution, formulated in the original
NW ring-shaped network setting, see:
M E J Newman: Networks: An Introduction. Oxford, UK, 2010: 713-718
Some More Concepts
Degree Correlations Weighted Networks Evolving Networks
Degree Correlations
Average degree alone is not sufficient to characterize a network
Degree Correlations
Example:
Degree Correlations
Relationship:
Weighted Undirected Networks
Static Networks:
Weighted Undirected Networks
Dynamic Networks:
w ij
wHhh w0ww ij i j ii ij ji
h 1
i
Weight of Edge e : ij
i, j: nodes
h : index of action
j
ih = 1, if node i has action h (h = 1, … , H) = 0, otherwise
Total coupling strength of node i : Si w ik
k
Weighted Undirected Networks
Example:
i
w ij
j
k Nodes: i,j,k
Actions: Send and Receive E-mails
i sent 2 e-mails to j: indexed h = 1, 2 (so, H = 2)
j received the first e-mail: indexed h = 1 but it rejected the second e-mail
i sent 1 e-mail to k (the second e-mail): indexed h = 2 (so, H = 2) k received the (second) e-mail from i
1 1,2 1; 1 1,2 0; 1 0,2 1 iijjkk
HH
w hh 11101 w hh 10111
ij
ij ik
ik h 1 h 1
Evolving Networks
Reference
BREAK
10 minutes
Scale-Free Networks
“Emergence of scaling in random networks”
Science 286: 509 (1999)
A.-L. Barabási
R. Albert
(Norte Dame University)
BA Scale-Free Network Model Start with a connected network having m0 1 nodes
(i) Add new nodes:
Add 1 new node into the network:
This node is connected to m ( m m0) existing nodes simultaneously
(ii) Add new edges:
The way to add the m new edges into the network: Every existing node is to be chosen with probability
(k) ki
i kl l
Scale-Free Network Modeling
p = 2/20 = 1/10
p = 4/20 = 1/5
Henneberg Network
Step 1. Start with a small connected network.
Step 2. Node addition: Add a new node to the existing network.
Connect it to any pair of existing nodes.
Step 3. Edge addition: If the pair of old nodes were connected, then do nothing; otherwise, connect them with a new edge.
Step 4. Repeat Steps 2 and 3 till the network has the desired size.
Facebook is Scale-Free Network
Different ways to displace
Scale
–
Free Networks
Features:
Connectivity:
in power-law form
Heterogeneous nature:
very few nodes have many links but most nodes have very few links
Growing (Hawoong Jeong)
Scale-Free Network Model
P(k) ~ k
Power-Law
slope
Log-Log Plot
Scale-free: It is independent of the network size
Different ways to displace
Why Log-Log Plot ?
To see subtle details
(A.-L. Barabasi)
Comparison
Scale-Free Network
How to derive the power law ? – A heuristic 1/2 Let i be a node, which was added to the network at time ti
Suppose this node has degree ki when it is being picked up at time t ti
Imaging that the node degree ki is a continuous variable, so the rate of change of ki is proportional to ki Therefore,
k
tj j
i cki aki /
Since the new node brings m edges in, the change of its degree
k a(k) (a:c ji
k isparameter) j
is m, one has a m Also, ignoring initial nodes, j k j 2mt
Hence,
Solving this equation, with the initial condition that node i was added to the network at ti with connectivity ki (ti ) m , yields
ki mki ki t 2mt 2t
ki(t)m tt namelyti m2t
ik2 i
How to derive the power law ? – A heuristic 2/2 k k ti m2tm2t
i2k2k2 P(k(t)k)Pt mt i
iik2
{ti} P(ti ) 1 ti
m2t m2 P(k(t)k) Ptik2 1k2
t
Pti k2 1Pti k2 1 k2 P(ti)1 k2 t 1 k2
m2t m2t m2t
m2t 1 m2
P(k) i 2m2k3 k k k
bk
3
BA Model
P(k)2m2k3
P(k) ~k-3
A.-L. Barabási, R. Albert, Science 286, 509 (1999)
Log-Binned Curves
Data binning (or bucketing) is a data pre-processing technique used to reduce the effects of minor observation errors.
The original data values which fall in a given small interval, a bin, are replaced by a value representative of that interval, often the central value.
It is a form of quantization.
Comparison 1
Comparison 2
Figure 2. Homogeneous vs Heterogeneous networks, both with a Center They have the same power-law distribution
Comparison 3
A Historical Remark (1)
Prof George Zipf from Harvard University studied the
frequencies of words In English (and languages) in 1932-1935 Zipf’s Law
Few words occur very frequently; Most words occur only occasionally
A Historical Remark (2)
Nevertheless, the BA model is much more influential in recent years
Power-Law Distributions: Scale-Free
Consider a probability distribution function f (x). If, for any given constant a, there is a constant b such that the following “scale-free” property holds:
f (a x) = b f (x)
then, with the assumption that f (1) f (1) 0 , the function f (x) is uniquely determined by a power-law:
f(x) f(1)x
f ‘ (1) / f (1)
Note: The reverse may not be true
BA Model:
P(k)2m2k3
Power-Law Distributions: Scale-Free
Proof. In f (a x) = b f (x), let x = 1. Then, f(a) = bf(1), so b = f(a) / f(1), giving
f (a) f (x)
f (1)
Since this equality holds for arbitrary a and x, one may also
consider a as a variable and take a derivative w.r.t. a : df(ax)d(ax) f(x)df(a)
f (ax)
d(ax) da f (1) da Letting a = 1 gives
x df (x) f (1) f (x) d(x) f (1)
which has a unique solution
f(x) f(1)x
f'(1)/ f(1)
BA Scale-Free Network Model
Theorem:
Average Path Length:
Clustering Coefficient:
Degree Distribution:
L~ lnN ln ln N
m2(m1)2 m1
C 4(m1) ln m m1 t
1 (lnt)2
P(k)2m2k3
B. Bollobas and O. Riordan, Mathematical results on scale-free random graphs, In S. Bornholdt and H.G. Schuster (eds.), Handbook of Graphs and Networks: From the Gerome to the Internet, Wiley-VCH, 2003, pp. 1-34.
R. Cohen and S. Havlin, Scale-free networks are ultrasmall, Phys. Rev. Lett., 86: 3682-3685, 2003.
Extended BA (EBA) Model
The BA Model can describe scale-free networks having a power
law with r = 3, but many real-world networks do not satisfy r = 3 EBA model (Albert and Barabasi, 2000)
Start with a connected network with m0 0 nodes. (i) Add new nodes (incremental growth):
With probability p, one new node is added into the network (ii) Re-wiring:
With probability q, m ( m m0 ) edges are rewired (iii) Add new edges (preferential attachment):
m ( m m0 ) new edges are added into the network with probability (k) ki
i kl l
EBA Model Inthismodel, 0 p1 and 0q1p
If q min(1 p, (1 p m) /(1 2m)), then the degree distribution of nodes follows a shifted power-law:
P(k) ~ (k A(p,q,m)1) where 1 B (typically, 2 3 ), and
2m(1q) A(p,q,m)(pq)1pq 1
B ( p , q , m ) 2 m (1 q ) 1 p q
m
Fitness Model
Recall: During the growth of the BA model, the degree of a node is changing by
t ti
is the instant
at which node i is being added into the network.
This implies that the older a node, the higher its degree
In real life, however, this may not be true. For example:
• A teenager can have more social connections than an elder man
• A new website in WWW can receive more links than an old one • ……
ki (t)
where ki (t) is the degree of node i at time t and ti
Fitness Model
1. Growth: Start from a small network of size m0 1 and introduce one new node to the existing network each time, and with probability () this node is given a fitness value, 0 i 1
2. Preferential Attachment: The new node is connected to 1 m m0 existing nodes, each is according to the probability
iki
i nj1jkj
where n m0 t 1 is the total number of existing nodes at the (t-1)st step of the process.
Basic Properties: Similar to the BA model
Main difference: Preferential attachment is proportional to both
(1) node degree; (2) fitness value Bianconi and Barabási, Phys. Rev. Lett. (2001)
A Simple Model
with power-law degree distribution
1. Start with nothing: no nodes, no links
2. At each time, with probability p , one new node is added to the
existing network
3. For every pair of unconnected nodes, with probability q = 1 – p , one edge is added to connect them
Theorem: The degree distribution of the above network model has a power-law form, P(k) ~ k , where 1 q1
Corollary:If1/2q1then 23
Aiello, Chung and Lu (2002)
Scale-Free Networks Debate 1/2 Criticism Rebut
2018
Scale-Free Networks Debate 2/2
Criticism
Rebut
2019
Some Other Models
Assembly-Line Automation
Snapback Network
Note: The direction indicates how to operate the snapback connection
The model can be undirected if all the directions are finally removed
Genome
End