PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral entropies as information-theoretic tools for complex network comparison

Manlio De Domenico, Jacob Biamonte

arXiv:1609.01214v1physics.soc-phcond-mat.dis-nnquant-ph

TL;DR

Complex-network information has lacked an appropriate entropy definition. The paper introduces a quantum-inspired density matrix based on network Laplacian spectra, develops divergences and inference tools, and reports successful model fitting and network comparison, including accurate recovery of human-microbiome community associations.

  • Problem

    Quantifying information in complex networks has remained elusive, with earlier approaches often restricted to distributions of individual network descriptors.

  • Method

    The paper defines a Gibbs-inspired density matrix from the combinatorial Laplacian and develops spectral entropy, generalized divergences, model-fitting, and network-distance procedures.

  • Results

    The framework supports maximum spectral-likelihood parameter estimation, hierarchical clustering of network layers, and high-accuracy recovery of human-microbiome community-based associations.

  • Takeaways & Limitations

    Spectral information measures provide a whole-network basis for statistical inference and distance-based comparison in complex network research.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper frames complex networks as information-processing systems but notes that network entropy has lacked an appropriate general definition. It proposes a spectral, quantum-inspired framework for quantifying network information, fitting models, selecting models, and comparing multilayer structures.

  • Complex-network entropy has remained elusive, with prior applications often limited to probability distributions of individual network descriptors.
  • The framework defines network information measures inspired by quantum information, including spectral entropy, R´enyi q-entropy, and generalized divergences.
  • Kullback-Leibler minimization provides spectral maximum-likelihood inference for fitting network-model parameters and enables model selection using information criteria.
  • The Jensen-Shannon-based distance quantifies differences between complex networks and supports comparison of layers in multilayer systems.
  • Hierarchical clustering of human-microbiome network sites recovers existing community-based associations with high accuracy.

II. VON NEUMANN ENTROPY OF A COMPLEX NETWORK

The paper constructs a Gibbs-like density matrix from the graph Laplacian and uses its spectrum to define network entropy. This construction is intended to preserve entropy’s basic additivity behavior while supporting whole-network comparison and inference.

  • A density matrix is mathematically Hermitian, positive semi-definite, and trace-normalized; its eigenvalues are non-negative and sum to 1.
  • The resulting von Neumann entropy equals the Shannon entropy of the density matrix’s eigenvalues.
  • The proposed network matrix uses ρ = Z−1e−βH with H equal to the combinatorial Laplacian L = D−A and Z = Tr e−βH.
  • Using e−Lt connects the same functional form to purely diffusive dynamics when β parameterizes time.
  • The rescaled-Laplacian approach can violate sub-additivity in critical circumstances, motivating the proposed alternative.
  • The proposed spectral entropy is designed so that aggregating two networks yields entropy no greater than the sum of their separate entropies.

III. VON NEUMANN ENTROPY OF STANDARD NETWORK MODELS

The paper defines network von Neumann entropy from Laplacian spectral properties and examines its behavior across standard network models and special cases. This entropy satisfies sub-additivity, unlike the BGS entropy in the tested settings.

  • The network entropy is denoted S(G) = S(ρG), where ρG is the network’s density matrix.
  • Networks of isolated nodes: For isolated-node networks, the entropy is log2 N for every β, while BGS entropy is undefined.
  • Single-link networks: For a single-link network, the spectral entropy asymptotically approaches log2 N for any β, whereas BGS entropy equals zero.
  • Complex network models: For Erdős-Rényi, Watts-Strogatz, and K-regular networks, entropy approaches log2 N at small β and zero at high β.The models are evaluated across their link probability, rewiring probability, and neighborhood-number parameters.
  • Sub-additivity of spectral entropy: The spectral entropy never violates sub-additivity regardless of β, whereas BGS entropy often violates this requirement.The comparison is shown for Erdős-Rényi networks and similar results are reported for Watts-Strogatz and K-regular ensembles.

IV. R´ENYI ENTROPY OF COMPLEX NETWORKS

The paper generalizes network spectral entropy using the quantum Rényi entropy family. Varying q changes which Laplacian-derived eigenvalue probabilities receive emphasis, revealing differences between network models.

  • Rényi spectral entropy is expressed in terms of the eigenvalues of the network Laplacian matrix.
  • As q approaches 0, Rényi entropy approaches Hartley entropy; as q approaches 1, it approaches spectral entropy.
  • As q approaches infinity, Rényi entropy converges to min-entropy, while q = 2 recovers collision entropy.
  • For Watts-Strogatz networks approaching Erdős-Rényi behavior, Rényi entropy is considerably larger for Watts-Strogatz networks.The comparison is reported from entropy curves across q and β for the standard network models.

V. GENERALIZED QUANTUM DIVERGENCES BETWEEN TWO COMPLEX NETWORKS

The paper develops generalized quantum divergences for comparing complex networks through their spectral density matrices. It emphasizes Jensen-Shannon-type measures because general divergences are not necessarily symmetric or bounded, limiting comparison uses.

  • Information divergences quantify information about an empirical probability distribution relative to a fully specified model distribution.
  • Quantum Rényi divergence generalizes to the quantum Kullback-Leibler divergence, also called quantum relative entropy.
  • General divergences are often nonsymmetric and unbounded, making them difficult to use for certain comparisons.
  • The q-quantum Jensen-Shannon construction defines a true metric for 0 ≤ q < 2 and measures network distinguishability or similarity.
  • The framework uses q-quantum divergences to compare two networks and address fundamental comparison problems in network science.

A. Maximum Likelihood Estimation and Model Selection

The framework turns spectral divergences into likelihood-based parameter estimation and information-criterion model selection for complex networks. Synthetic tests recover generating parameters across Erdős–Rényi, Watts–Strogatz, and stochastic block-model networks.

  • Maximum-likelihood estimation: Minimizing the network Kullback-Leibler divergence yields maximum-likelihood estimates for model parameters Θ.The approach uses density matrices for empirical and model networks and connects the divergence minimization to likelihood maximization.
  • Model selection: The framework supports model selection by balancing divergence from data against model parameter count, with minimum AIC identifying the preferred candidate.BIC, FIA, and MDL are also described as extensions of information-theoretic model selection.
  • Synthetic tests: Global minima in Erdős–Rényi scans are expected around the true link probability p⋆_link = 0.05.The experiments vary p_link and evaluate average divergence across 100 realizations for each value.
  • Synthetic tests: The Watts–Strogatz scan identifies the most likely region around K⋆ = 6 and p⋆_rew = 0.2 using one realization per parameter pair.The result suggests robustness against sample size while reducing computational cost.
  • Synthetic tests: The stochastic block-model minimum occurs at 8 blocks, p_intra = 0.6, and p_inter = 0.05, matching the generating network.The study averages divergence over 100 realizations for each parameter triad.

B. Clustering layers of multilayer systems

Jensen–Shannon distances provide a basis for comparing and clustering layers or snapshots in multilayer and time-varying networks. Applied to 18 human-microbiome body-site layers, hierarchical clustering agrees with existing community-type associations and is robust across β values.

  • Layer comparison: Jensen–Shannon distances can compare multiplex layers or time-varying snapshots and support clustering or aggregation of redundant information.The approach targets multilayer systems whose nodes are replicated across networks with different relationships.
  • Human microbiome application: The human microbiome dataset contains 18 multiplex layers, each corresponding to a body site, which are compared pairwise across β values.The layers had previously been partitioned into community types using Dirichlet multinomial mixture models.
  • Human microbiome application: Hierarchical clustering of the microbiome layers is in good agreement with previously reported community-based associations.The analysis uses Jensen–Shannon distance matrices and a resulting dendrogram.
  • Robustness: The clustering result is robust to the choice of β.Figure 6 compares distance matrices for β = 0.1 and β = 10 and reports dendrogram-comparison statistics.

VI. DISCUSSION

