Cluster Definition by the Optimization of Simple Measures

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.