A Probabilistic MajorClust Variant for the Clustering of Near-Homogeneous Graphs

Clustering remains a major topic in machine learning; it is used e.g. for document categorization, for data mining, and for image analysis. In all these application areas, clustering algorithms try to identify groups of related data in large data sets. In this paper, the established clustering algorithm MajorClust ([12]) is improved; making it applicable to data sets with few structure on the local scale—so called near-homogeneous graphs. This new algorithm MCProb is verified empirically using the problem of image clustering. Furthermore, MCProb is analyzed theoretically. For the applications examined so-far, MCProb outperforms other established clustering techniques.