Source-linked AI summary
The entropy of randomized network ensembles
Ginestra Bianconi
TL;DR
The paper asks how much information structural features retain in randomized network null models. It constructs ensembles with progressively fixed constraints and measures their entropy across real directed and undirected networks. The analysis finds lower entropy for low-exponent scale-free ensembles than for homogeneous-degree ensembles, while structural constraints generally reduce the space of possible networks.
Problem
The paper addresses how much information is retained by degree distributions, degree correlations, and community structure when real networks are represented by randomized ensembles.
Method
The authors construct successive randomized ensembles that fix network size and links, degree sequence, degree correlations, community structure, or combinations of these features, then calculate their entropies.
Results
Low-exponent scale-free network ensembles have lower entropy than ensembles with homogeneous degree distributions, and fixing structural features reduces the space of possible networks.
Takeaways & Limitations
Entropy can indicate the role of degree sequence, degree correlations, and community structure in constraining a given real network.
Takeaways & Limitations
The sparse-network approximation assumes a structural cutoff, with node degrees constrained by k_i < ⟨k⟩N.
Abstract
from arXiv · showhide
Randomized network ensembles are the null models of real networks and are extensivelly used to compare a real system to a null hypothesis. In this paper we study network ensembles with the same degree distribution, the same degree-correlations or the same community structure of any given real network. We characterize these randomized network ensembles by their entropy, i.e. the normalized logarithm of the total number of networks which are part of these ensembles. We estimate the entropy of randomized ensembles starting from a large set of real directed and undirected networks. We propose entropy as an indicator to assess the role of each structural feature in a given real network.We observe that the ensembles with fixed scale-free degree distribution have smaller entropy than the ensembles with homogeneous degree distribution indicating a higher level of order in scale-free networks.
Introduction. –
The paper treats real networks as members of ensembles of functionally equivalent networks and uses entropy to quantify how structural constraints reduce their variability. It progressively fixes degree sequence, degree correlations, and community structure to assess the information retained by each feature.
- Motivation: Real networks may belong to ensembles of networks that perform the same task equally well despite evolutionary variability.The paper motivates this view with biological networks sharing functions across species.
- Motivation: Entropy is proportional to the logarithm of the number of networks in an ensemble and measures its variability under structural constraints.The authors use successive approximations because the minimal functionally equivalent ensemble is difficult to characterize.
- Approach: The analysis constructs randomized ensembles that preserve a real network’s degree sequence, degree correlations, or community structure.These features are treated as increasingly specific constraints on the possible networks.
- Approach: The first reference ensemble fixes only the number of nodes N and links L, corresponding to the G(N, L) random-graph ensemble.Subsequent models progressively restrict the space of possible networks.
- Approach: Degree-sequence ensembles are framed as hidden-variable models, while jointly constrained ensembles generalize this framework to degree correlations or community structure.The hidden variables for the degree-sequence ensemble correspond to node-connectivity Lagrange multipliers.
Undirected networks. –
For undirected networks, the paper defines successive randomized ensembles by preserving progressively richer structural information. Their partition functions and network counts provide the basis for calculating entropy at each approximation level.
- Ensemble construction: The zero-order undirected ensemble fixes the number of nodes N and links L, with link probability p_ij = L/(N(N −1)/2).It is the G(N, L) ensemble for distinguishable nodes.
- Ensemble construction: The first-order configuration model fixes the degree sequence {k_1, . . . , k_N}, where each degree k_i is obtained from the adjacency matrix.This constraint reduces the set of possible networks relative to G(N, L).
- Ensemble construction: The second-order ensemble additionally fixes the average nearest-neighbour connectivity k_nn(k), preserving degree-dependent connectivity patterns.This captures degree-degree correlations beyond the degree sequence alone.
- Ensemble construction: Community-structure ensembles fix the number of links within and between communities, represented by A(q, q′).The community assignment of each node is represented by q_i.
- Entropy calculation: Partition functions determine the number of undirected simple networks in each constrained ensemble, while entropy per node is defined for ensemble κ.These quantities provide the counting framework for comparing successive approximations.
The volume of the network ensemble with given degree sequence.
The paper estimates the volume of network ensembles with a fixed degree sequence using statistical-mechanical partition functions and saddle-point approximations. These constraints substantially restrict the ensemble, with low-exponent scale-free networks attaining especially low entropy.
- Fixed degree sequence: The first approximation fixes a network’s degree sequence and defines the corresponding partition function for undirected simple networks.This retains more structure than the unrestricted G(N, L) ensemble.
- Fixed degree sequence: The partition function is evaluated by expressing degree constraints with Lagrange multipliers and solving the resulting integral through saddle-point equations.The multipliers satisfy equations enforcing the prescribed node degrees.
- Fixed degree sequence: In the resulting ensemble, link probabilities are determined by node-specific hidden variables and recover the hidden-variable formulation.The model retains natural correlations associated with the degree sequence and the restriction to simple networks.
- Entropy of scale-free ensembles: Scale-free networks with γ →2 minimize entropy within sparse uncorrelated networks, indicating greater ordering than random homogeneous networks.The entropy measures the logarithm of the number of networks in the ensemble, so lower entropy corresponds to fewer admissible networks.
- Entropy of scale-free ensembles: The configuration-model entropy decreases as the power-law exponent γ decreases, reaching its minimum at γ →2 for networks with natural correlations.The figure considers N = 10^4 nodes and fixed average connectivities ⟨k⟩ = 6, 8, 10.
The volume of a network ensemble with fixed degree correlations.
The second approximation fixes degree correlations in addition to the degree sequence. Solving the associated constrained ensemble allows construction of networks with the same degree statistics and nearest-neighbor degree averages, while further reducing entropy in empirical networks.
- Fixed degree correlations: The second approximation incorporates degree correlations beyond the natural correlations already present in the configuration model.The ensemble is defined through a partition function with constraints on the degree sequence and correlations.
- Fixed degree correlations: Solving the constraint equations for a real network’s degree sequence and nearest-neighbor average degree permits construction of other networks in the same ensemble.Links are then drawn with probabilities determined by the solved parameters.
- Fixed degree correlations: The entropy of the degree-correlation-constrained ensemble is approximated in the large-network limit from the corresponding partition function.The approximation follows the same general evaluation strategy used for the degree-sequence ensemble.
- Empirical networks: For Internet and protein-interaction networks, fixing the degree distribution strongly reduces randomized-ensemble entropy, while explicit degree correlations fine-tune it further.The comparison covers the Internet at the Autonomous System Level and protein-interaction networks from S. cerevisiae and H. sapiens.
The volume of network ensemble with given community structure.
The paper defines randomized ensembles that preserve both a network’s degree sequence and the numbers of links between communities, then calculates their entropy. For Zachary’s club, the entropy quantifies information in the known community partition.
- Community-structure ensembles: The ensemble fixes each node’s degree sequence and the number of links between every pair of communities.The community assignment has Q finite communities, and A(q,q′) specifies links between communities q and q′.
- Community-structure ensembles: The entropy of this community-and-degree-constrained ensemble is obtained using the same calculation steps as the preceding ensemble.
- Community-structure ensembles: The entropy expression is evaluated with Lagrangian multipliers satisfying saddle-point equations.
- Community-structure ensembles: The model assigns a link probability between nodes according to the community and degree constraints.
- Community-structure ensembles: For Zachary’s club, the calculated entropy is Σundir_c = 3.25, quantifying information in the known community partition.
Directed networks. –
Directed networks have more degrees of freedom than undirected networks because their adjacency matrices are generally non-symmetric. Their ensemble count is therefore treated separately from the symmetric undirected case.
- Directed networks: A directed network’s adjacency matrix is generally non-symmetric, unlike the symmetric matrix of an undirected network.
- Directed networks: Directed networks have more degrees of freedom than undirected networks because their adjacency matrices are not constrained by symmetry.
- Directed networks: The number of directed networks with a fixed number of nodes and directed links is calculated separately.
Volume of randomized directed network ensembles with given degree sequence.
For directed networks with a given degree sequence, the paper constrains incoming and outgoing connectivities and derives the ensemble entropy and link probabilities. It also identifies a condition for uncorrelated directed networks.
- Directed degree-sequence ensembles: The directed configuration ensemble imposes constraints on each node’s incoming and outgoing connectivities.
- Directed degree-sequence ensembles: The entropy of the directed degree-sequence ensemble is derived using the same approach as for undirected networks.
- Directed degree-sequence ensembles: The directed-link probability from node i to node j is obtained from the constrained ensemble.
- Directed degree-sequence ensembles: When ω_i + ˆω_j < 0 for all node pairs, the directed network becomes uncorrelated.
- Directed degree-sequence ensembles: Uncorrelated directed networks require K(in)K(out)/(⟨k_in⟩N) < 1.
- Directed degree-sequence ensembles: The entropy of the directed uncorrelated network follows from satisfying this maximal-degree condition.
- Directed degree-sequence ensembles: Different degree distributions reduce randomized directed-network entropy by different amounts, with some distributions carrying more information than others.
Conclusions. –
The paper studies how degree sequences, degree correlations, and community structure constrain the space of possible networks. It finds lower entropy for scale-free ensembles with low power-law exponent than for homogeneous-degree ensembles.
- Conclusions: The study evaluates randomized network models to characterize the space of possible complex networks.
- Conclusions: Scale-free ensembles with low power-law exponent γ have lower entropy than random networks with homogeneous degree distributions.
- Conclusions: Successive random approximations reveal how degree sequence, degree correlations, and community structure constrain a real graph’s ensemble.
- Conclusions: Entropy estimates across real directed and undirected networks show how each structural feature reduces the space of possible networks.
- Conclusions: The paper acknowledges support from the IST STREP GEN-NETEC contract 034952 and discussions with D. Garlaschelli and M. Marsili.