title: Cluster definition by the optimization of simple measures.
abstract: We adopt the following measures of clustering based on simple edge counts in an undirected loop-free graph. Let S be a subset of the points of the graph. The compactness of S is measured by the number of edges connecting points in S to other points in S. The isolation or separation of S is measured by the negative of the number of edges connecting points in S to points not in S. The subset S is a cluster if it is compact and isolated. We study the cluster search problem: find a subset S which maximizes a linear combination of the compactness and (negative) isolation edge counts. We show that a closely related decision problem is NP-complete. We develop a pruned search tree algorithm which is much faster than complete search, especially for graphs which are derived from points embedded in a space of low dimensionality.
authors.affiliation: Department of Computer Science, University of Wyoming, Laramie, WY 82071.
authors.forename: T
authors.initials: T
authors.lastname: Bailey
authors.forename: J
authors.initials: J
authors.lastname: Cowles