Student Seminars

Can Le
PhD student, Department of Statistics, University of Michigan

Sparse random graphs: regularization and concentration of the Laplacian

We study random graphs with possibly different edge probabilities and which can be very sparse, so the expected degrees may be bounded. The spectrum of a sparse graph is highly irregular, and the Laplacian fails to concentrate near its expectation. We prove that concentration of the Laplacian can be enforced by regularizing the graph by simply adding the same value (of order $1/n$) to each entry of the adjacency matrix. Our proof of concentration is based on Grothendieck inequality combined with paving arguments. This regularization was proposed in the analysis of complex networks, where its beneficial effects were observed empirically. The current work justifies these empirical predictions. It establishes the validity of one of the simplest and fastest proposed approaches to community detection in sparse networks - regularized spectral clustering.

Student Seminar Archive

For questions regarding the Statistics Student Seminar or if you are interested in presenting, please contact Joonha Park(joonhap@umich.edu) or Jingshen Wang(jshwang@umich.edu).