Higher-order spectral clustering for geometric graphs

DOI10.1007/S00041-021-09825-2MaRDI QIDQ2658739zbMATH OpenOpenAlexFDO

Authors Andrei V. Bobu, Maximilien Dreveton, Konstantin Avrachenkov

Publication date 24 March 2021

Published in The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.11353

zbMATH Keywords

block modelsrandom geometric graphsspectral clustering

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector associated with a higher-order eigenvalue. We establish the weak consistency of this algorithm for a wide class of geometric graphs which we call Soft Geometric Block Model. A small adjustment of the algorithm provides strong consistency. We also show that our method is effective in numerical experiments even for graphs of modest size.

Recommendations

• Spectral clustering and block models: a review and a new algorithm
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of spectral clustering
• A variational approach to the consistency of spectral clustering
• Partitioning well-clustered graphs: spectral clustering works!

Cites work

• A new look at independence
• Community detection and stochastic block models: recent developments
• Community detection on Euclidean random graphs
• Connectivity of soft random geometric graphs
• Consistency of spectral clustering in stochastic block models
• Eigenvalues of Euclidean random matrices
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 3563431 (Why is no real title available?)
• Performance and Accuracy of LAPACK's Symmetric Tridiagonal Eigensolvers
• Residual Bounds on Approximate Eigensystems of Nonnormal Matrices
• Spectral partitioning works: planar graphs and finite element meshes

Cited in

(9)

• Consistency of modularity clustering on random geometric graphs
• Spectral clustering based on local linear approximations
• A graph spectrum based geometric biclustering algorithm
• Overview of the topical collection: harmonic analysis on combinatorial graphs
• Spectral clustering and block models: a review and a new algorithm
• How the result of graph clustering methods depends on the construction of the graph
• On the efficacy of higher-order spectral clustering under weighted stochastic block models
• Random geometric graph: some recent developments and perspectives
• A self-adjusting spectral clustering algorithm

This page was built for publication: Higher-order spectral clustering for geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658739)