Growing optimal scale-free networks via likelihood

Preferential attachment, by which new nodes attach to existing nodes with probability proportional to the existing nodes' degree, has become the standard growth model for scale-free networks, where the asymptotic probability of a node having degree $k$ is proportional to $k^{-\gamma }$. However, the motivation for this model is entirely ad hoc. We use exact likelihood arguments and show that the optimal way to build a scale-free network is to attach most new links to nodes of low degree. Curiously, this leads to a scale-free network with a single dominant hub: a starlike structure we call a superstar network. Asymptotically, the optimal strategy is to attach each new node to one of the nodes of degree $k$ with probability proportional to $\frac{1}{N+\zeta \left(\gamma \right){(k+1)}^{\gamma }}$ (in a $N$ node network): a stronger bias toward high degree nodes than exhibited by standard preferential attachment. Our algorithm generates optimally scale-free networks (the superstar networks) as well as randomly sampling the space of all scale-free networks with a given degree exponent $\gamma$. We generate viable realization with finite $N$ for $1\ll \gamma <2$ as well as $\gamma >2$. We observe an apparently discontinuous transition at $\gamma \approx 2$ between so-called superstar networks and more treelike realizations. Gradually increasing $\gamma$ further leads to reemergence of a superstar hub. To quantify these structural features, we derive a new analytic expression for the expected degree exponent of a pure preferential attachment process and introduce alternative measures of network entropy. Our approach is generic and can also be applied to an arbitrary degree distribution.

Figure 1

Representative realizations of the optimal scale-free network generation scheme with $\gamma =1.93$, 1.94, 1.95, 2.0, and 2.5 ($N={10}^3$). For $\gamma \ll 2$ the algorithm is unable to find viable networks; however, for $1\ll \gamma <2$ viable networks do exist (certainly for finite $N$ it is easy to see why this is the case), and such dense networks are, in fact, quite plentiful [5]. As $\gamma$ approaches 2.0 there is a sudden phase transition to large treelike networks with a proliferation of cross-links. As $\gamma$ increases further, the cross-links gradually become scarcer and the networks we obtain evolve from highly treelike back to hub-centric superstar networks.

Figure 2

(a) As we vary $\gamma \in [1.5,5]$ we generate optimal and random realization of our scale-free network growth algorithm. We plot $\gamma$ against $\widehat{\gamma }$ (the maximum likelihood estimate of the scale-free exponent from the sample degree distribution) for both optimal (red) and partially random (green: slightly larger variance at extrema) realizations with $N={10}^4$ nodes. The identity line is also shown. (b) Typical degree distribution for BA (blue, squares), optimal attachment (red, stars), and semirandom ($q=0.5$, green asterisks). The partially random scheme (with $q=0.5$ as described in the text) did not significantly affect the final degree histogram, and yet this allowed much more variation in the resultant networks; for $q<1$ we see a transition from superstar networks towards the usual results of BA.

Figure 3

For $\gamma \in (1,5]$ we compute optimal realizations of our scale-free network generation algorithms ($N={10}^4$). We show (a) assortativity (linear Pearson correlation coefficient), (b) global clustering coefficient, (c) shortest path length, and (d) two measures of network entropy. Note that the hublike nature of networks with large $\gamma$ is evident from the shortest path length, while the global clustering coefficient drops to zero at $\gamma \approx 2$. Interestingly, assortativity remains negative, peaking with a value of 0 at $\gamma \approx 2$ and then declines rapidly. The shortest path length has clear evidence of the undersize networks for $\gamma \ll 2$, an abrupt transition to treelike networks near 2, and then a gradual decay to a single dominant hub as $\gamma$ increases further. The two network entropy statistics compute the entropy of the degree sequence [13, 14] (lower, red/blue line) and the entropy of the link-degree coincidences (upper, magenta/green line). Both entropy measures show an abrupt, nondifferentiable transition at $\gamma \approx 2$. Each data point reported in these figures is the corresponding statistic values estimated from a single network (with $\gamma$ increasing between simulations in steps of size 0.01); variance can be inferred from the smoothness of the plotted curves.

Figure 4

