Source-linked AI summary
The entropy of network ensembles
Ginestra Bianconi
TL;DR
The paper addresses how to describe and quantify organization in networks with nontrivial structural features. It develops statistical-mechanics constructions for constrained network ensembles and studies their entropy, showing that scale-free degree distributions are most likely at corresponding small structural entropy.
Problem
Statistical-mechanics models had described power-law degree distributions, but limited work had measured network organization and order through entropy.
Method
The paper constructs microcanonical, canonical, and hidden-variable network ensembles under structural constraints and analyzes their entropy, including structural entropy for uncorrelated networks with fixed degree distributions.
Results
Scale-free degree distributions are the most likely degree distributions at a given small structural entropy, whereas Poisson distributions are most likely at maximal structural entropy.
Takeaways & Limitations
Small structural entropy corresponds to greater order, and scale-free degree distributions emerge naturally in ensembles with small structural entropy.
Takeaways & Limitations
The canonical saddle-point calculation is limited to at most M = O(N) constraints and linear adjacency-matrix constraints.
Abstract
from arXiv · showhide
In this paper we generalize the concept of random networks to describe networks with non trivial features by a statistical mechanics approach. This framework is able to describe ensembles of undirected, directed as well as weighted networks. These networks might have not trivial community structure or, in the case of networks embedded in a given space, non trivial distance dependence of the link probability. These ensembles are characterized by their entropy which evaluate the cardinality of networks in the ensemble. The general framework we present in this paper is able to describe microcanonical ensemble of networks as well as canonical or hidden variables network ensemble with significant implication for the formulation of network constructing algorithms. Moreover in the paper we define and and characterize in particular the "structural entropy", i.e. the entropy of the ensembles of undirected uncorrelated simple networks with given degree sequence. We discuss the apparent paradox that scale-free degree distribution are characterized by having small structural entropy but are so widely encountered in natural, social and technological complex systems. We give the proof that while scale-free networks ensembles have small structural entropy, they also correspond to the most likely degree distribution with the corresponding value of the structural entropy.
INTRODUCTION
The paper develops a statistical-mechanics framework for network ensembles with structural constraints and entropy-based measures of organization. It links small structural entropy to scale-free degree distributions while covering microcanonical, canonical, and hidden-variable constructions.
- Scope of the framework: The framework targets undirected, directed, and weighted networks, including networks with community structure or distance-dependent link probabilities.Networks are represented through adjacency matrices, with weighted links using positive integer values and directed networks using nonsymmetric matrices.
- Motivation and framework: Entropy measures the logarithmic cardinality of a network ensemble and quantifies how restrictive added structural constraints are.Adding constraints produces successive ensembles with decreasing entropy; entropy differences measure the restrictiveness of each added characteristic.
- Motivation and framework: The framework constructs microcanonical ensembles satisfying fixed structural constraints and also describes canonical or hidden-variable network ensembles.The canonical formulation uses soft constraints, with structural constraints satisfied on average.
- Structural entropy: Scale-free degree distributions have small structural entropy, yet the paper shows they are the most likely degree distributions at a corresponding small structural entropy.This resolves the apparent tension between low ensemble entropy and the frequent occurrence of scale-free networks.
- Scope and assumptions: The canonical calculation is restricted to at most M = O(N) constraints and linear constraints on the adjacency matrix.Nonlinear structural constraints are identified as requiring perturbative developments beyond the paper’s treatment.
UNDIRECTED SIMPLE NETWORKS
The paper formulates several undirected simple-network ensembles through adjacency-matrix constraints, including fixed links, degrees, correlations, communities, and spatial dependence. It gives canonical counterparts for fixed-link ensembles and configuration-model constraints.
- Network definitions: Undirected simple networks use aij = 0, 1 with forbidden tadpoles, aii = 0.These adjacency restrictions define the simple-network setting used for the listed ensembles.
- Degree-based ensembles: The configuration model fixes the degree sequence {k1, . . . , kN}, with ki = Pj aij.This degree-sequence constraint defines the ensemble of networks with prescribed node connectivities.
- Correlations, communities, and space: Additional ensembles constrain degree correlations through knn(k), community structure through inter-feature link counts, or spatial dependence through distance-interval link counts.The spatial construction fixes node positions and counts links whose endpoint distances fall within specified intervals.
- Correlations, communities, and space: For spatial constraints, B(dℓ) sums adjacency entries selected by a characteristic function over each distance interval.The selector equals one when dij lies in the interval [dℓ, dℓ+(∆d)ℓ] and zero otherwise.
- Fixed-link ensembles: The G(N, L) ensemble fixes the number of nodes N and links L, while its entropy is the logarithm of the corresponding binomial count.Its canonical counterpart G(N, p) assigns every node pair probability p(0)ij = L/(N(N −1)/2).
The configuration ensemble
The configuration ensemble contains networks with a fixed degree sequence, and its entropy and link probabilities can be approximated using saddle-point methods in the large-network limit. Under a structural cutoff, the resulting ensemble is uncorrelated and its network count agrees with combinatorial estimates.
- Configuration ensemble: The configuration ensemble considers all networks with a given degree sequence and evaluates its partition function explicitly.The degree constraints are represented with Lagrange multipliers before applying saddle-point analysis.
- Configuration ensemble: In the large-network limit, saddle-point equations approximate the ensemble entropy and determine the Lagrange multipliers.The approximation is formulated for N ≫1.
- Canonical counterpart: The canonical counterpart assigns hidden variable ωi to each node, with link probabilities determined by these variables and average degrees distributed according to a Poisson distribution.The hidden variables fix the average degree of each node.
- Uncorrelated networks: For a structural cutoff, the link probabilities reduce to the uncorrelated form, and the corresponding entropy is called the structural entropy ΣS.The uncorrelated network count is also expressed through the structural entropy.
- Uncorrelated networks: The number of uncorrelated networks with a given degree sequence agrees with the large-N combinatorial estimate, which counts valid wirings after correcting for double links and equivalent half-edge permutations.The wiring construction initially includes double links, while the final count accounts for their exclusion and node-level half-edge permutations.
The entropy of a network ensemble with fixed
The paper extends the configuration-model calculation to ensembles constrained by degree correlations and average neighbor degree. Their entropy is obtained at the saddle point, and the resulting link probability generalizes the hidden-variable formulation to strongly correlated networks.
- Correlated ensembles: The ensemble fixes degree correlations and the average degree of neighboring nodes through constraints on the network.Lagrange multipliers ωi fix individual degrees, while Ak fix the average degree of nodes with degree k.
- Entropy calculation: The partition function yields the ensemble entropy in the thermodynamic limit through saddle-point evaluation.The corresponding multipliers satisfy saddle-point equations.
- Canonical construction: The resulting link probability extends the configuration-model hidden-variable formula to networks with strong degree-degree correlations.A canonical network can be built using node hidden variables θi, group variables Gθ, and the derived probability pij.
The entropy of network ensemble with given degree
The paper evaluates network ensembles with specified degree sequences and community structure using saddle-point methods. The canonical formulation assigns hidden variables and community interactions that determine link probabilities.
- Saddle-point evaluation: For ensembles with given degree sequence and community structure, the partition function is evaluated by saddle-point approximation when Q = O(N 1/2).This condition applies in the large-network limit.
- Saddle-point evaluation: The entropy of the community-structured ensemble is obtained from the same saddle-point procedure.The derivation follows the preceding ensemble calculation.
- Link probabilities: The link probability depends on the community structure through p(c)ij.The probability is introduced after solving the saddle-point equations.
- Canonical construction: A hidden-variable or canonical ensemble assigns each node θi and each pair of communities a symmetric interaction matrix V(q,q′), then samples links probabilistically.This construction encodes both node-level and community-level factors.
The entropy of a network ensemble with given
The framework extends entropy calculations to spatial and weighted network ensembles. Weighted ensembles can constrain total strength, node strengths, or both degree and strength sequences, with corresponding entropy, expected weights, and link probabilities.
- Spatial networks: For spatially embedded networks with structural constraints, the entropy is calculated in the large-network limit using saddle-point equations.The associated link probability is then derived from the constrained ensemble.
- Spatial networks: The spatial hidden-variable model fixes node variables θi and distance-dependent weights W(dℓ), then draws links according to the resulting probability.Distance dependence enters through W(dℓ).
- Weighted networks: Weighted networks use integer positive link weights aij ≥1, while node degree and strength characterize their topology and interaction magnitudes.The paper assumes finite networks, making the integer-weight restriction non-stringent.
- Weighted networks: Weighted ensembles can fix total strength, the strength sequence, or both degree and strength sequences, adding structural features progressively.These are the three relevant weighted cases considered in the paper.
- Weighted networks: For the weighted ensembles, the paper derives entropy, average link weight, and link probability expressions under the selected constraints.The canonical construction is parameterized by ω = −ln[1 + N(N −1)/(2S)] in the total-strength setting.
- Weighted networks: Thresholding positive weights produces an uncorrelated simple network, with Aij = Θ(aij) for every node pair.The threshold function is zero for zero weight and one for positive weight.
given strength sequence
The paper calculates entropy for undirected weighted networks with a prescribed strength sequence using a saddle-point approximation, then derives average link weights and link probabilities. Rewiring links while allowing multilinks yields an uncorrelated network structure.
- given strength sequence: The entropy of undirected networks with a given strength sequence is obtained through a saddle-point approximation.The calculation introduces saddle-point equations and Jacobian eigenvectors.
- given strength sequence: The average weight of a link between nodes i and j is derived from the resulting ensemble.
- given strength sequence: The probability of a link between nodes i and j is likewise determined by the ensemble formulation.
- given strength sequence: Rewiring links while allowing multilinks produces an uncorrelated network structure.The canonical ensemble can be constructed by assigning weights to possible links with specified probabilities.
given strength /degree sequence
For weighted networks constrained by both strength and degree sequences, the paper derives the entropy in the large-network limit and specifies the associated saddle-point conditions and link statistics.
- given strength /degree sequence: The entropy of weighted networks with given strength and degree sequences is obtained in the large-size network limit.
- given strength /degree sequence: The derivation uses Lagrangian multipliers satisfying saddle-point equations.The calculation also involves eigenvectors of the Jacobian of the relevant function.
- given strength /degree sequence: The average weight of link (i,j) is derived for the constrained weighted-network ensemble.
- given strength /degree sequence: The probability of a link between nodes i and j is determined within the same ensemble.The canonical construction assigns each possible link a weight with a specified probability.
DIRECTED NETWORKS
Directed networks have more degrees of freedom than undirected networks because their adjacency matrices are generally nonsymmetric. The paper treats ensembles constrained by link counts or directed degree sequences and derives their entropy and link probabilities.
- DIRECTED NETWORKS: Directed networks are represented by generally nonsymmetric adjacency matrices and therefore have more degrees of freedom than undirected networks.
- DIRECTED NETWORKS: The paper considers directed ensembles constrained by the total number of directed links or by the incoming and outgoing degree sequence.The latter uses both k_in and k_out constraints.
- DIRECTED NETWORKS: The entropy of directed networks with a fixed number of nodes and directed links is derived, together with the corresponding link probability.
- DIRECTED NETWORKS: For fixed directed in/out degrees, the paper derives the entropy by imposing incoming and outgoing connectivity constraints.The directed-link probability follows from the resulting ensemble.
- DIRECTED NETWORKS: The directed network becomes uncorrelated when the relevant multiplier condition holds; in that regime, its entropy has a combinatorial interpretation.The stated condition involves the maximal in-degree, maximal out-degree, average in-degree, and network size.
NATURAL DEGREE DISTRIBUTION
The paper resolves the apparent tension between the low structural entropy of scale-free networks and their prevalence by finding the most likely degree distribution at fixed structural entropy. The resulting distribution is power-law-like at low entropy and Poisson-like at maximal entropy.
- NATURAL DEGREE DISTRIBUTION: Scale-free networks have smaller structural entropy than homogeneous networks at the same average degree, creating an apparent paradox given their frequent occurrence.
- NATURAL DEGREE DISTRIBUTION: The paper seeks the most likely degree distribution for a specified structural entropy while fixing the total numbers of nodes and links.Structural entropy is defined for uncorrelated networks with a fixed degree distribution.
- NATURAL DEGREE DISTRIBUTION: A statistical-mechanics partition function, with β controlling the average structural entropy, is used to construct the degree-distribution model.The sum is restricted to degree distributions with fixed N and L, enforced through delta functions.
- NATURAL DEGREE DISTRIBUTION: For sparse networks with L = O(N), the saddle-point equations have a solution when β > 1 and average degree ⟨k⟩ > 1.
- NATURAL DEGREE DISTRIBUTION: At large β, the degree distribution is Poisson-like, whereas small structural entropy produces a fat power-law tail with exponent γ = β+1.As β approaches its minimum near 1, the tail exponent approaches γ →2.
CONCLUSIONS
The paper develops statistical-mechanical descriptions for diverse network ensembles and uses entropy to quantify their cardinality. It applies structural entropy to degree distributions, finding that scale-free distributions are most likely at low structural entropy.
- Statistical mechanics provides a natural description for a wide set of network ensembles and theoretically estimates their entropy.The entropy quantifies the cardinality of the network ensembles.
- Randomized ensembles built from real networks may be useful for inference problems in technological, social, and biological networks.
- Canonical or hidden-variables models can generate networks with community structure and spatial embedding.
- For fixed average degree, structural entropy decreases as the exponent γ of a power-law degree distribution increases.
- Scale-free degree distributions are the most likely distributions at small structural entropy, whereas Poisson distributions are most likely at maximal structural entropy.