Hierarchical Single-Linkage Clustering for Community Detection with Overlaps and Outliers

Most community detection approaches make very strong assumptions about communities in the data, such as every vertex must belong to exactly one community (the communities form a partition). For vector data, Hierarchical Density Based Spatial Clustering for Applications with Noise (HDBSCAN) has emerged as a leading clustering algorithm that allows for outlier points that do not belong to any cluster. The first step in HDBSCAN is to redefine the distance between vectors in such a way that single-linkage clustering is effective and robust to noise. Many community detection algorithms start with a similar step that attempts to increase the weight of edges between similar nodes and decrease weights of noisy edges. In this paper, we apply the hierarchical single-linkage clustering algorithm from HDBSCAN to a variety of node/edge similarity scores to see if there is an algorithm that can effectively detect clusters while allowing for outliers. In experiments on synthetic and real world data sets, we find that no single method is optimal for every type of graph, but the admirable performance indicates that hierarchical single-linkage clustering is a viable paradigm for graph clustering.