Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering

Abstract

One of the longstanding open problems in spectral graph clustering (SGC) is the so-called model order selection problem: automated selection of the correct number of clusters. This is equivalent to the problem of finding the number of connected components or communities in an undirected graph. We propose automated model order selection (AMOS), a solution to the SGC model selection problem under a random interconnection model (RIM) using a novel selection criterion that is based on an asymptotic phase transition analysis. AMOS can more generally be applied to discovering hidden block diagonal structure in symmetric non-negative matrices. Numerical experiments on simulated graphs validate the phase transition analysis, and real-world network data is used to validate the performance of the proposed model selection procedure.

Accepted to IEEE Transactions on Signal Processing

References in corpus (9)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Discrete Signal Processing on Graphs
• Graph spectra and the detectability of community structure in networks
• Local-set-based Graph Signal Reconstruction
• Estimating the number of communities in a network
• Universal Phase Transition in Community Detectability under a Stochastic Block Model

Cited by in corpus (6)

• Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms
• AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
• Revisiting Spectral Graph Clustering with Generative Community Models
• Node Embedding via Word Embedding for Network Community Discovery
• Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications
• Scalable Spectral Clustering Using Random Binning Features