Correlation clustering is perhaps the most natural formulation of clustering. Given @math objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its theoretical appeal, the practical relevance of correlation clustering still remains largely unexplored, mainly due to the fact that correlation clustering requires the @math pairwise similarities as input. In this paper we initiate the investigation into algorithms for correlation clustering. In we are given the identifier of a single object and we want to return the cluster to which it belongs in some globally consistent near-optimal clustering, using a small number of similarity queries. Local algorithms for correlation clustering open the door to algorithms, which are particularly useful when the similarity between items is costly to compute, as it is often the case in many practical application domains. They also imply @math distributed and streaming clustering algorithms, @math constant-time estimators and testers for cluster edit distance, and @math property-preserving parallel reconstruction algorithms for clusterability. Specifically, we devise a local clustering algorithm attaining a @math -approximation in time @math independently of the dataset size. An explicit approximate clustering for all objects can be produced in time @math (which is provably optimal). We also provide a fully additive @math -approximation with local query complexity @math and time complexity @math . The latter yields the fastest polynomial-time approximation scheme for correlation clustering known to date.
Finally, we point out the work of Spielman and Teng @cite_28 pertaining local clustering algorithms. In their papers an algorithm is local'' if it can, given a vertex @math , output @math 's cluster in time nearly linear in the cluster's size. Our local clustering algorithms also have this ability (assuming, as they do, that for each vertex we are given a list of its neighbours), although the results are not comparable because @cite_28 attempt to minimize the cluster's conductance.
@cite_28
2135512436
We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster---a subset of vertices whose internal connections are significantly richer than its external connections---near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph....