title: Lower Bounds on Paraclique Density.
abstract: The scientific literature teems with clique-centric clustering strategies. In this paper we analyze one such method, the paraclique algorithm. Paraclique has found practical utility in a variety of application domains, and has been successfully employed to reduce the effects of noise. Nevertheless, its formal analysis and worst-case guarantees have remained elusive. We address this issue by deriving a series of lower bounds on paraclique densities.
authors.affiliation: Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN, USA, 37996.
authors.forename: Ronald D
authors.initials: RD
authors.lastname: Hagan
authors.affiliation: Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN, USA, 37996.
authors.forename: Michael A
authors.initials: MA
authors.lastname: Langston
authors.affiliation: Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN, USA, 37996.
authors.forename: Kai
authors.initials: K
authors.lastname: Wang
keywords: clique; clustering; graph density; paraclique