程序代写代做代考 ER assembly clock graph algorithm C go Complex Dynamical Networks: Lecture 2: Network Topologies

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:
(N1)1[(N2)(N3)21]22 2 (N 1)[(N 2)(N 3)21] 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’N1  
Let   pN ‘ (referred to as expectation value) and fix it as constant
N ‘
N’ k N’k P(k|N’)kp (1p)
Thus, P (k|N’) N’!   k1  N’k  k!(N’k)! N’  N’
P(k) lim P (k|N’)

lim N'(N’1)(N’k1)k 1N’1k
N’ N’k k! N’  N’
k  P(k) k!e
1k 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(p2)
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 x1
(c — constant)
Average Path Length of NW small-world network model:
L(p)2N f(NKp/2) K
f (x)  1 tanh1 x
2 x22x
x2
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 iK / 2
epK/2
min{k K / 2,K / 2}  K / 2
P(k)   (1p)i p(K/2)i
kK/2 Degree Distribution of NW small-world network model:
 N KpkK KpNkK P(k)kKN 1N kK
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.
i0  i  P(k)0 kK/2
(kNK/2)!
  
kK

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 02,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
wHhh w0ww 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 hh 11101 w hh 10111
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 of 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 m2tm2t
i2k2k2 P(k(t)k)Pt mt i
iik2
 {ti} P(ti )  1 ti
 m2t  m2 P(k(t)k) Ptik2 1k2
t
Pti  k2 1Pti  k2 1 k2 P(ti)1 k2 t 1 k2
 m2t   m2t  m2t 
m2t 1 m2
P(k) i   2m2k3 k k k
bk
3

BA Model
P(k)2m2k3
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)2m2k3

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(m1)2  m1
C 4(m1) ln m m1 t
1 (lnt)2 
P(k)2m2k3
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 p1 and 0q1p
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(1q)  A(p,q,m)(pq)1pq 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 nj1jkj
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 q1
Corollary:If1/2q1then 23
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