2012 ChromaticCorrelationClustering

• (Bonchi et al., 2012) ⇒ Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Antti Ukkonen. (2012). “Chromatic Correlation Clustering.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339735

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Chromatic+Correlation+Clustering
• http://dl.acm.org/citation.cfm?id=2339530.2339735&preflayout=flat#citedby

Quotes

Author Keywords

• Clustering; data mining; edge-labeled graphs

Abstract

We study a novel clustering problem in which the pairwise relations between objects are categorical. This problem can be viewed as clustering the vertices of a graph whose edges are of different types (colors). We introduce an objective function that aims at partitioning the graph such that the edges within each cluster have, as much as possible, the same color. We show that the problem is NP-hard and propose a randomized algorithm with approximation guarantee proportional to the maximum degree of the input graph. The algorithm iteratively picks a random edge as pivot, builds a cluster around it, and removes the cluster from the graph. Although being fast, easy-to-implement, and parameter free, this algorithm tends to produce a relatively large number of clusters. To overcome this issue we introduce a variant algorithm, which modifies how the pivot is chosen and and how the cluster is built around the pivot. Finally, to address the case where a fixed number of output clusters is required, we devise a third algorithm that directly optimizes the objective function via a strategy based on the alternating minimization paradigm.

We test our algorithms on synthetic and real data from the domains of protein-interaction networks, social media, and bibliometrics. Experimental evidence show that our algorithms outperform a baseline algorithm both in the task of reconstructing a ground-truth clustering and in terms of objective function value.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 ChromaticCorrelationClustering	Francesco Bonchi Aristides Gionis Antti Ukkonen Francesco Gullo			Chromatic Correlation Clustering				10.1145/2339530.2339735		2012