# Structure-Preserving Sparsification Methods for Social Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2016.

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

- [Graph Sparsification via Mixture of Graphs](https://mlsanity.com/paper/2405.14260/) (2024)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness](https://mlsanity.com/paper/2402.01242/) (2024)
- [A Generic Graph Sparsification Framework using Deep Reinforcement Learning](https://mlsanity.com/paper/2112.01565/) (2021)
- [Graph-Based Model-Agnostic Data Subsampling for Recommendation Systems](https://mlsanity.com/paper/2305.16391/) (2023)
- [On the Robustness of Graph Reduction Against GNN Backdoor](https://mlsanity.com/paper/2407.02431/) (2024)
- [Sparsistent filtering of comovement networks from high-dimensional data](https://mlsanity.com/paper/2101.09174/) (2021)
- [On the Adversarial Robustness of Graph Neural Networks with Graph Reduction](https://mlsanity.com/paper/2412.05883/) (2024)
- [Not All Neighbors Matter: Understanding the Impact of Graph Sparsification on GNN Pipelines](https://mlsanity.com/paper/2603.06952/) (2026)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)

## Abstract (arXiv)

Sparsification reduces the size of networks while preserving structural and statistical properties of interest. Various sparsifying algorithms have been proposed in different contexts. We contribute the first systematic conceptual and experimental comparison of textitedge sparsification methods on a diverse set of network properties. It is shown that they can be understood as methods for rating edges by importance and then filtering globally or locally by these scores. We show that applying a local filtering technique improves the preservation of all kinds of properties. In addition, we propose a new sparsification method (textitLocal Degree) which preserves edges leading to local hub nodes. All methods are evaluated on a set of social networks from Facebook, Google+, Twitter and LiveJournal with respect to network properties including diameter, connected components, community structure, multiple node centrality measures and the behavior of epidemic simulations. In order to assess the preservation of the community structure, we also include experiments on synthetically generated networks with ground truth communities. Experiments with our implementations of the sparsification methods (included in the open-source network analysis tool suite NetworKit) show that many network properties can be preserved down to about 20% of the original set of edges for sparse graphs with a reasonable density. The experimental results allow us to differentiate the behavior of different methods and show which method is suitable with respect to which property. While our Local Degree method is best for preserving connectivity and short distances, other newly introduced local variants are best for preserving the community structure.