Community-aware network sparsification
Files
Accepted manuscript
Date
2017-06-11
Authors
Gionis, Aristides
Tatti, Nikolaj
Rozenshtein, Polina
Terzi, Evimaria
Version
Accepted manuscript
OA Version
Citation
E Terzi, Aristides Gionis, Nikolaj Tatti, Polina Rozenshtein. 2017. "Community-aware network sparsification." Proceedings of the 2017 SIAM International Conference on Data Mining. pp. 426-434.
Abstract
Network sparsification aims to reduce the number of edges of a network while maintaining its structural properties; such properties include shortest paths, cuts, spectral measures, or network modularity. Sparsification has multiple applications, such as, speeding up graph-mining algorithms, graph visualization, as well as identifying the important network edges.
In this paper we consider a novel formulation of the network-sparsification problem. In addition to the network, we also consider as input a set of communities. The goal is to sparsify the network so as to preserve the network structure with respect to the given communities. We introduce two variants of the community-aware sparsification problem, leading to sparsifiers that satisfy different connectedness community properties. From the technical point of view, we prove hardness results and devise effective approximation algorithms. Our experimental results on a large collection of datasets demonstrate the effectiveness of our algorithms.