Source-linked AI summary
Graph spectra and the detectability of community structure in networks
Raj Rao Nadakuditi, M. E. J. Newman
TL;DR
The paper examines when matrix-based methods can detect community structure in networks. Using random matrix methods to analyze adjacency and modularity spectra, it identifies a sharp detectability transition and shows spectral modularity maximization is optimal for the studied model.
Problem
Community detection seeks accurate and efficient identification of densely connected groups, but the formal properties and performance limits of matrix-based methods have received less study.
Method
The authors use random matrix methods to analyze the spectral properties of adjacency and modularity matrices in stochastic block-model networks.
Results
The spectra exhibit a sharp transition separating detectable community structure from a regime where communities remain present but spectral methods cannot detect them.
Takeaways & Limitations
Because the transition coincides with that of an optimal Bayesian maximum-likelihood method, spectral modularity maximization is optimal for the studied model.
Takeaways & Limitations
The analysis is accurate for large-average-degree networks and uses the standard stochastic block model; extensions to low-degree and more complex models remain open.
Abstract
from arXiv · showhide
We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.