Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
arXiv:1604.03159
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.
arXiv commentAccepted to IEEE Transactions on Signal Processing
References in corpus (19)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Discrete Signal Processing on Graphs
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Abrupt transition in the structural formation of interconnected networks
- Graph spectra and the detectability of community structure in networks
- Signal Recovery on Graphs: Variation Minimization
- Local-set-based Graph Signal Reconstruction
- Clustering with Multi-Layer Graphs: A Spectral Perspective
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Estimating the number of communities in a network
- Multi-layer graph analysis for dynamic social networks
- Phase Transitions in Spectral Community Detection
- Universal Phase Transition in Community Detectability under a Stochastic Block Model
- Incremental Method for Spectral Clustering of Increasing Orders
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