Sparse random graphs: regularization and concentration of the Laplacian

Understand

We study random graphs with possibly different edge probabilities in the challenging sparse regime of bounded expected degrees.

• Unlike in the dense case, neither the graph adjacency matrix nor its Laplacian concentrate around their expectations due to the highly irregular distribution of node degrees.
• It has been empirically observed that simply adding a constant of order $1/n$ to each entry of the adjacency matrix substantially improves the behavior of Laplacian.
• Here we prove that this regularization indeed forces Laplacian to concentrate even in sparse graphs.