# Unwinding the hairball graph: pruning algorithms for weighted complex networks

arXiv: https://arxiv.org/abs/1503.04085 · HTML: https://mlsanity.com/paper/1503.04085/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2015.

## Built on by (most cited first, 3 of 3)

- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Exploring Time Granularity on Temporal Graphs for Dynamic Link Prediction in Real-world Networks](https://mlsanity.com/paper/2311.12255/) (2023)
- [A cost-based multi-layer network approach for the discovery of patient phenotypes](https://mlsanity.com/paper/2209.09032/) (2022)

## Abstract (arXiv)

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.