<abstract xmlns="http://www.w3.org/1999/xhtml"><p> The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order to discover clusters. Based on matrix perturbation theory and properties of graph spectra we show that the adjacency matrix can be more suitable for partitioning than other Laplacian matrices. The main problem concerning the use of the adjacency matrix is the selection of the appropriate eigenvectors. We thus propose an approach based on analysis of the adjacency matrix spectrum and eigenvector pairwise correlations. Formulated rules and heuristics allow choosing the right eigenvectors representing clusters, i.e., automatically establishing the number of groups. The algorithm requires only one parameter-the number of nearest neighbors. Unlike many other spectral methods, our solution does not need an additional clustering algorithm for final partitioning. We evaluate the proposed approach using real-world datasets of different sizes. Its performance is competitive to other both standard and new solutions, which require the number of clusters to be given as an input parameter.</p></abstract>

The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order to discover clusters. Based on matrix perturbation theory and properties of graph spectra we show that the adjacency matrix can be more suitable for partitioning than other Laplacian matrices. The main problem concerning the use of the adjacency matrix is the selection of the appropriate eigenvectors. We thus propose an approach based on analysis of the adjacency matrix spectrum and eigenvector pairwise correlations. Formulated rules and heuristics allow choosing the right eigenvectors representing clusters, i.e., automatically establishing the number of groups. The algorithm requires only one parameter-the number of nearest neighbors. Unlike many other spectral methods, our solution does not need an additional clustering algorithm for final partitioning. We evaluate the proposed approach using real-world datasets of different sizes. Its performance is competitive to other both standard and new solutions, which require the number of clusters to be given as an input parameter.

Clustering Based on Eigenvectors of the Adjacency Matrix

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Clustering Based on Eigenvectors of the Adjacency Matrix"}

The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order...

Clustering Based on Eigenvectors of the Adjacency Matrix

Published Online: Jan 11, 2019

Page range: 771 - 786

Received: Oct 02, 2017

Accepted: Jun 10, 2018

DOI: https://doi.org/10.2478/amcs-2018-0059

Keywords
spectral clustering, adjacency matrix eigenvalues/eigenvectors, graph perturbation theory, eigengap heuristics

© 2019 Małgorzata Lucińska, Sławomir T. Wierzchoń, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Clustering Based on Eigenvectors of the Adjacency Matrix

Published Online: Jan 11, 2019

Page range: 771 - 786

Received: Oct 02, 2017

Accepted: Jun 10, 2018

DOI: https://doi.org/10.2478/amcs-2018-0059

Keywordsspectral clustering, adjacency matrix eigenvalues/eigenvectors, graph perturbation theory, eigengap heuristics

© 2019 Małgorzata Lucińska, Sławomir T. Wierzchoń, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
spectral clustering, adjacency matrix eigenvalues/eigenvectors, graph perturbation theory, eigengap heuristics