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 (69)

• Emergence of scaling in random networks
• Quantum entanglement
• Error and attack tolerance of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Catastrophic cascade of failures in interdependent networks
• Functional cartography of complex metabolic networks
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Area laws for the entanglement entropy - a review
• Network robustness and fragility: Percolation on random graphs
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Stochastic blockmodels and community structure in networks
• Self-similarity of complex networks
• The Role of Relative Entropy in Quantum Information Theory
• Detecting rich-club ordering in complex networks
• Mathematical Formulation of Multi-Layer Networks
• Synchronization reveals topological scales in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Communicability in complex networks
• The physics of spreading processes in multilayer networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Mapping change in large networks
• Random Walks on Multiplex Networks
• Navigability of Complex Networks
• Statistical physics of inference: Thresholds and algorithms
• Fisher Information and entanglement of non-Gaussian spin states
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Structure and inference in annotated networks
• The Physics of Communicability in Complex Networks
• Measuring multipartite entanglement via dynamic susceptibilities
• Abrupt transition in the structural formation of interconnected networks
• Entanglement Percolation in Quantum Networks
• Parsimonious module inference in large networks
• Assessing the relevance of node features for network structure
• Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states
• Hamiltonian Learning and Certification Using Quantum Resources
• Robust Online Hamiltonian Learning
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Properties of Classical and Quantum Jensen-Shannon Divergence
• Statistical-mechanical approach to subgraph centrality in complex networks
• On dynamic network entropy in cancer
• Mapping multiplex hubs in human functional brain network
• On the metric character of the quantum Jensen-Shannon divergence
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states
• Quantum complex networks
• The entropic origin of disassortativity in complex networks
• Quantum fidelity in the thermodynamic limit
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Renyi Entropy of the XY Spin Chain
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Entanglement percolation in quantum complex networks
• Evolution of robust network topologies: Emergence of central backbones
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Communicability reveals a transition to coordinated behavior in multiplex networks
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Information geometry of Gaussian channels
• Quantum Fisher Information of Entangled Coherent States in a Lossy Mach-Zehnder Interferometer
• Degree Distribution in Quantum Walks on Complex Networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Community Detection in Quantum Complex Networks
• Communicability and multipartite structures in complex networks at negative absolute temperatures
• A unified data representation theory for network visualization, ordering and coarse-graining
• Tensor Network Methods for Invariant Theory

Cited by in corpus (54)

• The Statistical Physics of Real-World Networks
• Reconstruction methods for networks: the case of economic and financial systems
• Weighted simplicial complexes and their representation power of higher-order network data and topology
• Detecting sequences of system states in temporal networks
• Statistical physics of complex information dynamics
• Towards quantum advantage via topological data analysis
• Network comparison and the within-ensemble graph distance
• Complex Quantum Networks: a Topical Review
• Information Dynamics in Evolving Networks Based on the Birth-Death Process: Random Drift and Natural Selection Perspective
• The topological Dirac equation of networks and simplicial complexes
• Quantifying genuine multipartite correlations and their pattern complexity
• Multilayer Network Science: from Cells to Societies
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Unraveling the effects of multiscale network entanglement on disintegration of empirical systems
• netrd: A library for network reconstruction and graph distances
• Enhancing transport properties in interconnected systems without altering their structure
• Information propagation in multilayer systems with higher-order interactions across timescales
• Topology and dynamics of higher-order multiplex networks
• Embedded Topological Insulators
• Diffusion geometry of multiplex and interdependent systems
• Graph Comparison via the Non-backtracking Spectrum
• Generalized network density matrices for analysis of multiscale functional diversity
• Classical Information Theory of Networks
• The mass of simple and higher-order networks
• Atomic Quantum Technologies for Quantum Matter and Fundamental Physics Applications
• Dirac gauge theory for topological spinors in 3+1 dimensional networks
• Connecting Network Science and Information Theory
• Characterization and comparison of large directed graphs through the spectra of the magnetic Laplacian
• Networks with many structural scales: a Renormalization Group perspective
• Synchronization Invariance Under Network Structural Transformations
• Thermodynamics of network model fitting with spectral entropies
• Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function
• Multi-scale Laplacian community detection in heterogeneous networks
• Quantum entropy couples matter with geometry
• Inference of Edge Correlations in Multilayer Networks
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
• Emergent information dynamics in many-body interconnected systems
• The Quantum Theil Index: Characterizing Graph Centralization using von Neumann Entropy
• Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
• Regressing bubble cluster dynamics as a disordered many-body system
• Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels
• Asymptotic entropy of the Gibbs state of complex networks
• The latent cognitive structures of social networks
• Measuring and utilizing temporal network dissimilarity
• Effective one-dimension reduction of multi-compartment complex systems dynamics
• Potential energy of complex networks: a novel perspective
• From Local Atomic Environments to Molecular Information Entropy
• Beyond holography: the entropic quantum gravity foundations of image processing
• Dilution of Ferromagnets via a Random Graph-based Strategy
• Geometric Criticality in Scale-Invariant Networks
• Asymptotic versus mesoscopic spectral dimensions in networks and inhomogeneous structures
• Statistical Properties of Links of Network: A Survey on the Shipping Lines of Worldwide Marine Transport Network
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy