Source-linked AI summary
Entropy measures for complex networks: Toward an information theory of complex topologies
Kartik Anand, Ginestra Bianconi
TL;DR
Complex-network research lacks a way to quantify network complexity and its information content. This paper defines Shannon entropy for network ensembles, relates it to Gibbs and von Neumann entropies, and finds equality in some cases but O(1) differences under extensive constraints.
Problem
Complex networks lack a means to quantify their complexity and require an information theory to support inference problems.
Method
The paper defines Shannon entropy for canonical network ensembles, studies maximum-Shannon-entropy and canonical–microcanonical relations, and examines connections with von Neumann entropy.
Results
Gibbs entropy per node equals Shannon entropy per node for random graphs in the thermodynamic limit, but differs by O(1) under extensive constraints; for scale-free networks, von Neumann and Shannon entropies are linearly related.
Takeaways & Limitations
The entropies S, S_VN, and Σ may support quantifying network complexity and addressing inference problems in networks.
Takeaways & Limitations
The regular-versus-Poisson entropy relation uses the Stirling approximation, which is valid for large c.
Abstract
from arXiv · showhide
The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this paper we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models of networks through maximum-entropy arguments and will contribute to inference problems emerging in the field of complex networks.