程序代写代做代考 graph algorithm C Bayesian Complex Dynamical Networks: Lecture 4b: Internet

Complex Dynamical Networks: Lecture 4b: Internet
— Topology and Modeling EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks

Network Topology Modeling
 Graph representations
 AS-level:
 nodes are domains (AS)
 edges are peering relationships
 Router-level:
 nodes are routers
 edges are one-hop IP connections
 PC-level: not manageable today  nodes are PCs, hand-held sets  edges are optical fibers

Internet Modeling
A model should be made “as simple as possible, but not simpler.” – Albert Einstein
Recall simple generic models: Random-graph model Small-world model
Scale-free model
Actually, there are better ones

Representative Models
— — — (1980s)
 Waxman (Waxman 1988)
Router-level model capturing locality — — — (1990s)
 Transit-Stub (Zegura 1997), Tiers (Doar 1997) Router level model capturing hierarchy and clustering — — — (2000s)
 Inet (Jin 2000)
AS-level model based on degree sequence
 BRITE (Medina 2000)
AS-level model based on evolution
 BA-Model (Barabasi-Albert 1999-2000)
AS-level model based on degree sequence and evolution
 HOT (CalTech 2004-2005) Heuristic Optimized Tradeoffs  MLW (Fan-Chen, 2006-2010)
Multi-Local-Worlds

Router-Level Internet Topology
 A common software tool to represent the router-level Internet topology by a graph is traceroute
 The traceroute uses hop-limited probe, which consists of a hop-limited IP (Internet Protocol) packets and the corresponding ICMP (Internet Control Message Protocol) responses, to probe every possible IP address and record every reached router and the corresponding edges
 Commercial: traceroute software or its IPv6 version traceroute6(8)

Router-Level Internet Topology
 Some analysis on the real data collected during October-November of 1999 shows that in the router-level of the Internet topology:
 basically, it does not have hierarchical structure
 power-law node-distribution is not prominent but Weibull distribution seems better, yet the latter can only reflect Transit but not Stub subnets
 Some analytical results on the real data collected during December 2001 — January 2002 show that the Weibull distribution can better fit the complementary cumulative distribution function of router out-degree than the Pareto and Power-law distributions
 Today, data size is too big to manage for modeling

k  x k 1 fk(x) e(x/)k
k and  are constant parameters
x
Weibull distribution

k fk(x)kxk1, x0
k and  are constant parameters
Pareto distribution
x

First Generation of
Internet Topology Models
1980s

Waxman Model
Waxman model:
 Start with N nodes, randomly placed on a lattice, at most
one in each small square
 Each step, for every pair of two nodes, u and v, connect them by an edge according to the following probability (called Waxman probability):
P(u,v)ed(u,v) / ( Lmax)
where d(u,v) is the distance, Lmax is the longest distance,
and  is the (normalized) average number of edges and

satisfying 0   ,   1 , that together make the formula a
is a parameter determined by the average path length, probability distribution function

Waxman Model
N = 150,   0.25,   0.3 Degree distribution (~ Weibull) (Waxman, 1988) (Medina et al., 2000)

Second Generation of
Internet Topology Models
1990s

MILNET (Military Network), part of the ARPANET, unclassified by US Department of Defense (1989)

Transit-Stub Topology
Illustration of network structure from Transit-Stub topology generator
(Hierarchy with Communities)

Transit-Stub Topology Generator
 Modeling Data
 Generate all Transit domains:
 Use a random-graph generation method (e.g., the Waxman algorithm), where each node represents a Transit domain.
 Generate nodes in each Transit domain by adding some nodes around the Transit point, and then connect these nodes with edges at random.
 Generate Stubs for each Transit:
 This is similar to the above Transit-domain generation, but at a
lower level.
 Connect every Stub domain to a Transit domain: Randomly select one node from a Stub domain and then connect this node to the Transit domain by an edge.
 Generate LANs for each Stub:
 This is similar to the above Transit-Stub generation, but at the
lowest level.
 They all have star-shaped structures.
 Connect each LAN to a Stub domain.

Transit-Stub Topology Generator
A typical Transit-Stub topology
(Hierarchy with Communities) (Calvert, 1997)

Transit-Stub Topology Generator
Out-degree distribution of a Transit-Stub network with 6660 nodes ~ Weibull (Medina et al., 2000)

Third Generation of
Internet Topology Models
2000s

Inet
 Router-level model and AS-level model
 Input:
 Total number of nodes
 Percentage of degree-one nodes
 Degree sequence: power-law
P(k)  k
  2.14 ~ 2.21

Inet
 From the given data set, let V1 be the set of all degree-1 nodes, typically has about 30% of the total (green nodes). Let the rest be V2 (pink nodes).
 GenerateaspanningtreeconsistingofnodesfromV2
