Abstract
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 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.
- Received 25 August 2016
DOI:https://doi.org/10.1103/PhysRevX.6.041062
Published by the American Physical Society under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
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.