A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
Authors:
- Jiong GuoJGJiong Guo
- Christian KomusiewiczCKChristian Komusiewicz
- Rolf NiedermeierRNRolf Niedermeier
- Johannes UhlmannJUJohannes Uhlmann
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 24 (4) , 1662-1683
Abstract
We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least $|S|-s$. Cliques are 1-plexes. The advantage of s-plexes for $s\geq2$ is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering.
Keywords
This publication has 33 references indexed in Scilit:
- Isolation concepts for efficiently enumerating dense subgraphsTheoretical Computer Science, 2009
- A more effective linear kernelization for cluster editingTheoretical Computer Science, 2009
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph propertiesJournal of Computer and System Sciences, 2008
- Transmission Network Analysis in Tuberculosis Contact InvestigationsThe Journal of Infectious Diseases, 2007
- Invitation to data reduction and problem kernelizationACM SIGACT News, 2007
- Complex trait analysis of gene expression uncovers polygenic and pleiotropic networks that modulate nervous system functionNature Genetics, 2005
- Graph-Modeled Data Clustering: Exact Algorithms for Clique GenerationTheory of Computing Systems, 2005
- Correlation ClusteringMachine Learning, 2004
- A general method to speed up fixed-parameter-tractable algorithmsInformation Processing Letters, 2000
- NP-hard problems in hierarchical-tree clusteringActa Informatica, 1986