HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Monday, March 15, 2021 - 5:42:58 PM
Last modification on : Friday, February 4, 2022 - 3:24:51 AM
Long-term archiving on: : Wednesday, June 16, 2021 - 7:20:06 PM

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

90

Files downloads

108