Unwinding the hairball graph: pruning algorithms for weighted complex networks

Abstract

Empirical networks of weighted dyadic relations often contain noisy edges that alter the global characteristics of the network and obfuscate the most important structures therein. Graph pruning is the process of identifying the most significant edges according to a generative null model, and extracting the subgraph consisting of those edges. Here, we focus on integer-weighted graphs commonly arising when weights count the occurrences of an "event" relating the nodes. We introduce a simple and intuitive null model related to the configuration model of network generation, and derive two significance filters from it: the Marginal Likelihood Filter (MLF) and the Global Likelihood Filter (GLF). The former is a fast algorithm assigning a significance score to each edge based on the marginal distribution of edge weights whereas the latter is an ensemble approach which takes into account the correlations among edges. We apply these filters to the network of air traffic volume between US airports and recover a geographically faithful representation of the graph. Furthermore, compared with thresholding based on edge weight, we show that our filters extract a larger and significantly sparser giant component.

References in corpus (4)

• Extracting the multiscale backbone of complex weighted networks
• Information filtering in complex weighted networks
• Statistical Mechanics of Multi-Edge Networks
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes

Cited by in corpus (18)

• Understanding the growth of the Fediverse through the lens of Mastodon
• Weight Thresholding on Complex Networks
• backbone: An R package to extract network backbones
• A parametric approach to information filtering in complex networks: The Pólya filter
• Detecting coalitions by optimally partitioning signed networks of political collaboration
• Comparing Alternatives to the Fixed Degree Sequence Model for Extracting the Backbone of Bipartite Projections
• Thresholding normally distributed data creates complex networks
• An Evaluation Tool for Backbone Extraction Techniques in Weighted Complex Networks
• Irreducible network backbones: unbiased graph filtering via maximum entropy
• Linguistic neighbourhoods: explaining cultural borders on Wikipedia through multilingual co-editing activity
• Extracting the signed backbone of intrinsically dense weighted networks
• Associative nature of event participation dynamics: a network theory approach
• Cross-validation of correlation networks using modular structure
• A maximum entropy approach to separating noise from signal in bimodal affiliation networks
• The Atlas for the Aspiring Network Scientist
• Using co-sharing to identify use of mainstream news for promoting potentially misleading narratives
• The Census-Stub Graph Invariant Descriptor
• Linking Multi-Site Sex Ad Data at the Individual Level to Aid Counter-Trafficking Efforts