We generate BA networks (blue solid lines), estimate the scale exponent $\gamma$, and then generate networks according to our first two schemes with this estimated value $\widehat{\gamma }$ and $N={10}^4$ nodes (red dot-dashed and green dashed lines). Displayed here are the usual network properties estimated from the resultant networks and depicted as histograms (generated from 100 network realizations via a Gaussian kernel smoothing algorithm): (a) assortativity, (b) shortest path length, and (c) estimated exponent $\widehat{\gamma }$ (adaptive binning). Remarkably the distributions reported for the optimal scheme (red dot-dashed) is almost identical to the results of the randomization scheme ($q=0.5$ and green dashed lines). As assortativity is a linear measure, it is not particularly good at describing the detail of degree-degree correlation. Panels (d)–(f) illustrate scatter plots (circle size and colour proportional to likelihood/number) of actual degree-degree structure for representative networks: (d) BA, (e) optimal, and (f) random.

Figure 5

Representative realizations of the BA method, optimal method (Sec. 2), and an imposed $C_{\max }$ with $C_{\max }=20,100,200,300,400,900$ ($N={10}^3$) (Sec. 3). When $C_{\max }$ is quite small, i.e., $C_{\max }\le 100$, networks look like the BA network because of a scattered structure. For $C_{\max }>100$, networks tend to have less hubs and gradually evolve to concentrated superstar networks, equivalent to the optimal method.

Figure 6

In (a) and (b), we apply the optimal method, the BA method and the truncated $C_{\max }$ method with different $C_{\max }$ to generate scale-free networks. For each method or each value of $C_{\max }$, we generate 100 networks, and then display the histogram of common properties of scale-free networks: assortativity and shortest path length. The number on the top of the bars indicates the $C_{\max }$ value. From panels (a) and (b) we can see that when the $C_{\max }$ value is large, the networks we have very similar properties to the optimal maximum likelihood networks. This makes sense because if $C_{\max }$ is large, the cutoff function has so little power that the optimal method and the $C_{\max }$ method are almost the same. Then, when we decrease $C_{\max }$, the properties of networks move towards those of BA networks. Notably, when $C_{\max }$ is small, the properties of $C_{\max }$ networks are quite similar to those of BA networks. All of this indicates that the $C_{\max }$ method can actually link the BA method and optimal method. Panel (c) illustrates relative probability (relative to optimal maximum likelihood network) of $C_{\max }$ networks, with $C_{\max }$ ranging from 15 to $N$. Surprisingly, when $C_{\max }$ is neither very big nor very small, the relative probability will be higher than 1, which means the probability of truncated $C_{\max }$ network will be bigger than optimal networks. This suggests that the truncated approach provides a useful middle ground to generate networks “between” BA and the optimal growth networks.

Figure 7

Panel (a) illustrates our constructive definition of hubs. Starting with a fixed $\gamma =2.47$ (corresponding to the estimated $\gamma$ in comparable BA networks), we construct a straight line in the degree distribution on the log-log scale (the solid red line) $log\left(n_k\right)=log\left(n_1\right)-\gamma log\left(k\right)$ where $k$ is degree and $n_k$ is the number of nodes with degree $k$. The intersection of this line and $x$ axis occurs at $log\left(n_1\right)/\gamma$. As there is some variability at the end of the degree distribution, we add $\theta$ to exclude the tail. In panel (a), the green diamonds show the degree distribution of $C_{\max }$ network with $C_{\max }=25$, and blue circles show the BA network. Here we use $\theta =3$ and draw the minimum degree of hubs as the black line. From (a) we can see our definition successfully distinguishes the hubs in the networks. In (b), for $C_{\max }\in [21,36]$ and $\gamma =2.47$ (the estimated $\gamma$ of BA method when minimum degree is 1), we compute realizations of $C_{\max }$ method and the number of hubs in the representative networks. The orange, green, blue, and yellow areas (from bottom to top in the plot) indicate the number of hubs will be 1, 2, 3, 4 with particular $C_{\max }$ and $N$ in the representative areas. Note that if we fix $C_{\max }$, when we increase the size of networks, the number of hubs will increase; if we fix $N$ and increase $C_{\max }$, the number of hubs will decrease.

Figure 8

Left panel: Expected values of $\gamma$ as a function of $m$ [Eq. (A2)] (heavy magenta line) and estimated values of $\gamma$ from 30 independent realizations of BA networks of size $N$ (mean $\pm$ standard deviation). We take $m\in [1,10]$ and $N={10}^3$ (red), ${10}^4$ (green), ${10}^5$ (blue). Right panel: $\gamma$ as a function of $m$ computed via the solution of (A4) (stars) and estimated from a function fit of the form $\widehat{\gamma }\left(m\right)=3-{(m+\alpha )}^{-\beta }$. The best fit (obtained from a fit on $m\in [1,10]$) is then extrapolated over the domain. Parameter values are $\alpha =0.9205$ and $\beta =0.9932$.