Spectral entropies as information-theoretic tools for complex network comparison

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 Renyi 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 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.

13 pages, 6 figures

References in corpus (21)

• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The structure and dynamics of multilayer networks
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Communicability in complex networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Navigability of Complex Networks
• Fisher Information and entanglement of non-Gaussian spin states
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Parsimonious module inference in large networks
• Robust Online Hamiltonian Learning
• Properties of Classical and Quantum Jensen-Shannon Divergence
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Statistical-mechanical approach to subgraph centrality in complex networks
• On the metric character of the quantum Jensen-Shannon divergence
• The entropic origin of disassortativity in complex networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Evolution of robust network topologies: Emergence of central backbones
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Communicability and multipartite structures in complex networks at negative absolute temperatures

Cited by in corpus (3)

• Quantifying genuine multipartite correlations and their pattern complexity
• Graph Comparison via the Non-backtracking Spectrum
• Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function