STA 290 Seminar: Can Le

STA 290 Seminar Series

Thursday, January 19th, 4:10pm, MSB 1147 (Colloquium Room)

Refreshments at 3:30pm in MSB 4110 (Statistics Lounge)

Speaker:          Can Le (University of Michigan)

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