Skip to Main content Skip to Navigation
Journal articles

Higher-Order Spectral Clustering for Geometric Graphs

Konstantin Avrachenkov 1 Andrei Bobu 1 Maximilien Dreveton 1
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadata

https://hal.inria.fr/hal-03169834
Contributor : Konstantin Avrachenkov <>
Submitted on : Monday, March 15, 2021 - 5:42:58 PM
Last modification on : Tuesday, March 16, 2021 - 3:29:41 AM

File

Avrachenkov2021_Article_Higher...
Publication funded by an institution

Identifiers

Collections

Citation

Konstantin Avrachenkov, Andrei Bobu, Maximilien Dreveton. Higher-Order Spectral Clustering for Geometric Graphs. Journal of Fourier Analysis and Applications, Springer Verlag, 2021, 27, ⟨10.1007/s00041-021-09825-2⟩. ⟨hal-03169834⟩

Share

Metrics

Record views

98

Files downloads

137