REVIEW 3 major objections 4 minor 40 references
Classical Information Theory of Networks
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Information theory explains why networks are scale-free
desk verdict The paper's core variational derivation is internally inconsistent: Eq. (16) does not follow from Eq. (15), and the sign error undermines the main claim as presented, though the underlying framework is worth engaging. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key machinery is a lossy compression channel. The source is a classical network ensemble where each of the L links is an independent message, an ordered pair of node labels drawn with probability πij; when only expected degrees are constrained, πij = kikj/(⟨k⟩N)^2. The channel replaces each link label (i,j) with the pair of degree classes (k,k′), erasing node identity. The output ensemble has entropy H = −L∑ Π_{kk′} ln Π_{kk′} with Π_{kk′} = kk′P(k)P(k′)/⟨k⟩^2. Because the channel is deterministic given the input, H equals the mutual information between input and output; maximizing H − λS with S = S* is a channel-capacity problem whose solution is the optimal degree distribution. The same construction, with hidden variables (κ,κ′,δ), yields optimal pair correlation functions for spatial networks.
What would settle it
Take any finite network ensemble with N, L, ⟨k⟩ and a chosen S*; enumerate or sample degree distributions P(k) satisfying the normalization and mean-degree constraints. If any P(k) that is not of the form in Eq. (16) yields a strictly larger H-entropy (Eq. 13) than P*(k) under S = S*, the claimed optimality is false. An empirical check: measure S and H on a real network, compute the exponent predicted by Eq. (16), and compare with the observed degree distribution; a consistent mismatch would indicate the channel or constraints miss something.
Extended reading notes
Core claim
The central discovery is that the optimal degree distribution for a fixed classical entropy S* takes the form P*(k) = ⟨k⟩ e^(−(µ+1)) e^(−ν⟨k⟩/k) k^(−(λ+1)) (Eq. 16), which decays as a power law for large k. For spatial networks, optimizing H under S = S* yields a pair correlation function ω*(δ) = e^(−(µ+1)) e^(−ν/f(δ)) f(δ)^(−(λ+1)) (Eq. 23), so power-law linking probabilities induce power-law distance distributions; in Euclidean space this corresponds to a fractal, non-uniform node placement. The paper further shows that the entropy H of the compressed ensemble equals the mutual information of the compression channel, and validates Eq. (31) against empirical pair correlation functions of air transportation networks.
Load-bearing premise
The whole derivation assumes that a network ensemble's information content should be held fixed at some externally given value S* while maximizing the entropy of the degree-class compression, and that compressing node labels to degree classes is the right channel to use; neither the value of S* nor the choice of channel follows from the framework itself.
Editorial extensions
If this is right
- Power-law degree distributions no longer need to be imposed by hand: they arise as the unique maximizer of compressed entropy for fixed classical entropy.
- The framework supplies a principled prior for the spatial distribution of nodes in network embeddings, replacing arbitrary uniform priors.
- The exponent of the optimal power law is set by λ, the Lagrange multiplier enforcing S = S*, so networks with different information content should exhibit different exponents.
- The equality between H and the channel mutual information means the optimization is literally a channel-capacity calculation, connecting network modeling to standard information theory.
- Real air transportation networks' pair correlation functions follow the predicted form, suggesting the mechanism operates in real systems.
Reading between the lines
- The same trade-off could be applied to other compression channels—e.g., grouping nodes by community or by geometric region—in which case the optimal hidden-variable distribution would change, offering testable predictions for community sizes or spatial densities.
- If S* is not fixed by data but itself evolves, the framework suggests a two-level story where networks select their information content; the paper leaves that selection unexplained.
- Because the optimal P*(k) has an exponential cutoff at low k, the framework predicts that finite-size effects should soften scale-free behavior, which could be tested by measuring the cutoff's dependence on N and ⟨k⟩.
- The same variational structure likely extends to multilayer networks and simplicial complexes, as the authors note, where the 'hidden variables' would include layer identities or simplex sizes.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a 'classical information theory of networks' in which a network is represented by its edge list, each link drawn from a distribution over node pairs. For the ensemble with only expected-degree constraints, the authors derive an entropy S for the original ensemble and an entropy H for a compressed representation that keeps only degree classes of linked nodes. They then optimize H subject to S = S* and the usual normalization/mean-degree constraints, claiming that the optimal degree distribution is a power law k^{-(λ+1)} with an exponential cutoff. The same formalism is applied to spatially embedded networks, predicting non-uniform node distributions, and to heterogeneous spatial networks, yielding a pair-correlation function that is fitted to three air-transportation networks.
Significance. If the derivation were correct, the framework would offer a fresh information-theoretic justification for heterogeneous degree distributions and spatial non-uniformity in networks, and the channel-based reinterpretation of coarse-grained network ensembles is a genuinely useful conceptual idea. The paper also cleanly reproduces the standard uncorrelated-network result ⟨A_ij⟩ = k_i k_j/(⟨k⟩N) from its classical ensemble, which is a nice pedagogical contribution. However, the significance is substantially reduced by a load-bearing algebraic error in the central variational calculation, by the fact that the empirical comparison in Fig. 4 fits the free parameters per network rather than testing predictions, and by the external nature of the target entropy S* that sets the predicted exponent.
major comments (3)
- [Optimal degree distribution, Eqs. (15)–(16)] The variational solution quoted in Eq. (16) does not follow from the functional F in Eq. (15). Using H and S from Eqs. (13) and (9), the stationarity condition ∂F/∂P(k) = 0 gives P*(k) ∝ k^{λ-1} e^{-ν/k}. For the stated condition λ>1 this distribution increases with k and is not normalizable on k≥1, whereas Eq. (16) claims a decaying power law k^{-(λ+1)} exp(-ν⟨k⟩/k). The claimed form follows only if the λ term in Eq. (15) has the opposite sign (equivalently, if the same symbol λ is redefined as -λ). The same sign error propagates into Eqs. (23) and (31), so the central claim that power-law degree distributions and spatial correlations are optimal is not actually derived from the stated optimization problem. The derivation, the existence conditions for the Lagrange multipliers, Fig. 2, and the fitted forms in Fig. 4 must all be re-examined after this correction.
- [Real-world networks, Fig. 4] The agreement shown in Fig. 4(c) is not an independent validation of Eq. (31): the values λ = 1.2, 1.3, 0.45 and ν = 120, 5, 8 are fitted separately to the three airline networks, so the theory is used as a two-parameter curve family rather than as a predictive model. Furthermore, the reported λ = 0.45 for Ryanair contradicts the assertion after Eq. (16) that λ > 1, and once the sign error in the variational derivation is corrected, the functional form used for the fit changes. This section should be reframed as an illustrative fit, or the authors should provide a genuinely out-of-sample validation if the predictive claim is to be retained.
- [Information theory framework / Optimal degree distribution] The optimization is conditional on an externally specified target entropy S*, introduced just before Eq. (15) and formalized in Eq. (C.1). Because S* fixes the Lagrange multiplier λ and hence the exponent of the predicted power law, the framework does not by itself explain why real networks possess the particular degree heterogeneity they exhibit; it predicts a functional form with a free parameter. The paper should either derive S* from additional first principles or explicitly state that the prediction is parametric and therefore incomplete as an explanation of heterogeneity.
minor comments (4)
- [Classical network ensembles, Eq. (4)] The displayed functional for G is miswritten: the right-hand side after the first equality is missing the S term, and the minus signs before the sums over ψ_i are not displayed correctly. Please rewrite this equation carefully.
- [Introduction] There is a typo in the Introduction: 'if we we want to infer the positions of the nodes' should read 'if we want to infer...'.
- [Optimal degree distribution, after Eq. (16)] The statement that the Lagrange multipliers 'always exist as long as λ>1' is internally inconsistent with the value λ=0.45 reported for Ryanair in Fig. 4, and it must be reconciled with the corrected variational derivation.
- [Code availability] The paper states that code is available upon request; for reproducibility, the authors should deposit the code in a permanent public repository.
Circularity Check
Main variational derivation is self-contained; Fig. 4 agreement is a per-network curve fit of the two free parameters lambda and nu.
-
fitted input called prediction
[Real-world networks section, Figure 4 caption (panel c)]
"Panel (c) shows the pair correlation functions ω(κ,κ′,δ ) = ω(w), where w = κκ′f(δ), for the three networks. Points represent empirical densities, while the full lines are theoretical predictions according to Eq. (31). Values of the Lagrange multipliers are: λ = 1.2 andν = 120 for AA, λ = 1.3 and ν = 5 for LU, and λ = 0.45 and ν = 8 for RY."
Eq. (31) is a two-parameter family C exp(-ν/w) w^{-(λ+1)}. The plotted 'theoretical predictions' use per-network values of λ and ν, and the text does not report the independent constraint values (S*, mean degree, normalization) from which these Lagrange multipliers would be fixed. Since the same empirical ω(w) curves are shown as the points being compared, the listed parameters are free constants selected to match those points. The agreement in panel (c) is therefore a curve fit rather than an out-of-sample prediction; the statement that the data are 'well described by Eq. (31)' is an evaluation of that fit, not an independent test of the theory.
full rationale
The core optimization is not circular: H and S are independently defined functions of the degree distribution P(k), and maximizing H - λS subject to normalization and mean-degree constraints is a standard constrained entropy maximization. The power-law family in Eq. (16) is the Euler-Lagrange form of that optimization (although the sign convention in Eq. (15) does not appear to reproduce Eq. (16) as written; that is a mathematical consistency defect, not a circularity). The one place where a 'prediction' reduces to a fit is the real-world validation in Fig. 4, where λ and ν are listed per network and no independent constraint calculation is shown, so the match is in-sample. This affects the empirical claim but not the central variational derivation, so the overall circularity score is moderate rather than high. Self-citations (e.g., Ref. [34] for the hyperbolic approximation) are not load-bearing for the main derivation.
Assumptions & free parameters
free parameters (3)
- S* (target classical entropy) =
arbitrary input; varied in Fig 2; determines λ via Eq. (16)
- λ (Lagrange multiplier for S) =
1.2 (AA), 1.3 (LU), 0.45 (RY) in Fig 4
- ν (Lagrange multiplier for normalization of P) =
120 (AA), 5 (LU), 8 (RY) in Fig 4
assumptions (4)
- domain assumption The compression of links to degree classes is an appropriate lossy channel.
- ad hoc to paper The target entropy S* is a freely adjustable constraint.
- domain assumption The ensemble permits multiedges and tadpoles, making edges independent.
- standard math Lagrange multipliers exist for λ > 1.
Cite this review
Pith. "Pith review of Classical Information Theory of Networks." pith.science (2026). https://pith.science/paper/WT47T5QW
@misc{pith2026190803811,
author = {Pith},
title = {Pith review of: Classical Information Theory of Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/WT47T5QW}},
note = {Machine review of arXiv:1908.03811}
}
read the original abstract
Existing information-theoretic frameworks based on maximum entropy network ensembles are not able to explain the emergence of heterogeneity in complex networks. Here, we fill this gap of knowledge by developing a classical framework for networks based on finding an optimal trade-off between the information content of a compressed representation of the ensemble and the information content of the actual network ensemble. In this way not only we introduce a novel classical network ensemble satisfying a set of soft constraints but we are also able to calculate the optimal distribution of the constraints. We show that for the classical network ensemble in which the only constraints are the expected degrees a power-law degree distribution is optimal. Also, we study spatially embedded networks finding that the interactions between nodes naturally lead to non-uniform spread of nodes in the space, with pairs of nodes at a given distance not necessarily obeying a power-law distribution. The pertinent features of real-world air transportation networks are well described by the proposed framework.
Figures
Reference graph
Works this paper leans on
-
[1]
Information theory and statistical mechanics
Edwin T Jaynes. Information theory and statistical mechanics. Physical Review, 106(4):620, 1957
1957
-
[2]
Principles of maximum entropy and maximum caliber in statistical physics
Steve Press´ e, Kingshuk Ghosh, Julian Lee, and Ken A Dill. Principles of maximum entropy and maximum caliber in statistical physics. Reviews of Modern Physics , 85(3):1115, 2013
work page 2013
-
[3]
A simple introduction to maximum entropy models for natural language processing
Adwait Ratnaparkhi. A simple introduction to maximum entropy models for natural language processing. IRCS Technical Reports Series, page 81, 1997
work page 1997
-
[4]
A.G. Wilson. A statistical theory of spatial distribution models. Transportation Research, 1(3):253 – 269, 1967
work page 1967
-
[5]
Ravi Kanbur and Xiaobo Zhang. Fifty years of regional inequality in china: a journey through central planning, reform, and openness. Review of development Economics , 9(1):87–106, 2005
work page 2005
-
[6]
Detecting direct associations in a network by information theoretic approaches
Jifan Shi, Juan Zhao, Tiejun Li, and Luonan Chen. Detecting direct associations in a network by information theoretic approaches. Science China Mathematics , 62(5):823–838, 2019
work page 2019
-
[7]
A maximum entropy model applied to spatial and temporal correlations from cortical networks in vitro
Aonan Tang, David Jackson, Jon Hobbs, Wei Chen, Jodi L Smith, Hema Patel, Anita Prieto, Dumitru Petrusca, Matthew I Grivich, Alexander Sher, et al. A maximum entropy model applied to spatial and temporal correlations from cortical networks in vitro. Journal of Neuroscience , 28(2):505–518, 2008
work page 2008
-
[8]
The information bottleneck method
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057 , 2000
arXiv 2000
Show all 40 references
-
[9]
Resolution and relevance trade-offs in deep learning
Juyong Song, Matteo Marsili, and Junghyo Jo. Resolution and relevance trade-offs in deep learning. Journal of Statistical Mechanics: Theory and Experiment , 2018(12):123406, 2018
2018
-
[10]
The stochastic thermodynamics of computation
David H Wolpert. The stochastic thermodynamics of computation. Journal of Physics A: Mathematical and Theoretical, 52(19):193001, 2019
2019
-
[11]
The statistical physics of real-world networks
Giulio Cimini, Tiziano Squartini, Fabio Saracco, Diego Garlaschelli, Andrea Gabrielli, and Guido Caldarelli. The statistical physics of real-world networks. Nature Reviews Physics , 1(1):58, 2019
2019
-
[12]
Statistical mechanics of networks
Juyong Park and Mark EJ Newman. Statistical mechanics of networks. Physical Review E , 70(6):066117, 2004
2004
-
[13]
Entropy of network ensembles
Ginestra Bianconi. Entropy of network ensembles. Physical Review E, 79(3):036114, 2009
2009
-
[14]
Entropy measures for networks: Toward an information theory of complex topologies
Kartik Anand and Ginestra Bianconi. Entropy measures for networks: Toward an information theory of complex topologies. Physical Review E, 80(4):045102, 2009
2009
-
[15]
Gibbs entropy of network ensembles by cavity methods
Kartik Anand and Ginestra Bianconi. Gibbs entropy of network ensembles by cavity methods. Physical Review E, 82(1):011116, 2010
2010
-
[16]
A statistical mechanics approach for scale-free networks and finite-scale networks
Ginestra Bianconi. A statistical mechanics approach for scale-free networks and finite-scale networks. Chaos: An Interdisciplinary Journal of Nonlinear Science , 17(2):026114, 2007
2007
-
[17]
Entropy of stochastic blockmodel ensembles
Tiago P Peixoto. Entropy of stochastic blockmodel ensembles. Physical Review E, 85(5):056122, 2012
2012
-
[18]
Reducing degeneracy in maximum entropy models of networks
Szabolcs Horv´ at,´Eva Czabarka, and Zolt´ an Toroczkai. Reducing degeneracy in maximum entropy models of networks. Physical review letters, 114(15):158701, 2015. Classical information theory of networks 16
2015
-
[19]
Statistical mechanics of multiedge networks
Oleguer Sagarra, CJ P´ erez Vicente, and Albert D¨ ıaz-Guilera. Statistical mechanics of multiedge networks. Physical Review E, 88(6):062806, 2013
2013
-
[20]
An exponential family of probability distributions for directed graphs
Paul W Holland and Samuel Leinhardt. An exponential family of probability distributions for directed graphs. Journal of the american Statistical association , 76(373):33–50, 1981
1981
-
[21]
Emergence of scaling in random networks
Albert-L´ aszl´ o Barab´ asi and R´ eka Albert. Emergence of scaling in random networks. science, 286(5439):509–512, 1999
1999
-
[22]
Scale-free networks well done
Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, and Dmitri Krioukov. Scale-free networks well done. Physical Review Research, 1(3):033034, 2019
2019
-
[23]
The architecture of complex weighted networks
Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. The architecture of complex weighted networks. Proceedings of the national academy of sciences , 101(11):3747–3752, 2004
2004
-
[24]
Defining and identifying communities in networks
Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proceedings of the national academy of sciences, 101(9):2658–2663, 2004
2004
-
[25]
Benchmark graphs for testing community detection algorithms
Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110, 2008
2008
-
[26]
Information theory, inference and learning algorithms
David JC MacKay. Information theory, inference and learning algorithms . Cambridge University Press, 2003
2003
-
[27]
On random graphs i.Publ
P Erd˝ os and A R´ enyi. On random graphs i.Publ. Math. Debrecen, 6:290–297, 1959
1959
-
[28]
Number 73
B´ ela Bollob´ as and Bollob´ as B´ ela.Random graphs. Number 73. Cambridge university press, 2001
2001
-
[29]
Breaking of ensemble equivalence in networks
Tiziano Squartini, Joey de Mol, Frank den Hollander, and Diego Garlaschelli. Breaking of ensemble equivalence in networks. Physical review letters, 115(26):268701, 2015
2015
-
[30]
A critical point for random graphs with a given degree sequence
Michael Molloy and Bruce Reed. A critical point for random graphs with a given degree sequence. Random structures & algorithms , 6(2-3):161–180, 1995
1995
-
[31]
Generalized bose-fermi statistics and structural correlations in weighted networks
Diego Garlaschelli and Maria I Loffredo. Generalized bose-fermi statistics and structural correlations in weighted networks. Physical review letters, 102(3):038701, 2009
2009
-
[32]
Finding and evaluating community structure in networks
Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004
2004
-
[33]
A few useful things to know about machine learning
Pedro M Domingos. A few useful things to know about machine learning. Commun. acm , 55(10):78–87, 2012
2012
-
[34]
Hyperbolic geometry of complex networks
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Mari´ an Bogun´ a. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010
2010
-
[35]
Bureau of transportation statistics
-
[36]
Emergence of network features from multiplexity
Alessio Cardillo, Jes´ us G´ omez-Gardenes, Massimiliano Zanin, Miguel Romance, David Papo, Francisco Del Pozo, and Stefano Boccaletti. Emergence of network features from multiplexity. Scientific reports, 3:1344, 2013
2013
-
[37]
Statistical mechanics of multiplex networks: Entropy and overlap
Ginestra Bianconi. Statistical mechanics of multiplex networks: Entropy and overlap. Physical Review E, 87(6):062806, 2013
2013
-
[38]
Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
Owen T Courtney and Ginestra Bianconi. Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes. Physical Review E , 93(6):062311, 2016
2016
-
[39]
Spectral entropies as information-theoretic tools for complex network comparison
Manlio De Domenico and Jacob Biamonte. Spectral entropies as information-theoretic tools for complex network comparison. Physical Review X, 6(4):041062, 2016
2016
-
[40]
Statistical Mechanics
K Huang. Statistical Mechanics. 1963. Appendix A. The classical network ensemble We consider a classical network ensemble defining the probability of a network G = (V,E ) of|V| =N nodes and|E| =L links. In this ensemble, a network G is described by an edge list { ⃗𝓁[n] } with n...
1963
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.