  This paper studies how close random graphs are typically to their
expectations. We interpret this question through the concentration of the
adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous
Erd\"os-R\'enyi random graphs on $n$ vertices, where edges form independently
and possibly with different probabilities $p_{ij}$. Sparse random graphs whose
expected degrees are $o(\log n)$ fail to concentrate; the obstruction is caused
by vertices with abnormally high and low degrees. We show that concentration
can be restored if we regularize the degrees of such vertices, and one can do
this in various ways. As an example, let us reweight or remove enough edges to
make all degrees bounded above by $O(d)$ where $d=\max np_{ij}$. Then we show
that the resulting adjacency matrix $A'$ concentrates with the optimal rate:
$\|A' - \mathbb{E} A\| = O(\sqrt{d})$. Similarly, if we make all degrees
bounded below by $d$ by adding weight $d/n$ to all edges, then the resulting
Laplacian concentrates with the optimal rate: $\|L(A') - L(\mathbb{E} A')\| =
O(1/\sqrt{d})$. Our approach is based on Grothendieck-Pietsch factorization,
using which we construct a new decomposition of random graphs. We illustrate
the concentration results with an application to the community detection
problem in the analysis of networks.
