Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering

Abstract

Graph clustering, or community detection, is the task of identifying groups of closely related objects in a large network. In this paper we introduce a new community-detection framework called LambdaCC that is based on a specially weighted version of correlation clustering. A key component in our methodology is a clustering resolution parameter, $\lambda$, which implicitly controls the size and structure of clusters formed by our framework. We show that, by increasing this parameter, our objective effectively interpolates between two different strategies in graph clustering: finding a sparse cut and forming dense subgraphs. Our methodology unifies and generalizes a number of other important clustering quality functions including modularity, sparsest cut, and cluster deletion, and places them all within the context of an optimization problem that has been well studied from the perspective of approximation algorithms. Our approach is particularly relevant in the regime of finding dense clusters, as it leads to a 2-approximation for the cluster deletion problem. We use our approach to cluster several graphs, including large collaboration networks and social networks.

References in corpus (6)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Statistical Mechanics of Community Detection
• The ground truth about metadata and community detection in networks
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering

Cited by in corpus (14)

• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Universality of the stochastic block model
• Understanding the Cluster LP for Correlation Clustering
• Correlation Clustering Generalized
• Metrics matter in community detection
• Stochastic Block Models are a Discrete Surface Tension
• Combinatorial Correlation Clustering
• A Projection Method for Metric-Constrained Optimization
• Scalable Community Detection via Parallel Correlation Clustering
• Flow-Partitionable Signed Graphs
• Lexicographically Ordered Multi-Objective Clustering
• GPU-Accelerated Multilevel Graph Clustering: A Parallel Perspective on Louvain and Leiden
• Learning Resolution Parameters for Graph Clustering
• Correlation-Based Community Detection