To generate the spanning tree in a network G, start from isolated initial conditions, and then a node i is connected to a node j , both in V2 , according to the following (preferential attachment) probability:
(i, j)  w j
i w j — weight (reverse distance) from i to j
kG
 Connect the degree-1 nodes from V1 to the spanning
tree, according to the above same probability.
 Connect high-degree nodes to those available nodes which did not connect to V1 , also according to the above same probability (blue dashed lines).
wki i
Recall: Analysis on the Internet data of April 2002 shows that nodes with degrees of 1, 2, and 3 were 26%, 38% and 14%, respectively, which sums up to about 80% of the whole network (Zhou and Mondragon, 2004)
(Jin 2000)

Inet
Started by University of Michigan (2002)
Inet Framework
Inet-3.6.6 Program
Simulations based on real data:
6700 nodes (Feb. 2000), 8880 nodes (Feb. 2001) and 12700 nodes (Feb. 2002)

Average path lengths
Out-degree power-law distributions 

BRITE
(Boston university Representative Internet Topology gEnerator) Modeling NS-3 codes
Framework –
 Set a lattice on the plane, divide the lattice into some large squares, and then further divide all large squares into small squares. According to a certain (e.g., uniform or Pareto) distribution, determine how many nodes will be assigned into each large square.
 Then, in each large square, randomly pick a small square and assign at most one future node to it (next page shows how to add future nodes).
Assign nodes: (a) Uniform distribution (b) Pareto distribution

Now, start to add nodes:

BRITE
Node-degree distribution – 5000 router nodes (Di Fatta et al., 2001)

Internet Topology
at Router Level
Routers = 1,204,038 Edges = 13,349,748 Average degree = 22.17 Average clustering = 0.73 Power exponent = 2.34
July 2010
CAIDA

Internet Topology
at AS level
AS nodes = 17,492 Edges = 47,804
Average degree = 5.4 Average clustering = 0.25 Power exponent = 2.13
July 2010
CAIDA

Geographic Layout of the Internet
(a) Router density (b) Human population density (Yook et al., 2002)

Geographic Layout of the Internet
Yook et al. (2002)

GeoBA model (Yook et al., PNAS 2002)
 Start with a lattice consisting of many small squares
 Assign to the squares a user population density (x, y)
 At each step, add a node i into a square centered at (x,y) its user population density (x, y)
 This new node i will bring in m new edges, and each edge connects to an existing node j of degree k j , with geographic distance dij to node i, according to the
probability (nonlinear preferential attachment)
(kj,dij)~ j d ij
where  and  are constant parameters.
k

GeoBA Model: Simulation/Data
Data
 =1 gives power-law
(Yook et al., PNAS 2002)

Facebook Modeling
Facebook: The largest social network today Existing Models:
 Scale-Free (BA) model
 Distance Social Network (DSN) model
 Asymmetric Weights Dynamic (AWD) model  Exponential Random Graph models
 Markov Random (MR) model  Random Triangle (RT) model

Existing Models

Existing Models

Henneberg Network
Step 1. Start with a small (triangularly) connected network. Step 2. Node addition: Add a new node to the existing network.
Connect it to a randomly-picked pair of existing nodes. Step 3. Edge addition: If the pair of old nodes were connected,
do nothing; otherwise, connect them with a new edge. Step 4. Repeat Steps 2 and 3 till the network has the desired size.
Original Model L. Henneberg (1911)

Facebook is Scale-Free Network
Different ways to displace

Modified Henneberg Model
Modified Henneberg Model
with preferential attachment connections

BREAK
10 minutes

Modeling the Internet
Starting from scale-free models …

Limitation
of most scale-free Internet models
Preferential Attachment (or, its variants):   ki
i j kj
They all use global preferential attachment –
 Every newly added node requires the connectivity information of all nodes in the network
 A real network only uses local preferential attachment with information of only some nodes in the network

Question: How to describe a topology of the AS-level Internet with localization property?
 The Internet consists of several sub-networks: each sub-network is called a “local-world”
 The newly added node only needs connectivity information of those nodes in a local-world
 The connections among different local-worlds are sparse
 The connections of nodes within the same local-world are dense

A Scale-Free Network Model for Internet
— Multi-Local-World (MLW) Model This model includes 4 events:
 Addition of local-worlds
 Addition of new nodes to local-worlds with preferential
attachments
 Addition and deletion of edges of new nodes to local-worlds  Addition of edges among local-worlds
G. Chen, Z. Fan and X. Li (2005), Z. Fan and G. Chen (2006, 2009)
Oregon data (1998)

MLW Model
Start with m isolated local-worlds, with
m0 nodes and e0 edges in each local-world Example:
Start with m  3 local-worlds (A, B, C), with m0  3 nodes (black circles) and e0  2 edges in each local-world
Each local-world has a unique identifier (red circle)

