A distance-based spectral clustering approach with applications to network community detection

Spectral clustering is an important unsupervised learning approach to many object partitioning and pattern analysis problems. In this paper, we present our work on a novel spectral clustering algorithm that groups a collection of objects using the spectrum of the pairwise distance matrix. If the points in a metric space can be associated with a well-defined distance, it is proven that the pairwise distance matrix is almost negative definite, and we show that the eigenvectors for its most significant negative eigenvalue can be used to approximate the solution to a quadratic binary partition problem. We define the quality measures for the one dimensional partitioning of the eigenvector entries, which are further applied to evaluate the partitioning results for the data points projected into the space spanned by the selected eigenvectors. Since the Lanczos iterative algorithm may be revised to find the eigenvalues efficiently in a distributed way, we adapt this algorithm to the network community detection problem using a decentralized multi-agent framework. The performance of the proposed approach is tested with different datasets, and the empirical experiments show that this approach is able to enhance the effectiveness of clustering.