  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.
