Price's model

Price's model (named after the physicist

Considering a directed graph with n nodes. Let ${\displaystyle p_{k}}$ denote the fraction of nodes with degree k so that ${\displaystyle \sum _{k}{p_{k}}=1}$. Each new node has a given out-degree (namely those papers it cites) and it is fixed in the long run. This does not mean that the out-degrees can not vary across nodes, simply we assume that the mean out-degree m is fixed over time. It is clear, that ${\displaystyle \sum _{k}{kp_{k}}=m}$, consequently m is not restricted to integers. The most trivial form of preferential attachment means that a new node connects to an existing node proportionally to its in-degrees. In other words, a new paper cites an existing paper in proportional to its in-degrees. The caveat of such idea is that no new paper is cited when it is joined to the network so it is going to have zero probability of being cited in the future (which necessarily is not how it happens). To overcome this, Price proposed that an attachment should be proportional to some ${\displaystyle k+k_{0}}$ with ${\displaystyle k_{0}}$ constant. In general ${\displaystyle k_{0}}$ can be arbitrary, yet Price proposes a ${\displaystyle k_{0}=1}$, in that way an initial citation is associated with the paper itself (so the proportionality factor is now k + 1 instead of k). The probability of a new edge connecting to any node with a degree k is

${\displaystyle {\frac {(k+1)p_{k}}{\sum _{k}(k+1)p_{k}}}={\frac {(k+1)p_{k}}{m+1}}}$

Evolution of the network

The next question is the net change in the number of nodes with degree k when we add new nodes to the network. Naturally, this number is decreasing, as some k-degree nodes have new edges, hence becoming (k + 1)-degree nodes; but on the other hand this number is also increasing, as some (k − 1)-degree nodes might get new edges, becoming k degree nodes. To express this net change formally, let us denote the fraction of k-degree nodes at a network of n vertices with ${\displaystyle p_{k,n}}$:

${\displaystyle (n+1)p_{k,n+1}-np_{k,n}=[kp_{k-1,n}-(k+1)p_{k,n}]{\frac {m}{m+1}}{\text{ for }}k\geq 1,}$

and

${\displaystyle (n+1)p_{0,n+1}-np_{0,n}=1-p_{0,n}{\frac {m}{m+1}}{\text{ for }}k=0.}$

To obtain a stationary solution for ${\displaystyle p_{k,n+1}=p_{k,n}=p_{k}}$, first let us express ${\displaystyle p_{k}}$ using the well-known master equation method, as

${\displaystyle p_{k}={\begin{cases}[kp_{k-1}-(k+1)p_{k}]{\frac {m}{m+1}}&{\text{for }}k\geq 1\\1-p_{0}{\frac {m}{m+1}}&{\text{for }}k=0\end{cases}}}$

After some manipulation, the expression above yields to

${\displaystyle p_{0}={\frac {m+1}{2m+1}}}$

and

${\displaystyle p_{k}={\frac {k!}{(k+2+1/m)\cdots (3+1/m)}}p_{0}=(1+1/m)\mathbf {B} (k+1,2+1/m),}$

with ${\displaystyle \mathbf {B} (a,b)}$ being the Beta-function. As a consequence, ${\displaystyle p_{k}\sim k^{-(2+1/m)}}$. This is identical to saying that ${\displaystyle p_{k}}$ follows a power-law distribution with exponent ${\displaystyle \alpha =2+1/m}$. Typically, this places the exponent between 2 and 3, which is the case for many real world networks. Price tested his model by comparing to the citation network data and concluded that the resulting m is feasible to produce a sufficiently good power-law distribution.

Generalization

It is straightforward how to generalize the above results to the case when ${\displaystyle k_{0}\neq 1}$. Basic calculations show that

${\displaystyle p_{k}={\frac {m+k_{0}}{m(k_{0}+1)+k_{0}}}{\frac {\mathbf {B} (k+k_{0},2+k_{0}/m)}{\mathbf {B} (k_{0},2+k_{0}/m)}},}$

which once more yields to a power law distribution of ${\displaystyle p_{k}}$ with the same exponent ${\displaystyle \alpha =2+k_{0}/m}$ for large k and fixed ${\displaystyle k_{0}}$.

Properties

The key difference from the more recent

For example, in a directed acyclic graph both longest paths and shortest paths are well defined. In the Price model the length of the longest path from the n-th node added to the network to the first node in the network, scales as^[4] ${\displaystyle \ln(n)}$

Notes

For further discussion, see,^[5][6] and.^[7][8] Price was able to derive these results but this was how far he could get with it, without the provision of computational resources. Fortunately, much work dedicated to preferential attachment and network growth has been enabled by recent technological progress^{[according to whom?]}.

References