Graph Analytics L 5 - Home Pages of People@DU

Graph Analytics L 5
Vasudha Bhatnagar
Special Topics in Data Mining
Graph Analytics L 5
Barabasi-Albert Graph Model
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
6 Sept 2014
Vasudha Bhatnagar
Department of Computer Science,University of Delhi
Delhi, India.
.1
Outline
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
1 Barabasi-Albert Graph Model
2 Estimation of degree distribution
Discreet Approach
Continuous Approach
.2
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
1
Dynamic model with two parameters (n, q)
2
Initially at time t0 , n0 = n nodes are present in the the
graph G0
Estimation of degree
distribution
Discreet Approach
Continuous Approach
3
All nodes have equal degree, say q
4
G0 has m0 = qn/2 edges
5
At each time step, one node with q links is added to the
graph
6
The new node links with existing n nodes with probability
proportional to their degrees
7
Probability that a new node links with vj is π(vj ) =
d
Pj
i
di
.3
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
• At time t, number of nodes nt in graph Gt = n0 + t
• At time t, number of edges mt in graph Gt = m0 + qt
As t −→ ∞, nt ' t and mt ' qt
• Total degree at time t = 2(m0 + tq)
• Probability of linkage of node vj at time t is πt (vj ) =
dj
2(m0 +qt)
.4
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree distribution
Estimation of degree
distribution
Discreet Approach
Continuous Approach
• Degree distribution changes as the network evolves with time
• However, over a long period of time (t −→ ∞), it becomes
stationary
• Objective of analysis is to find the stationary distribution
Two approaches
• Discreet Approach (master-equation method)
• Continuous Approach (mean-field method)
.5
Graph Analytics L 5
• Let Xt be a random variable denoting the degree of a node
Vasudha Bhatnagar
in Gt
• Let ft (k ) denote the probability mass function for Xt i.e.
ft (k ) =
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
.6
Graph Analytics L 5
• Let Xt be a random variable denoting the degree of a node
Vasudha Bhatnagar
in Gt
• Let ft (k ) denote the probability mass function for Xt i.e.
ft (k ) =
nt (k )
nt .
• At time-step t + 1, the probability πt (k ) of a node with
degree k is chosen for linkage
t (k )
πt (k ) = Pk ∗n
(i∗nt (i))
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
i
• Dividing the numerator and denominator by nt ,
Pk ∗ft (k )
i (i∗ft (i))
k ∗ft (k )
E[Xt ]
k ∗ft (k )
2q
πt (k ) =
=⇒
=⇒
Consolidate....
ft (k ) is probability that a node in Gt has degree k (nt (k )/nt )
πt (vi ) is probability that node vi in Gt is picked for linkage
(di /total − degree − in − Gt )
πt (k ) is probability that node with degree k in Gt is picked for
linkage (k ∗ ft (k )/2q)
.6
Graph Analytics L 5
Consider the change in the number of nodes with degree k
Net change = (nt + 1) ∗ ft+1 (k ) − nt ∗ ft (k )
= (t + 1) ∗ ft+1 (k ) − t ∗ ft (k )
—- (1) Nodes that had degree (k − 1), and now have new
linkages are added - q ∗ πt (k − 1)
≈ 12 ∗ (k − 1) ∗ ft (k − 1)
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
.7
Graph Analytics L 5
Consider the change in the number of nodes with degree k
Net change = (nt + 1) ∗ ft+1 (k ) − nt ∗ ft (k )
= (t + 1) ∗ ft+1 (k ) − t ∗ ft (k )
—- (1) Nodes that had degree (k − 1), and now have new
linkages are added - q ∗ πt (k − 1)
≈ 12 ∗ (k − 1) ∗ ft (k − 1)
Holds when k > q
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
Nodes that had degree k , and now have new linkages are
subtracted - q ∗ πt (k )
= 21 ∗ (k ) ∗ ft (k )
• Net change = 12 ∗ (k − 1) ∗ ft (k − 1) − 12 ∗ (k ) ∗ ft () — (2)
Equating (1) and (2)
(t + 1) ∗ ft+1 (k ) − t ∗ ft (k ) =
Master Eqn for k > q
1
2
∗ (k − 1) ∗ ft (k − 1) − 12 ∗ (k ) ∗ ft (k )
.7
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Consider boundary condition k = q
Continuous Approach
Newly added node increase the k degree nodes by 1
When it links to q ∗ πt (k ) nodes, their degree becomes k + 1
Net change = 1 − q ∗ πt (k ) = 1 − 12 k ∗ ft (k ) Master Equation
for the boundary condition k = q
(t + 1)ft+1 (k ) − tft (k ) = 1 − 12 k ∗ ft (k )
.8
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Goal is to obtain time-invariant solution to estimates degree
distribution (f (k ), k = 1 . . .)
i.e. ft+1 (k ) = ft (k ) = f (k )
Discreet Approach
Continuous Approach
Master Equations to be solved
(1) (t + 1)ft+1 (k ) − tft (k ) = 1 − 21 k ∗ ft (k ) - for condition k = q
(2)
(t + 1) ∗ ft+1 (k ) − t ∗ ft (k ) = 12 ∗ (k − 1) ∗ ft (k − 1) − 12 ∗ (k ) ∗ ft (k )
for condition k > q
.9
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
Solving for boundary condition for stationary condition i.e.
ft+1 (k ) = ft (k ) = f (k )
2
f (q) = 2+q
Solving master equation for k > q, f (k ) ∝ k −3
=⇒ degree distribution follows power law
.10
Graph Analytics L 5
Mean-field method
Vasudha Bhatnagar
Convert n-body problem to one-body problem
• Let ki = dt (i) denote the degree of vertex vi at time t
• πt (i) is the probability that the newly added node u links to vi
• Change in degree of vi per time-step is qπt (i)
dki
ki
i
• Rate of change of ki with time
= q ∗ πt (i) = q∗k
2qt = 2t
dt
After rearranging:
R dki
R dt
=
ki
2t
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
dki
dt
=
and Integrating
ki
2t
√
ki = α t,
(1)
where α is a constant
Initial degree for any node is q, yields boundary condition
ki = q at time t = ti
Substituting above gives α = qti , Rewrite (1)
ki =
q√
t,
ti
(2)
.11
Graph Analytics L 5
Recall fundamentals in statistics:
• pdf: f (k ); Distribution function : F (k ) = P(K ≤ k )
dF
• f (k ) =
dk
1
, if X ∼ U(a, b)
• f (x) = b−a
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
.12
Graph Analytics L 5
Recall fundamentals in statistics:
• pdf: f (k ); Distribution function : F (k ) = P(K ≤ k )
dF
• f (k ) =
dk
1
, if X ∼ U(a, b)
• f (x) = b−a
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
Consider
√ Ft (k ) = P(ki ≤ k )
= P( tq t ≤ k )
i
= P(ti >
tq 2
)
k2
= 1 − P(ti ≤
2
tq 2
)
k2
= 1 − qk 2 , Since the nodes are added uniformly at rate of 1 per
time unit
.12
Graph Analytics L 5
Recall fundamentals in statistics:
• pdf: f (k ); Distribution function : F (k ) = P(K ≤ k )
dF
• f (k ) =
dk
1
, if X ∼ U(a, b)
• f (x) = b−a
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
Consider
√ Ft (k ) = P(ki ≤ k )
= P( tq t ≤ k )
i
= P(ti >
tq 2
)
k2
= 1 − P(ti ≤
2
tq 2
)
k2
= 1 − qk 2 , Since the nodes are added uniformly at rate of 1 per
time unit
We need to find degree distribution i.e. f (k )
2
d(1 − qk 2 )
dF
f (k ) =
=
dk
dk
2
= 2q
k3
∝ k −3
.12
Graph Analytics L 5
Vasudha Bhatnagar
Barabasi-Albert Graph
Model
Estimation of degree
distribution
Discreet Approach
Continuous Approach
Diameter of BA graph
d(Gt ) = O( logloglogntnt )
Expected clustering coefficient of BA graph
2
O( (lognnt t ) )
.13

Download Report