The discussion interprets spectral entropy through network distinguishability and examines its computational limits. Isolated-node and clique networks have maximal entropy, while eigenvalue computations can challenge very large networks.

  • Interpretation: Spectral entropy is proposed as a measure of network information content, although this interpretation requires formalization from information theory.The framework is motivated by viewing complex networks as information-processing systems.
  • Interpretation: Isolated-node and fully connected networks have maximal entropy because reshuffling their adjacency entries leaves the graph unchanged.The resulting indistinguishability makes the graph-isomorphism problem trivial and maximizes uncertainty.
  • Interpretation: K-regular networks are expected to have entropy below log2 N because not every reshuffling preserves their structure.Extremely sparse and dense networks are instead expected to approach maximum entropy.
  • Computational limitation: The framework scales as O(n^γ), with 2 < γ < 2.4, making networks with hundreds of thousands of nodes challenging.Parallel dense-matrix methods may solve eigenvalue problems for matrices of order 10^5 in under five minutes on standard machines.

VII. CONCLUSIONS AND OUTLOOK

The paper proposes a spectral, quantum-inspired entropy framework for complex networks that preserves key entropy properties and supports inference, network comparison, and information-geometric analysis.

  • Previous network entropies mainly apply Shannon entropy to descriptor distributions, neglecting other network information.
  • The proposed Gibbs-inspired density matrix depends on the combinatorial Laplacian, so entropy reflects the network as a whole rather than one descriptor.
  • The entropy of an aggregate network is analytically and numerically shown to be no greater than the sum of the component entropies.
  • Spectral Renyi entropy and generalized relative entropies support maximum-likelihood model fitting by minimizing Kullback-Leibler divergence between observed networks and models.
  • The Jensen-Shannon metric quantifies spectral distances between networks and enables hierarchical clustering of multilayer network layers.
  • Human microbiome site networks recover existing community-based classifications with excellent accuracy.
  • The inference procedure identifies informative parameter regions but does not assign community labels to individual nodes.
  • The framework suggests extending information geometry to complex networks and exploring how much information is required to learn model parameters from partial connectivity.

Appendix A: Sub-additivity of the von Neumann entropy for aggregate networks

For two networks aggregated by summing their adjacency matrices, the von Neumann entropy of the aggregate is no greater than the sum of the individual entropies. The proof combines non-negativity of relative entropy with properties of the associated Laplacian and density matrices.

  • Setup and result: Aggregating networks by C = A+B produces a network GC whose entropy satisfies S(GC) ≤ S(GA) + S(GB).Here A and B are the adjacency matrices of GA and GB, while C is the adjacency matrix of their aggregate GC.
  • Density-matrix formulation: The proof represents each network with a Laplacian matrix and a corresponding density matrix.The matrices LA, LB, and LC and density matrices ρA, ρB, and ρC are associated with GA, GB, and GC.
  • Non-negativity argument: Kullback-Leibler divergences between the aggregate density matrix and each component density matrix are non-negative by Klein’s inequality.The argument uses the non-negativity of D(ρC||ρA) and D(ρC||ρB), together with positive-semidefinite matrix properties.
  • Deriving sub-additivity: Summing the non-negative terms yields an intermediate inequality that expands to the entropy sub-additivity relation.The expansion includes relative-entropy terms, trace terms involving Laplacians and density matrices, and partition-function logarithms before obtaining SA + SB ≥ SC.

Appendix B: Spectral Fisher information matrix

The appendix derives the spectral Fisher information matrix for a parametric network statistical model. It uses the quantum-information upper bound and evaluates the symmetric logarithmic derivative in the Laplacian eigenbasis.

  • Quantum-information bound: For a parametric network density matrix ρ(Θ), quantum information provides an upper bound to the expected Fisher information.The parameter set is Θ = {θ1, θ2, ..., θd}, and the bound is expressed through the symmetric logarithmic derivative.
  • Parameter derivatives: The symmetric logarithmic derivative is defined with respect to each model parameter using a symmetric product.The derivative is indexed by α = 1, 2, ..., d, and the appendix specifies the associated symmetric-product operation.
  • Spectral evaluation: Spectral decomposition diagonalizes the density matrix through Laplacian eigenvalues and eigenvectors, enabling evaluation of the derivative entries in the Laplacian eigenbasis.The diagonal matrix Λ(Θ) contains eigenvalues λi(Θ), while Q(Θ) contains the corresponding eigenvectors qi(Θ).
Loading 1609.01214v1…