Probabilistic Group Dependence Approach For Discovering Overlapping Clusters
Elena Ivannikova, University of Jyväskylä
Anna Kononova, Heriot-Watt University
Timo Hämäläinen, University of Jyväskylä

This article proposes Soft Dependence Clustering (SDC) algorithm which belongs to the class of spectral clustering methods. On each iteration, SDC performs a hierarchical clustering producing a binary split which greedily maximizes the group dependence score. One of the advantages of SDC is the fact that division of a group into two clusters is done based on the adjustable threshold which has a clear probabilistic interpretation. Due to this property, the algorithm naturally allows fuzzy group separations which makes it also suitable for cluster overlaps analysis. SDC can be used for graph segmentation applications as well as clustering data that has notion of distance. The proposed algorithm is compared with a few selected clustering methods using simulated and real-world data sets. The results clearly demonstrate that given reasonable settings, SDC outperforms other methods in the comparison.