  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. As an immediate consequence in network
analysis, we establish the validity of one of the simplest and fastest
approaches to community detection -- regularized spectral clustering, under the
stochastic block model. Our proof of concentration of regularized Laplacian is
based on Grothendieck's inequality and factorization, combined with paving
arguments.
