Greedy Recursive Spectral Bisection for Modularity-bound Hierarchical Divisive Community Detection

Abstract Spectral clustering refers to a class of techniques that depend on the eigenstructure of a similarity matrix for the purpose of dividing data points into disjoint clusters, where points within the same cluster exhibit high similarity and those in different clusters have a lower similarity. The objective of this work was to develop a spectral method that could be compared to clustering algorithms which represent the current state of art. This investigation conceived a novel spectral clustering method, as well as 5 policies which guide its execution, based on spectral graph theory and embodying hierarchical clustering principles. Computational experiments were undertaken in this study to evaluate the clustering methods under scrutiny. The assessment was performed using two evaluation metrics, specifically the adjusted Rand index, and modularity. The obtained results furnish compelling evidence, indicating that the proposed method is competitive and possesses distinctive properties compared to those elucidated in the existing literature. This suggests that our approach stands as a viable alternative, offering a robust choice within the spectrum of available same-purpose tools.