We will go beyond the expanders and generalize the Laplacian based spectral clustering methods to recover so-called regular cluster pairs of an edge-weighted graph such that the information ow between the pairs and within the clusters is homogeneous. For this purpose, we take into consideration both ends of the normalized Laplacian spectrum, i.e., large absolute value, so-called structural eigenvalues of our normalized modularity matrix introduced just for this convenience. The normalized modularity spectrum is testable as it corresponds to the spectrum of the operator taking conditional expectation with respect to the joint distribution determined by the edge-weights. We estimate the constant of volume regularity in terms of the gap between the structural and other eigenvalues, and the k-variance of the optimum vertex representatives constructed by the eigenvectors corresponding to the structural eigenvalues. The clusters themselves can be recovered by applying the k-means algorithm for the vertex representatives.
In a random graph setup, we investigate the asymptotic properties of the eigenvalues and corresponding eigen-subspaces in a generalized random graph model as the number of vertices tends to infinity together with the cluster sizes. Parameter estimation can be performed via the EM-algorithm. Spectral biclustering of rectangular arrays will also be discussed together with possible applications to microarrays and other biological, social, or communication networks.