Statistics Seminar: Can Le (University of Michigan) -- Latent structure of sparse random networks

Abstract: 

Network analysis has become an important area in many research domains. 
A common way to study real-world networks is to model them as random 
graphs whose structure is encoded in the expectation matrix. We consider 
a general model of networks on $n$ nodes, known as the inhomogeneous 
Erdos-Renyi model, where edges between nodes are formed independently 
and possibly with different probabilities. We study the behavior of 
such random networks through the concentration of their adjacency and 
Laplacian matrices in the spectral norm. Sparse random networks whose 
expected average degrees grow slower than $\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 immediate consequence, we establish the validity of one of the 
simplest and fastest approaches to community detection – regularized 
spectral clustering, under the stochastic block model. We also discuss 
how to choose the regularization parameter and estimate the number of 
communities.