  The metric backbone of a weighted graph is the union of all-pairs shortest
paths. It is obtained by removing all edges $(u,v)$ that are not the shortest
path between $u$ and $v$. In networks with well-separated communities, the
metric backbone tends to preserve many inter-community edges, because these
edges serve as bridges connecting two communities, but tends to delete many
intra-community edges because the communities are dense. This suggests that the
metric backbone would dilute or destroy the community structure of the network.
However, this is not borne out by prior empirical work, which instead showed
that the metric backbone of real networks preserves the community structure of
the original network well. In this work, we analyze the metric backbone of a
broad class of weighted random graphs with communities, and we formally prove
the robustness of the community structure with respect to the deletion of all
the edges that are not in the metric backbone. An empirical comparison of
several graph sparsification techniques confirms our theoretical finding and
shows that the metric backbone is an efficient sparsifier in the presence of
communities.
