Skip to Content

College of Arts & Sciences
Department of Statistics


Can Minh Le Colloquium

Thursday, February 4, 2016 - 2:45pm

Statistics Department Colloquium

Where: LeConte College, Room 210

Speaker: Can Minh Le

Affiliation: University of Michigan, Department of Statistics

Title:  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.