Conference Proceedings
A Correlation Clustering Framework for Community Detection
Nate Veldt, David F Gleich, Anthony Wirth
ASSOC COMPUTING MACHINERY | Published : 2018
Open access
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, λ, 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 clusteri..
View full abstractGrants
Awarded by NSF
Funding Acknowledgements
This work was supported by several funding agencies: Nate Veldt and David Gleich are supported by NSF award IIS-154648, David Gleich is additionally supported by NSF awards CCF-1149756 and CCF-093937 as well as the DARPA Simplex program and the Sloan Foundation. Anthony Wirth is supported by the Australian Research Council. We thank Flavio Chierichetti for several helpful conversations and also thank the anonymous reviewers for several helpful suggestions for improving our work, in particular for mentioning connections to the work of van Zuylen and Williamson [38], which led to significantly improved approximation results.