Type: Seminar

Distribution: World

Expiry: 29 Jan 2016

CalTitle1: Latent structure of sparse random networks

Auth: jormerod@pjormerod5.pc (assumed)

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.