Hierarchical clustering supported by reciprocal nearest neighbors

Clustering is a fundamental tool aiming at classifying data points into groups based on their pairwise distances or similarities. It has found successful applications in all natural and social sciences, including biology, physics, economics, chemistry, astronomy, psychology, and so on. Among various types of algorithms, hierarchical clustering is of particular advantages as it can provide results under different resolutions without the knowledge of a predetermined number of clusters. At the same time, it is usually time-consuming or inaccurate. In this paper, we propose a novel hierarchical clustering algorithm on the basis of a simple hypothesis that two reciprocal nearest data points should be grouped in one cluster. Extensive tests on data sets across multiple domains show that our method is much faster and more accurate than the state-of-the-art benchmarks. We further extend our method to deal with the community detection problem in real networks, achieving remarkably better results than the well-known Girvan-Newman algorithm. (C) 2020 Elsevier Inc. All rights reserved.