Price's model

Considering a directed graph with n nodes. Let $p\_k$ denote the fraction of nodes with degree k so that $\backslash textstyle\backslash 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, $\backslash textstyle\backslash sum\_\{k\}\{kp\_k\}=m$, is fixed over time, and consequently m is not restricted to the 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 proportion to the number of papers that cite it. The caveat to such an idea is that, since no new paper is cited when it is joined to the network, it is going to have zero probability of being cited in the future (contrary to what happens in real life). To overcome this, Price proposed that an attachment should be proportional to some $k+k\_0$ with $k\_0$ an arbitrary constant. Price proposed $k\_0=1$, such that an initial citation is associated with the paper itself. The probability of a new edge connecting to any node with a degree k is now

: $\backslash frac\{(k+1)p\_k\}\{\backslash sum\_k\; (k+1)p\_k\}=\backslash frac\{(k+1)p\_k\}\{m+1\}$

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 $p\_\{k,n\}$:

: $(n+1)p\_\{k,n+1\}-np\_\{k,n\}=[kp\_\{k-1,n\}-(k+1)p\_\{k,n\}]\backslash frac\{m\}\{m+1\}\backslash text\{\; for\; \}k\backslash geq\; 1,$

and

: $(n+1)p\_\{0,n+1\}-np\_\{0,n\}=1-p\_\{0,n\}\backslash frac\{m\}\{m+1\}\backslash text\{\; for\; \}k=0.$

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

:

After some manipulation, the expression above yields to

: $p\_0=\backslash frac\{m+1\}\{2m+1\}$

and

: $p\_k=\backslash frac\{k!\}\{(k+2+1/m)\backslash cdots(3+1/m)\}p\_0=(1+1/m)\backslash mathbf\{B\}(k+1,2+1/m),$

with $\backslash mathbf\{B\}(a,b)$ being the Beta-function. As a consequence, $p\_k\backslash sim\; k^\{-(2+1/m)\}$. This is identical to saying that $p\_k$ follows a power-law distribution with exponent $\backslash 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.

It is straightforward how to generalize the above results to the case when $k\_0\backslash neq\; 1$. Basic calculations show that

: $p\_k=\backslash frac\{m+k\_0\}\{m(k\_0+1)+k\_0\}\backslash frac\{\backslash mathbf\{B\}(k+k\_0,2+k\_0/m)\}\{\backslash mathbf\{B\}(k\_0,2+k\_0/m)\},$

which once more yields to a power law distribution of $p\_k$ with the same exponent $\backslash alpha=2+k\_0/m$ for large k and fixed $k\_0$.

The key difference from the more recent Barabási–Albert model is that the Price model produces a graph with directed edges while the Barabási–Albert model is the same model but with undirected edges. The direction is central to the citation network application which motivated Price. This means that the Price model produces a directed acyclic graph and these networks have distinctive properties.

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{{citation | last1=Evans | first1=T.S. |last2=Calmon | first2=L. |last3=Vasiliauskaite | first3=V. | title=The Longest Path in the Price Model | journal=Scientific Reports | volume=10 | date=2020 | issue=1 | doi=10.1038/s41598-020-67421-8 | pages=10503| pmid=32601403 | pmc=7324613 | arxiv=1903.03667 | bibcode=2020NatSR..1010503E }} $\backslash ln(n)$

For further discussion, see,{{cite journal | last1=Dorogovtsev | first1=S. N. | last2=Mendes | first2=J. F. F. | last3=Samukhin | first3=A. N. | title=Structure of Growing Networks with Preferential Linking | journal=Physical Review Letters | volume=85 | issue=21 | date=2000-11-20 | issn=0031-9007 | doi=10.1103/physrevlett.85.4633 | pages=4633–4636| pmid=11082614 | arxiv=cond-mat/0004434 | bibcode=2000PhRvL..85.4633D | s2cid=118876189 }}{{cite journal | last1=Krapivsky | first1=P. L. | last2=Redner | first2=S. | title=Organization of growing random networks | journal=Physical Review E | publisher=American Physical Society (APS) | volume=63 | issue=6 | date=2001-05-24 | issn=1063-651X | doi=10.1103/physreve.63.066123 | page=066123| pmid=11415189 |arxiv=cond-mat/0011094| bibcode=2001PhRvE..63f6123K | s2cid=16077521 }} and.{{cite journal | last1=Dorogovtsev | first1=S. N. | last2=Mendes | first2=J. F. F. | title=Evolution of networks | journal=Advances in Physics | volume=51 | issue=4 | year=2002 | issn=0001-8732 | doi=10.1080/00018730110112519 | pages=1079–1187|arxiv=cond-mat/0106144| bibcode=2002AdPhy..51.1079D | s2cid=429546 }}Krapivsky, P. L. and Redner, S., Rate equation approach for growing networks, in R. Pastor-Satorras and J. Rubi (eds.), Proceedings of the XVIII Sitges Conference on Statistical Mechanics, Lecture Notes in Physics, Springer, Berlin (2003). 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{{says who|date=January 2023}}.

{{reflist}}

• {{cite journal | last=Newman | first=M. E. J. | title=The Structure and Function of Complex Networks | journal=SIAM Review | volume=45 | issue=2 | year=2003 | issn=0036-1445 | doi=10.1137/s003614450342480 | pages=167–256| arxiv=cond-mat/0303516 | bibcode=2003SIAMR..45..167N | s2cid=221278130 }}

Category:Mathematical modeling

Category:Networks