Objectives
- growth models for complex network
- feedback in network growth: preferential attachment
Questions
- what is a master equation? How can it be used to analyze network growth models?
- consider the uniform attachment model and write down the master equation for $P(k,s,t)$ and $P(k,t)$.
- consider the preferential attachment model and write down the differential equation for the evolution of $k_i(t)$
- what are the final degree distributions for a growth model with uniform attachment and preferential attachment?
- uniform: normal distribution
- preferential: zipf distribution?
- in the preferential attachment model, how does the number of links m added in each step affect the final degree distribution?
- affect the peak?
- explain why the random walk model gives rise to preferential attachment
- explalin why the copying model gives rise to preferential attachment.
Keywords
attachment strategy
- preferential attachment
master equation
time-dependent degree distribution
Attachment rules
Uniform attachment
new nodes form links to existing nodes chosen uniformly at random
degree distribution
exponentially shaped
e.g. much like those generated by Erdos-Renyi random graph models
Preferential attachment
new nodes preferentially form links to highly connected nodes.
degree distribution
scale-free degree distribution, log-log plot a line
Analytical Approaches
Two main tools:
- master equation: for discrete perspective
- continuum limit approximation: for continuous perspective
Master equation/Rate equation
Definition
the first-order differential equations that describe the evolution of probabilities over time.
Case: uniform attachment
Settings
- node: each time, add a new node into the system. That is at time $t$, there are $t$ nodes.
- link: each newly added node uniformly chooses a random existing node. $p=\frac{1}{t}$
- observation: for an existing node, its probability to receive a new link decays over time.
Formula
The probability of a node added at time s has the degree $k$ at time $t+1$
$$
p(k,s,t+1)=\frac{1}{t}p(k-1,s, t)+(1-\frac{1}{t})p(k,s,t)
$$
the first item: the node has degree $k-1$ at time $t$
the second: the node has degree $k$ at time $t$.
the initial condition
$$
p(k,1,1)=\delta_{k,0}
$$
- $k=0$, the value is 1
- otherwise, the value is 0.
the boundary condition
$$
p(k,t,t)=\delta_{k,1}
$$
Degree distribution, time-dependent
$$
P(k,t)=\frac{1}{t}\sum_{s}P(k,s,t)
$$
Change over time
$$
(t+1)p(k,t+1)-(t-1)p(k,t-1)=p(k-1,t)+\delta_{k,1}
$$
limiting value
$$
p(k)=\frac{p(k-1)+\delta_{k,1}}{2}=2^{-k}
$$
- $p(0)=0$
- $\delta_{1,1}=1$
- exponentially-shape degree distribution, not like ER networks.
- because there is a dependence of the average degree on the birth time of a node.
Mean degree
$$
\langle k\rangle = \sum_{i=1}^{\infty}\frac{k}{2^k}=2
$$
how to calculate?
$$
|x|<1: f(x)=\sum_{n=1}^{\infty}x^n=\frac{x}{1-x},
$$
$$
\Rightarrow xf’(x)=\sum_{n=1}^{\infty}nx^n=\frac{x}{(1-x)^2}
$$
Case: Preferential attachment
Settings
node: each time, add a new node into the system. That is at time $t_i$, there are $i$ nodes.
link: each newly added node forms m links to existing nodes and the probability to each exsiting node is Positive feedback
$$
p(v_i)=\frac{k_i(t)}{\sum_jk_j(t)}
$$
Formula
For each existing node $x_i$, the expectation of its degree increase at time t is m\times the probability of one link to it.
Generating to continuous time, we have
$$
\frac{\mathrm{d}k_i(t)}{\mathrm{d}t}=m\cdot\frac{k_i(t)}{\sum_jk_j(t)=2mt}=\frac{k_i(t)}{2t}
$$
- initial condition: $k_i(t_i)=m$
We get
$$
k_i(t)=m(\frac{t}{t_i})^{\frac{1}{2}}
$$
- node degrees grow as square root of time
- node degrees are age-dependent.
Degree distribution
After a series of complex calculation,
$$
p(k)=2m^2k^{-3}\propto k^{-3}
$$
- degree distribution follows a power-law distribution with parameter 3.
Matthew effect
A dynamics by which “the rich get richer”, first-mover advantage. i.e. the degree of those nodes that already have the most links will grow fastest.
Preferential attachment
Simple attachment model
limitation:
- global knowledge. The newly added node needs to have the global knowledge.
- Preferential attachment here is an observation not mechanism.
Copying model
This is a local mechanism model.
A newly introduced node randomly selects a target node and links to it, as well as to all/some ancestor nodes of the target node.
Random walk model
new nodes start random walk at random node and form a link every l steps
- produce different clusters depending on the distance l: small l will lead to higher clustering
Heterogenous node fitness
$$
p(v_i)=\frac{\eta_ik_i(t)}{\sum_j\eta_jk_j(t)}
$$
Relation with Scale-free network
Preferential attachment is a sufficient condition of scale-free network, not a necessary condition.
Not all scale-free network are generated by preferential attachment.
