Of the largest eigenvalue for modularity-based partitioning

Despite the popularity and broad range of spectral clustering algorithms, there is little work addressing the statistical significance of clustering results. Spectral clustering uses the eigenvalues of matrices, such as the Laplacian graph or the adjacency matrix minus a null model, to partition a network. Even though the distribution of the largest eigenvalue for these matrices is not known, random matrix theory provides analytical formulas for a family of matrices called Gaussian random ensembles. We demonstrate that the Tracy-Widom mapping of the largest eigenvalue of Gaussian random ensembles can be modified to predict the distribution of the largest eigenvalue of matrices used for modularity-based spectral clustering. Using this finding we derive formulas that control the type I error rate on modularity-based partitions.