Entropic Origin of Disassortativity in Complex Networks

Why are most empirical networks, with the prominent exception of social ones, generically degree-degree anticorrelated? To answer this long-standing question, we define the ensemble of correlated networks and obtain the associated Shannon entropy. Maximum entropy can correspond to either assortative (correlated) or disassortative (anticorrelated) configurations, but in the case of highly heterogeneous, scale-free networks a certain disassortativity is predicted—offering a parsimonious explanation for the question above. Our approach provides a neutral model from which, in the absence of further knowledge regarding network evolution, one can obtain the expected value of correlations. When empirical observations deviate from the neutral predictions—as happens for social networks—one can then infer that there are specific correlating mechanisms at work.

Figure 1

Evolution of the Internet at the AS level. Empty (blue) squares and circles: entropy per node of randomized networks in the fully random and in the configuration ensembles, as obtained by Bianconi (hence the “$B$” superscription) [11]. Filled (red) triangles and diamonds: Shannon entropy for an ER network and a scale-free one with $\gamma =2.3$, respectively.

Figure 2

Shannon entropy of correlated scale-free networks against parameter $\beta$ (left panel) and against Pearson’s coefficient $r$ (right panel), for various values of $\gamma$ (increasing from bottom to top). $⟨k⟩=10$, $N={10}^4$.

Figure 3

Lines from top to bottom: $r$ at which the entropy is maximized, $r^{*}$, against $\gamma$ for random scale-free networks with mean degrees $⟨k⟩=\frac{1}{2}$, 1, 2, and 4 times $k_0=5.981$, and $N=N_0=10697$ nodes ($k_0$ and $N_0$ correspond to the values for the Internet at the AS level in 2001 [7], which had $r=r_0=-0.189$). Symbols are the values obtained in 7 as those expected solely due to the one-edge-per-pair restriction (with $k_0$, $N_0$ and $\gamma =2.1$, 2.3, and 2.5). Inset: $r^{*}$ against $N$ for networks with fixed $⟨k⟩/N$ (same values as the main panel) and $\gamma =2.5$; the arrow indicates $N=N_0$.

Figure 4

Level of assortativity that maximizes the entropy $r^{*}$ for various real-world, scale-free networks, as predicted theoretically by Eq. (1) (solid symbols) and as directly measured (empty symbols), against exponent $\gamma$.