Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison

Any physical system can be viewed from the perspective that information is implicitly represented in its state. However, the quantification of this information when it comes to complex networks has remained largely elusive. In this work, we use techniques inspired by quantum statistical mechanics to define an entropy measure for complex networks and to develop a set of information-theoretic tools, based on network spectral properties, such as Rényi $q$ entropy, generalized Kullback-Leibler and Jensen-Shannon divergences, the latter allowing us to define a natural distance measure between complex networks. First, we show that by minimizing the Kullback-Leibler divergence between an observed network and a parametric network model, inference of model parameter(s) by means of maximum-likelihood estimation can be achieved and model selection can be performed with appropriate information criteria. Second, we show that the information-theoretic metric quantifies the distance between pairs of networks and we can use it, for instance, to cluster the layers of a multilayer system. By applying this framework to networks corresponding to sites of the human microbiome, we perform hierarchical cluster analysis and recover with high accuracy existing community-based associations. Our results imply that spectral-based statistical inference in complex networks results in demonstrably superior performance as well as a conceptual backbone, filling a gap towards a network information theory.

Popular Summary

In the realm of complex networks—for example, biological and quantum systems—a satisfactory definition of network entropy has thus far been hindered. The difficulty lies in realizing a tractable probability distribution that defines an interconnected system as a whole. A candidate starting point has been classical information theory, which is built centrally on the quantification of information through entropy. Despite its widespread applications, this approach is limited to applying entropy to a known network descriptor, resulting only in an alternative means to analyze a probability distribution. Here, we introduce a probability distribution representing a complex network that satisfies the same properties as a density matrix in quantum mechanics.

We build an information-theoretic framework that allows us to quantify the information content of complex networks. We define an entropy measure based on spectral properties of observed networks and their models, rather than relying on a subset of network descriptors such as mesoscale structure or degree distribution. Crucially, we introduce a metric distance to compare the units of interconnected systems such as multilayer networks. We apply our methodology to classifying human microbiome sites, and we explore our findings using numerical experiments. We show that our technique, which is built on ideas appearing in quantum statistical mechanics, is superior to previous efforts based on classical information theory. These previous efforts took into account only a subset of the possibilities (which our formulation inherently considers) and, furthermore, were subject to inconsistencies.

By showing that spectral methods are fundamental for analyzing and understanding complex networks, our framework introduces a set of spectral tools that we expect will have many statistical applications.

Figure 1

Density matrix of a complex network. Network (top) and corresponding density matrix (bottom) from (a) a stochastic block model and (b) Watts-Strogats networks, for $\beta =3.16$. Colors in the networks indicate nodes belonging to the same community, whereas colors in the density matrices indicate the magnitude of the corresponding entry. Networks with $N=200$ nodes are shown.

Figure 2

von Neumann entropy of complex network models. Top panels: Spectral entropy as a function of $1/\beta$ for Erdös-Rényi networks (left), Watts-Strogatz’s small-world networks (center), and $K$-regular lattices (right). Color encodes realizations obtained by varying the parameter of the network model, i.e., the probability $p_{\mathrm{link}}$ of a link between two nodes, the rewiring probability $p_{\mathrm{rew}}$, and the number of neighbors $K$, respectively. In all cases, networks with $N=200$ are considered. Bottom panels: Spectral gap as a function of $1/\beta$. Note that the value of $\beta$ where it is maximum corresponds to the value where a knee is observed in the spectral entropy (see Appendix pp2 for further details).

Figure 3

Subadditivity of spectral entropy. Distribution of entropy variation (see the text) for an Erdös-Rényi network with $p_{\mathrm{link}}=0.01$ and $N=100$. The results for the quantum entropy defined in this work (left-hand panel) and the BGS entropy (right-hand panel) are shown. Quantum entropy never violates subadditivity, regardless of the $\beta$ parameter, whereas the BGS entropy significantly violates subadditivity.

Figure 4

Rényi entropy of complex network models. Entropy as a function of $q$ with $\beta =1/15.8$ for Erdös-Rényi networks (left), Watts-Strogatz’s small-world networks (center), and $K$-regular lattices (right). Color encodes realizations obtained by varying the parameter of the network model, i.e., the probability $p_{\mathrm{link}}$ of a link between two nodes, the rewiring probability $p_{\mathrm{rew}}$, and the number of neighbors $K$, respectively. In all cases, networks with $N=200$ are considered.

Figure 5

Maximum-likelihood parameter estimation based on Kullback-Leibler (KL) minimization. (a) Erdös-Rényi network model ($N=200$) for different values of the link probability $p_{\mathrm{link}}$ against an Erdös-Rényi network with $p_{\mathrm{link}}^{\star }=0.05$, assumed to be the data to fit. The vertical dashed line indicates the true value of the parameter. Each curve corresponds to a value ${\beta }^{\star }$ of $\beta$ such that $S[\mathit{\rho }({\beta }^{\star })]/{\log }_{2}N=c({\beta }^{\star })$, with $c$ a real number between 0 and 1. Global minima are expected around the true value. (b) Watts-Strogatz’s network model ($N=200$) for different values of the parameters $K$ and $p_{\mathrm{rew}}$ against a Watts-Strogatz network with $K^{\star }=6$ and $p_{\mathrm{rew}}^{\star }=0.2$, assumed to be the data to fit. The white dot indicates the true value and it falls in the iso-likelihood region with smallest Kullback-Leibler divergence (encoded by color in log scale). (c) Stochastic block model ($N=200$) for different values of the intra- and intercommunity probability parameters, $p_{\text{intra}}$ and $p_{\text{inter}}$, and number of equally sized blocks against a network obtained from the same model with 8 blocks, $p_{\text{intra}}^{\star }=0.5$ and $p_{\text{inter}}^{\star }=0.05$, assumed to be the data to fit.

Figure 6

Hierarchical clustering of human microbiome sites. The Jensen-Shannon distance matrices with (a) $\beta =0.1$ and (b) $\beta =10$ are shown, together with their (c) tantlegram, i.e., a visual analysis of their differences. Cophenetic distance and Baker’s gamma correlation coefficient, quantifying the correlation between the two dendrograms, are reported.