Source-linked AI summary
Enhanced reconstruction of weighted networks from strengths and degrees
Rossana Mastrandrea, Tiziano Squartini, Giorgio Fagiolo, Diego Garlaschelli
TL;DR
Reconstructing weighted networks from local information is difficult because strengths alone can be less informative than degrees. The paper introduces an analytical, unbiased maximum-entropy method using both, and finds improved reconstruction with degree information that is not redundant with strengths.
Problem
Strength-only reconstruction can perform poorly because weighted strengths may be less informative than degrees about network structure.
Source: §I · p. 2, §II · p. 3Method
An analytical, unbiased maximum-entropy method reconstructs weighted-network ensembles from the joint strengths and degrees without explicit sampling.
Source: §I · p. 2Results
The ECM accurately reconstructs real-network properties and outperforms the WCM; information-theoretic criteria find degree constraints nonredundant and not overfitting.
Source: §VIII · p. 10Takeaways & Limitations
Joint strengths and degrees can account for properties otherwise attributed to non-local mechanisms, with implications for identifying motifs and communities.
Source: §I · p. 2
Abstract
from arXiv · showhide
Network topology plays a key role in many phenomena, from the spreading of diseases to that of financial crises. Whenever the whole structure of a network is unknown, one must resort to reconstruction methods that identify the least biased ensemble of networks consistent with the partial information available. A challenging case, frequently encountered due to privacy issues in the analysis of interbank flows and Big Data, is when there is only local (node-specific) aggregate information available. For binary networks, the relevant ensemble is one where the degree (number of links) of each node is constrained to its observed value. However, for weighted networks the problem is much more complicated. While the naive approach prescribes to constrain the strengths (total link weights) of all nodes, recent counter-intuitive results suggest that in weighted networks the degrees are often more informative than the strengths. This implies that the reconstruction of weighted networks would be significantly enhanced by the specification of both strengths and degrees, a computationally hard and bias-prone procedure. Here we solve this problem by introducing an analytical and unbiased maximum-entropy method that works in the shortest possible time and does not require the explicit generation of reconstructed samples. We consider several real-world examples and show that, while the strengths alone give poor results, the additional knowledge of the degrees yields accurately reconstructed networks. Information-theoretic criteria rigorously confirm that the degree sequence, as soon as it is non-trivial, is irreducible to the strength sequence. Our results have strong implications for the analysis of motifs and communities and whenever the reconstructed ensemble is required as a null model to detect higher-order patterns.
I. INTRODUCTION
The paper introduces an analytical, unbiased maximum-entropy method that reconstructs weighted networks from local strengths and degrees. Across several networks, this joint information improves reconstruction and is not reducible to strengths alone.
I. INTRODUCTION
- Privacy-sensitive settings such as interbank lending and Big Data often provide aggregate local information rather than individual links and weights.Source: §I · p. 1
- Local information specifies O(N) quantities, while the network has O(N^2) entries to reconstruct, making the problem challenging.Source: §I · pp. 1–2
- Reconstructed networks also serve as null models for testing higher-order patterns, including assortativity, motifs, and communities.These models help filter out intrinsic node heterogeneity.Source: §I · p. 2
- The proposed analytical maximum-entropy method reconstructs unbiased weighted-network ensembles from both strengths and degrees without explicitly sampling reconstructed graphs.The method directly provides expected values of desired reconstructed properties.Source: §I · p. 2
- Strengths alone can reconstruct weighted networks poorly, even when their binary projections are well reproduced using degrees.Source: §I · p. 2
- Across several networks, joint strengths and degrees significantly improve reconstruction while remaining local, and information-theoretic criteria confirm that degrees are not reducible to strengths.The number of known variables remains O(N).Source: §I · p. 2
II. NA¨IVE RECONSTRUCTION OF WEIGHTED NETWORKS
The Weighted Configuration Model (WCM) reconstructs networks from node strengths, but strength-only constraints can poorly recover both weighted properties and binary topology. The section argues that this weakness persists even when the WCM is correctly implemented.
II. NA¨IVE RECONSTRUCTION OF WEIGHTED NETWORKS
- Equation (1) is not the unbiased expected-weight expression, and without a probability distribution it cannot yield expectations for nonlinear weight-based properties.A maximum-entropy approach had supplied the correct weight probability and expressions for functions of expected weights.Source: §II · pp. 2–3
- The WCM can predict degrees near N −1, redistributing node strengths across too many edges and producing overly dense networks.This helps explain why several reconstructed node properties are nearly constant.Source: §II · p. 3
- WCM-reconstructed node properties often lie along nearly constant lines, largely unrelated to their real values, across the networks examined.The section illustrates this for weighted and binary properties; an effective reconstruction would place points near the identity line.Source: §II · p. 3, Figure 1 · p. 4
- The section’s interpretation of the strength-only failure is reversed by an enhanced reconstruction method.The enhanced method is introduced later in the paper.Source: §II · p. 4
III. THE IRREDUCIBILITY CONJECTURE
The section conjectures that degrees carry structural information not captured by strengths alone. Across the networks studied, degree-based reconstruction reproduces binary properties better than the WCM, while strength-only predictions of degrees can imply overly dense networks.
III. THE IRREDUCIBILITY CONJECTURE
- The degree-based Configuration Model reconstructs binary nearest-neighbor degree and clustering better than the strength-based WCM across the studied networks.The comparison extends earlier findings for the World Trade Web to a broader set of real-world networks.Source: §III · p. 5, Figure 2 · p. 5
- Here, strengths and degrees are irreducible when specifying both constrains network structure differently from specifying either alone, even if their observed values are correlated.The claim concerns their distinct structural roles, not whether one sequence’s numerical values can be inferred from the other.Source: §III · p. 5
- WCM-predicted degrees often lie near constant values close to N −1, indicating that strengths are redistributed across too many edges and yield overly dense networks.In almost complete networks, the nearest-neighbor degree, clustering coefficient, and nearest-neighbor strength are necessarily nearly constant.Source: §III · p. 5, Figure 3 · p. 6
- The authors propose jointly specifying strengths and degrees, and use information-theoretic criteria to test whether degrees add non-redundant constraints.They state that these criteria confirm the irreducibility conjecture.Source: §III · p. 6
IV. WEIGHTED NETWORKS WITH GIVEN STRENGTHS AND DEGREES: THE ENHANCED CONFIGURATION MODEL
The Enhanced Configuration Model (ECM) uses a maximum-entropy ensemble constrained by each node’s expected degree and strength. Maximum-likelihood fitting determines parameters from the observed local sequences, without requiring reconstructed samples.
IV. WEIGHTED NETWORKS WITH GIVEN STRENGTHS AND DEGREES: THE ENHANCED CONFIGURATION MODEL
- The paper calls the ensemble with given strengths and degrees the Enhanced Configuration Model (ECM).The authors develop an analytical, unbiased, and fast maximum-entropy formalism for undirected networks; they describe extension to directed networks as straightforward.Source: §IV · p. 6
- The ECM maximizes Shannon entropy while constraining the expected degree and strength sequences, leaving the ensemble maximally random otherwise.The model considers undirected networks with non-negative integer edge weights.Source: §IV · p. 6
- Its mixed Bose-Fermi distribution assigns a higher cost to establishing a unit-weight link than reinforcing an existing link when x_i x_j > 1.This difference follows from imposing both binary and weighted constraints.Source: §IV · p. 7
- Maximum-likelihood parameters are obtained by solving 2N coupled equations so expected degrees and strengths match their observed sequences.The fitted parameter vectors can be found using only observed strengths and degrees, without the full network or sampling reconstructed graphs.Source: §IV · p. 7
V. RECONSTRUCTED PROPERTIES
After fitting the ECM parameters, the paper reconstructs network properties analytically from expectations of edge-weight powers. This avoids measuring those properties on sampled networks.
V. RECONSTRUCTED PROPERTIES
- Reconstructed properties are ensemble averages computed from the fitted ECM probability distribution rather than from sampled networks.For many properties, this reduces calculation to expected products of powers of distinct matrix entries.Source: §V · p. 7
- Replacing each edge-weight power with its expectation yields reconstructed values in the same time as calculating the corresponding real property.The expectation for γ = 1 gives mean edge weight, while γ = 0 gives connection probability.Source: §V · p. 7
VI. ENHANCED RECONSTRUCTION OF REAL WEIGHTED NETWORKS
Across the real-world networks considered, the enhanced method improves reconstruction of node-level assortativity and clustering properties over the standard approach. The authors report that local augmented properties explain these patterns well in those networks.
VI. ENHANCED RECONSTRUCTION OF REAL WEIGHTED NETWORKS
- Most reconstructed node-property values lie near the identity line, improving on the standard approach across the networks considered.The figure compares reconstructed and real values for four properties across 12 social, food-web, interbank, and trade networks.Source: §VI · p. 7, Figure 4 · p. 8
- Binary clustering remains the noisiest property, yet its improvement over the naive approach is described as perhaps the most significant.Source: §VI · pp. 7–8
- For the networks considered, reconstruction from purely local properties is possible to a highly satisfactory level.Source: §VI · p. 7
- Assortativity and clustering are well explained by local augmented properties, so non-local mechanisms are not needed to explain them in these networks.The authors suggest ECM may yield substantially different community-detection results from the WCM when used in modularity.Source: §VI · p. 8
VII. INFORMATION-THEORETIC TESTS OF IRREDUCIBILITY
The section compares the WCM and ECM using information-theoretic criteria that account for the ECM’s additional parameters. These tests generally favor the ECM, while identifying nearly fully connected networks as an exception where degree constraints are redundant.
VII. INFORMATION-THEORETIC TESTS OF IRREDUCIBILITY
- The comparison tests whether adding degree parameters improves fit without overfitting, since the ECM contains the WCM as a special case with those parameters switched off.Source: §VII · p. 9
- AIC weights quantify evidence in favor of each model, while AIC penalizes maximized likelihood according to the number of free parameters.Source: §VII · p. 9
- Except for two social networks, AIC weights favor the ECM, reaching unit probability within machine precision in the reported comparisons.Table I reports the AIC weights; AICc and BIC weights give the same results.Source: §VII · p. 9, Table I · p. 9
- For almost fully connected networks, degree constraints are redundant and the WCM is preferable; for nontrivial topology, degrees add non-redundant information.The section attributes the exceptions to their degree sequence being close to the WCM’s almost fully connected prediction.Source: §VII · p. 9
- AICc and BIC weights match AIC weights within machine precision, and the likelihood-ratio test gives the same response at both 5% and 1% significance levels.Source: §VII · p. 9
VIII. CONCLUSIONS
The conclusions report that strength-only reconstruction performs poorly on the analyzed networks, whereas the ECM accurately reproduces their properties. Information-theoretic criteria support using both strengths and degrees as non-redundant local constraints for most real networks.
VIII. CONCLUSIONS
- The paper introduces a fast, unbiased method that reconstructs weighted networks from the joint strengths and degrees.Source: §VIII · p. 9
- The WCM agrees extremely poorly with real network properties, while the ECM accurately reconstructs them and outperforms the strength-only approach in the analyzed networks.The interbank network considered in the paper is described as accurately reconstructed by the ECM and uninformatively reconstructed by the standard method.Source: §VIII · p. 10
- Information-theoretic criteria indicate that adding degrees is non-redundant and does not overfit, making strengths and degrees an irreducible local-information set for most real networks.Source: §VIII · p. 10