MLW Model
At each step, perform one of the five operations:
(i) With probability p a new local-world is created, which contains m0 nodes and e0 edges. Meanwhile, a unique identifier is generated for
this new local-world.
Local world D is created with probability p
(with m0  3 nodes (black circles)and e0 2edges)

MLW Model
(ii) With probability q, a new node is added to an existing local-world, which has m1 edges with the nodes within the same local-world:
First, a local-world  is selected at random. Then, a node to which the new node connects in the local-world
 is chosen with probability (k) ki
i (kj ) (1) j

MLW Model (Step (ii) continued)
In (1),  is the -th local-world in which node i locates, and the parameter   0 represents the “attractiveness” of node i which is used to govern the probability for “young” nodes to get new edges.
This process is repeated m1 times.

MLW Model (Step (ii) continued)
Example (continued) A new node j joins the network. First, it
selects the local-world C where it will locate, and then connects
an existing node ( m  1 ) in this local-world with preferential 1
attachment probability given by (1)

MLW Model
(iii) With probability r, m2 edges are added to
a chosen local-world:
First, a local-world  is selected at random.
Then, one end of an edge is chosen at random, while the other end of the edge is selected by (1)
This process is repeated m2 times

MLW Model (Step (iii) continued)
Example:
First, local-world C is chosen at random.
Then, m2  2 edges are added to this local-world.
One end of an edge is selected at random, while the other end of the edge is chosen with a probability given by (1)

MLW Model
(iv) With probability s, m3 edges are deleted
within a chosen local-world:
First, a local-world  is selected at random.
Then, one end of an edge is chosen at random,
while the other end of the edge is selected with probability
 ‘ ( k i )  1 (1   ( k i ) ) N (t) 1
(2) where N (t)represents the number of nodes within the
 -th local-world, and (ki ) is determined by (1) This process is repeated m3 times.

MLW Model (Step (iv) continued)
Example:
First, local-world C is chosen at random.
Then, m3  1 edge is deleted within this chosen local- world.
An end of the edge is selected at random, while the other end of the edge is chosen with probability given by (2)

MLW Model
(v) With probability u, a selected local-world
has m4 edges with the other existing local-worlds: First, randomly select a local-world and a node in
this local-world with probability given by (1).
Then, the selected node is acted as one end of an edge, while the other node of the edge, which is in another local-world chosen at random, is selected with probability given by (1).
This process is repeated m4 times.

MLW Model (Step (iv) continued)
Example:
Depending on the probability u, m4  1 link is added between two nodes in two different local-worlds.
Both ends of the link are chosen with preferential attachment according to a probability given by (1)

Illustration of a Resulting Network

MLW Model Degree Distribution has a power-law form:
P(k) t a(3mt(12p))
Here:
1/a  m b/a kb/a
0p,r,s,u1, 0q1,  11/a
1
pqrsu 1
a  qm  rm (q  m p  p)  sm p  2um 12034
c
b  qm1  c
(q  m0 p)c (q  m0 p)c rm2  rm2 (q  m0 p  p) 
(qm0 p) (qm0 p)c
c sm3 p
(qm0 p)c
 2sm3 (qm0 p)
 2um4 c

Evaluating the Internet models Internet Models at the AS-level:
Waxman model Transit-stub model
~Weibull distribution
Fluctuation-driven model
 BA model
 Generalized BA (GBA) model  Fitness model
 HOT model
MLW Model
Power-law distribution
GBA is also called EBA (Extended BA)

Evaluating the Internet models (cont.)
Fluctuation-driven model –
 BA model
 Generalized BA (GBA) model Fitness model
HOT model
MLW model
GBA = EBA
Exponentially growing network
Linearly growing networks

Evaluating the Internet models (cont.) Linearly growing
Number of Nodes
(from 2004 to 2010)
network
Fluctuation-driven model is NOT suitable for the AS-level Internet

Evaluating the Internet models (cont.) Power Exponent:
Internet snapshot on May 15, 2005
r = 2.2 for real Internet r = 3.0 for BA model
r = 1.5 for HOT model
BA and HOT models can NOT capture the scale- free feature of the Internet

Evaluating the Internet models (cont.)
Distance distributions of the Internet and of different scale-free models

Evaluating the Internet models (cont.)
BA, GBA, Fitness, and HOT models can NOT capture the small-world feature of the real Internet
Clustering coefficients as functions of the degree for the real Internet and the BA, GBA, Fitness, HOT, and MLW models.

Evaluating the Internet models (cont.)
Comparison of the average shortest path-lengths in the giant component for the real Internet and the five models studied.
f – Fraction of removed edges

