Clustering by Vertex Density in a Graph

In this paper we introduce a new principle for two classical problems in clustering: obtaining a set of partial classes and a partition on a set X of n elements. These structures are built from a distance D and a threshold value σ giving a threshold graph on X with maximum degree δ. The method is based on a density function De : X → R which is computed first from D. Then, the number of classes, the classes, and the partitions are established using only this density function and the graph edges, with a computational complexity of o(nδ). Monte Carlo simulations, from random Euclidian distances, validate the method.