  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.
