Source-linked AI summary
Extracting the multiscale backbone of complex weighted networks
M. Angeles Serrano, Marian Boguna, Alessandro Vespignani
TL;DR
Weighted networks often lack a characteristic scale, making global thresholds liable to discard relevant small-scale structure. The paper introduces disparity filtering, which tests local weight heterogeneity against a null model and retains statistically significant edges across scales. In real networks, it greatly reduces edges while preserving most weight, many nodes, and key structural properties, although its scope is strongest for networks with strong disorder.
Problem
Broad, heavy-tailed weight distributions and local correlations make arbitrary global cutoffs unsuitable for extracting relevant network backbones.
Method
The disparity filter tests normalized incident weights against a node-level random-assignment null model and retains an edge when it is significant for at least one endpoint.
Results
The filter substantially reduces edges while preserving almost all weight, a large fraction of nodes, the degree-distribution cutoff, the weight-distribution form, and clustering coefficient.
Takeaways & Limitations
The disparity backbone preserves relevant connections and hierarchies across weight scales, including statistically significant small-weight edges that global thresholding removes.
Takeaways & Limitations
The method is primarily suited to systems with strong disorder and globally and locally heterogeneous weights.
Abstract
from arXiv · showhide
A large number of complex systems find a natural abstraction in the form of weighted networks whose nodes represent the elements of the system and the weighted edges identify the presence of an interaction and its relative strength. In recent years, the study of an increasing number of large scale networks has highlighted the statistical heterogeneity of their interaction pattern, with degree and weight distributions which vary over many orders of magnitude. These features, along with the large number of elements and links, make the extraction of the truly relevant connections forming the network's backbone a very challenging problem. More specifically, coarse-graining approaches and filtering techniques are at struggle with the multiscale nature of large scale systems. Here we define a filtering method that offers a practical procedure to extract the relevant connection backbone in complex multiscale networks, preserving the edges that represent statistical significant deviations with respect to a null model for the local assignment of weights to edges. An important aspect of the method is that it does not belittle small-scale interactions and operates at all scales defined by the weight distribution. We apply our method to real world network instances and compare the obtained results with alternative backbone extraction techniques.
Results and Discussion
The disparity filter extracts statistically significant local weight heterogeneities across scales, retaining relevant structure while substantially reducing network size. Applied to real networks, it preserves broad structural and weight properties better than global thresholding, but is intended primarily for strongly disordered systems.
- Reduction methods: Global thresholding imposes a characteristic weight scale, systematically overlooking low-strength nodes and local structures below the cutoff.This is especially problematic when node strengths and edge weights are heavy-tailed and locally correlated.
- Disparity filtering: The disparity filter evaluates each edge against a node-level null model of random normalized-weight assignment to identify statistically significant local heterogeneity.An edge is retained when its weight is statistically incompatible with the null hypothesis for at least one incident node.
- The multiscale backbone of real networks.: At α ≈0.05, airport backbones retain more than 80% of total weight and 66% of nodes while keeping only 17% of edges.Global thresholding cannot preserve a comparable majority of nodes at similar retained weight or edge fractions.
- The multiscale backbone of real networks.: For α in [0.01, 0.5], airport backbones combine large node and weight fractions, original-network clustering, stable degree distributions, and strong edge reduction.For α ≲0.01, node and weight fractions begin decreasing significantly.
- Real-network backbones: The method retains statistically significant small-weight connections alongside dominant links, revealing multiscale transportation hierarchies and local airport hubs.These small-scale connections would be removed by a global threshold.
- Real-network backbones: In the Florida Bay food web, the α = 0.0008 backbone contains the top 40% of heaviest links and approximately half of the network’s total weight.The directed backbone also exposes star motifs, significant flux subsystems, and species with few trophic links that may have structural importance.
- The multiscale backbone of real networks.: The disparity filter preserves nearly all weight and many nodes while maintaining the degree-distribution cutoff, weight-distribution form, and clustering coefficient with far fewer edges.For airport networks, clustering remains stable until α becomes very restrictive, while the filtering process retains almost all weight scales except the smallest.
- Conclusions.: The method’s main scope boundary is strong disorder, requiring heterogeneous weights at both global and local levels.The authors recommend judging filter choice against the problem and do not exclude combining techniques.
The disparity filter for directed weighted networks
The directed disparity filter evaluates incoming and outgoing weights separately against degree-dependent null-model expectations, preserving statistically significant local heterogeneities. It retains an edge when it is significant for at least one endpoint, thereby selecting relevant fluctuations across scales while preserving small nodes and connectivity.
- Directed weighted networks: Directed networks represent each node with separate incoming and outgoing degrees, requiring direction-specific weight analysis.Incoming and outgoing connections are evaluated separately because an edge's role differs at its head and tail.
- Null model: The method compares normalized incoming and outgoing weights with null models that assume independent random assignments within each direction.The null-model moments depend on the relevant incoming or outgoing degree, so each node is compared with degree-matched expectations.
- Statistical test: Local heterogeneity is identified when an observed disparity falls outside the null-compatible region defined by the expected value, variability, and significance parameter a.Increasing a makes detection more restrictive; a typical Gaussian-analogy choice is a = 2.
- Backbone construction: The directed backbone preserves every edge whose incoming or outgoing test exceeds the threshold for at least one endpoint, using the appropriate head or tail null model.An outgoing connection is tested for the tail node, while the same connection is incoming for the head node.
- Backbone construction: The procedure retains relevant fluctuations at all scales, avoids belittling low-strength nodes, and keeps otherwise indispensable links to maintain network connectivity.For certain degree-one cases, an edge is retained because it is the only way to preserve connectivity.
- Backbone hierarchy: A constant significance level enables comparisons across nodes with different connection magnitudes and strengths, while decreasing confidence produces progressively more restrictive backbone hierarchies.The hierarchical interpretation is effective when weight heterogeneity is high; otherwise pruning may lose its hierarchical character.
Networks with uncorrelated weights
For uncorrelated weights, the disparity filter is analytically approximately equivalent to global thresholding under a relation between α and ωc, including for heterogeneous distributions with a defined average.
- Analytical equivalence: The result applies to homogeneous distributions and to power-law distributions with exponent larger than two, whose average is well defined.The method assigns independent edge weights drawn from P(ω) in the uncorrelated model.
- Analytical equivalence: The paper derives approximate equivalence between disparity filtering and global thresholding for uncorrelated weights with a well-defined average.The equivalence is formulated through matching edge survival probabilities.
- Analytical equivalence: For an edge of weight ωij incident to a degree-k node, both filters are compared through their survival probabilities.The disparity-filter probability is denoted S(ωij|k), while global thresholding uses Θ(ωij −ωc).
- Analytical equivalence: The matching threshold is ωc = ⟨ω⟩ln α−1, and the relation is independent of degree k.This follows after the survival-probability expression loses dependence on k.
- Empirical comparison: On an airport network with P(ω) ∝ω−2.5, the two filters produce very similar results when weights are randomly assigned.The figure compares the fractions of retained nodes and edges as a function of retained total weight.
- Endpoint rules: Using independent normalized weights pij = ωij/si and pji = ωij/sj allows the disparity filter to treat an edge’s relevance separately at its two endpoints.The OR rule preserves a connection when it is significant for either endpoint, whereas the AND rule requires significance for both.