Evaluating the Internet models (cont.) Comparison: Four Models vs Real Internet
BA
GBA
Fitness
MLW
Real Internet
(May 15,2005)
N
21999
21999
21999
21999
21999
C
0.003
0.01
0.01
0.24
0.46
d
4.14
3.49
3.71
3.45
3.49

3
2.69
2.45
2.36
2.18
max
27.82
62.83
39.16
111.87
141.12

Comparison of MLW Model with other models
Internet Modeling
Scale-free
feature
Small-world
feature
Community
structure
BA model
Yes
No
No
EBA model
Yes
Yes
No
Fitness
model
Yes
No
No
HOT model
Yes
No
No
MLW
model
YES
YES
YES
MLW model is better than the BA, EBA, Fitness and HOT models in capturing the scale-free and small-world features of the Internet

Further Evaluating the Internet models
Summary
MLW model is better than BA, EBA, Fitness, and HOT models in capturing the scale-free and small- world features of the Internet
Topological Statistics –
degree distribution, power-law exponent,
distance distribution, clustering coefficient, average shortest path-length, hierarchical clustering
But what about performances?
–

Comparison: What about performances? Robustness against random attacks
S f : the size of the largest component after a fraction of nodes, f, in the network are randomly removed.
S f / S0 measures the capability of the network in which nodes still can communicate each other after the f portion of nodes has been randomly removed.

Performance comparisons Traffic load distribution
MLW model does not perform well
T(r) – the ratio of the traffic load of the first r largest nodes over the total traffic load of the whole network

Verification of the methods used
Canonical variable analysis Bayesian decision theory
Topological measurements are projected into a reduced dimensional feature space by using canonical analysis, so that the Bayesian decision method can be applied onto a more representative feature space in a lower dimension
L. F. Costa, F. A. Rodrigues, G. Travieso, P. R. V. Boas, Advances in Physics 56(2007): 167

Comparison: Bayesian Test
Consider: average clustering coefficient, average distance,
and largest nonzero eigenvalue of adjacency matrix
Bayesian decision method

MLW model is most compatible with the Internet

Comparison: Hierarchical Clustering Algorithm
Applying the hierarchical clustering algorithm to evaluate different Internet models
Principle:
The sooner two networks are merged, the more similar they are
L. F. Costa, F. N. Silva,
J. Stat. Phys. 125(2006): 841
MLW model is closest to the Internet

 
    
  
Remarks
MLW is the best model for the AS-level Internet as compared to
Fluctuation-Driven, BA, EBA, and Fitness models
These comparisons were performed only based on part of the Internet features:
degree distribution
distance distribution
average path-length
clustering coefficient
robustness against random attack
The MLW model is rather complicated
More comparisons are needed
Internet is too complex to comprehend. As of today, there is no commonly-agreed model of the Internet
 Good models are badly needed

Brain and Internet
Any Inspiration ?

Topology
Brain  Internet
M. Bazhenov et al., J. Neuroscience, 2002 S. I. Cai et al., Proc. IEEE CDC, 2004 IXP (Internet Exchange Point)

Small-world Topology
Community Structure
Brain Topology
D. D. Bock et al., Nature, 2011

D. Krioukov et al., Scientific Report, 2012

Brain Topology
Internet (CAIDA Data); Trust (Social Network); de Sitter (Universe Space-time Data) N = 24,000
D. Krioukov et al., Scientific Report, 2012

Brain Topology
Brain Neural Networks: functioning Hierachical Structure
Upper level: High-frequency neuronal bursting Middle level: … …
Lower level: Diurnal neuroendocrine rhythm
J. A. Robert, et al, The heavy tail of the human brain, Neuobiology, 2014

Brain Topology
J. A. Robert, et al, The heavy tail of the human brain, Neuobiology, 2014

Brain Topology
Brain Internet
J. A. Robert, et al, Neuobiology, 2014 Faloutsos (3 brothers), ACM SIGCOMM, 1999

Brain Topology
Degree distribution of small-world brain functional network S. Achard, et al, Neurobiology, 2006

Brain Topology
Degree distribution of small-world brain anatomical network Yong He, et al, Cerebral Cortex, 2007; PLoS One, 2011

Inspiration
Structure:
Layers + Communities Feature: Small-world Distribution:
Internet
Power-law with flat head and heavy tail

Social Networks
are typical
Small-World
Networks
Human mobility and behaviors both affect Internet topological evolution

Brain Facebook Structure

Internet Modeling Graph Theory
 AS-level:
> nodes are domains (AS)
> edges are peering relationships > modeling manageable
 Router-level:
> nodes are routers
> edges are one-hop IP connections > partially manageable
 PC-level:
> nodes are PCs, hand-held sets > edges are optical fibers
> modeling not manageable

End