Faster Approximation Algorithms for Parameterized Graph Clustering and
  Edge Labeling
Vedangi Bengali Nate Veldt
Graph clustering is a fundamental task in network analysis where the goal is
to detect sets of nodes that are well-connected to each other but sparsely
connected to the rest of the graph. We present faster approximation algorithms
for an NP-hard parameterized clustering framework called LambdaCC, which is
governed by a tunable resolution parameter and generalizes many other
clustering objectives such as modularity, sparsest cut, and cluster deletion.
Previous LambdaCC algorithms are either heuristics with no approximation
guarantees, or computationally expensive approximation algorithms. We provide
fast new approximation algorithms that can be made purely combinatorial. These
rely on a new parameterized edge labeling problem we introduce that generalizes
previous edge labeling problems that are based on the principle of strong
triadic closure and are of independent interest in social network analysis. Our
methods are orders of magnitude more scalable than previous approximation
algorithms and our lower bounds allow us to obtain a posteriori approximation
guarantees for previous heuristics that have no approximation guarantees of
their own.