Scale-Free Network Growth by Ranking

Network growth is currently explained through mechanisms that rely on node prestige measures, such as degree or fitness. In many real networks, those who create and connect nodes do not know the prestige values of existing nodes but only their ranking by prestige. We propose a criterion of network growth that explicitly relies on the ranking of the nodes according to any prestige measure, be it topological or not. The resulting network has a scale-free degree distribution when the probability to link a target node is any power-law function of its rank, even when one has only partial information of node ranks. Our criterion may explain the frequency and robustness of scale-free degree distributions in real networks, as illustrated by the special case of the Web graph.

Figure 1

Inset: In-degree distributions for networks built according to our model (ranking by degree). The number of nodes is $N={10}^6$. Data are averaged within logarithmic bins of degree and shifted along the $y$ axis for illustration purposes. The main curve plots the degree distribution exponent $\gamma$ as a function of $\alpha$, from simulations with nodes ranked by various criteria. Error bars represent standard errors on the best fit estimates of $\gamma$, while the dashed line is the prediction of Eq. (4).

Figure 2

Degree distributions for networks grown according to the proposed model, with incomplete information. Inset: Regions of the parameter space for the four regime cases. The marked points correspond to the $(\alpha ,\beta )$ values that generate the distributions in the main plot.