Shannon and von Neumann entropy of random networks with heterogeneous expected degree

Entropic measures of complexity are able to quantify the information encoded in complex network structures. Several entropic measures have been proposed in this respect. Here we study the relation between the Shannon entropy and the von Neumann entropy of networks with given expected degree sequence. We find in different examples of network topologies that when the degree distribution contains some heterogeneity, an intriguing correlation emerges between the two entropic quantities. This results seems to suggest that heterogeneity in the expected degree distribution is implying an equivalence between a quantum and a classical description of networks, which respectively corresponds to the von Neumann and the Shannon entropy.

Figure 1

Laplacian spectra of dense networks with exponential expected degree distribution. The data are obtained from networks of size $N=1000$; the number of links and $p_q$ are distributed exponentially with average $\langle q\rangle =50,60,70,80,90$. The data are averaged over 20 network realizations.

Figure 2

Laplacian spectra predicted by the effective medium approximation for graphs with power-law (a) and exponential (b) distributions of the expected degrees. The predicted spectrum for large eigenvalues $\lambda$ has a power-law behavior for scale-free networks and an exponential behavior for exponential networks.

Figure 3

Spectra of single networks with power-law (a) and exponential (b) expected degree distributions. As predicted by the effective medium approximation, the spectra of the Laplacian matrices of power-law networks has a power-law tail, while the spectra of networks with expected exponential degree distribution have exponential tail. The data in (a) were obtained from single networks of size $N={10}^4$; the data in (b) were obtained from 20 network realizations of size $N={10}^3$.

Figure 4

Comparison between the von Neumann entropy $S_{\mathrm{VN}}$, the Shannon entropy $S$, and the entropy of the expected degree distribution $S_p$. These are for networks with power-law and exponential degree distributions, as a function of the average degree and the value of the power-law exponent $\gamma$ of the scale-free expected distribution. For every value of the Shannon entropy, an average is performed over 20 network realizations with exactly the same Shannon entropy: