Lower Bounds on Paraclique Density

Ronald D. Hagan; Michael A. Langston; Kai Wang

doi:10.1016/j.dam.2015.11.010

Lower Bounds on Paraclique Density

Ronald D. Hagan, Michael A. Langston, Kai Wang

Computer Science

University of Tennessee, Knoxville

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

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.

Original language	American English
Journal	Discrete Applied Mathematics
Volume	204
DOIs	https://doi.org/10.1016/j.dam.2015.11.010
State	Published - May 11 2016

Disciplines

Computer Sciences

Keywords

Clique
Clustering
Graph density
Paraclique

Access to Document

10.1016/j.dam.2015.11.010License: Unspecified

https://doi.org/10.1016/j.dam.2015.11.010

Cite this

@article{077671139f5341c5b84c0c03613e96a0,

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.",

keywords = "Clique, Clustering, Graph density, Paraclique",

author = "Hagan, {Ronald D.} and Langston, {Michael A.} and Kai Wang",

year = "2016",

month = may,

day = "11",

doi = "10.1016/j.dam.2015.11.010",

language = "American English",

volume = "204",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Lower Bounds on Paraclique Density

AU - Hagan, Ronald D.

AU - Langston, Michael A.

AU - Wang, Kai

PY - 2016/5/11

Y1 - 2016/5/11

N2 - 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.

AB - 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.

KW - Clique

KW - Clustering

KW - Graph density

KW - Paraclique

UR - https://digitalcommons.georgiasouthern.edu/compsci-facpubs/54

UR - https://doi.org/10.1016/j.dam.2015.11.010

U2 - 10.1016/j.dam.2015.11.010

DO - 10.1016/j.dam.2015.11.010

M3 - Article

SN - 0166-218X

VL - 204

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Lower Bounds on Paraclique Density

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this