Hierarchical Clustering Supported by Reciprocal Nearest Neighbors

Abstract

Clustering is a fundamental analysis tool aiming at classifying data points into groups based on their similarity or distance. It has found successful applications in all natural and social sciences, including biology, physics, economics, chemistry, astronomy, psychology, and so on. Among numerous existent algorithms, hierarchical clustering algorithms are of a particular advantage as they can provide results under different resolutions without any predetermined number of clusters and unfold the organization of resulted clusters. At the same time, they suffer a variety of drawbacks and thus are either time-consuming or inaccurate. We propose a novel hierarchical clustering approach 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 in comparison with the well-known Girvan-Newman algorithm.

arXiv comment13 pages, 5 figures, 5 supplementary figures, 2 tables

References in corpus (13)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Natural Scales in Geographical Patterns
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Link Prediction in Complex Networks: A Survey
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Community Structure in Jazz
• Modularity and community detection in bipartite networks
• Social Structure of Facebook Networks
• Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm

Cited by in corpus (4)

• Detecting network communities via greedy expanding based on local superiority index
• Multi-view Hierarchical Clustering
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Hierarchical clustering by aggregating representatives in sub-minimum-spanning-trees