JSM 2015 Preliminary Program

Online Program Home
My Program

Abstract Details

Activity Number: 87
Type: Contributed
Date/Time: Sunday, August 9, 2015 : 4:00 PM to 5:50 PM
Sponsor: Section on Statistical Learning and Data Mining
Abstract #316597
Title: Sparse Random Graphs: Regularization and Concentration of the Laplacian
Author(s): Can Le* and Elizaveta Levina and Roman Vershynin
Companies: University of Michigan and University of Michigan and University of Michigan
Keywords:
Abstract:

We study random graphs with possibly different edge probabilities and which can be very sparse -- the expected degrees may be bounded. The spectrum of a sparse graph is highly irregular, and the Laplacian fails to concentrate near its expectation. We prove that concentration of the Laplacian can be enforced by regularizing the graph by simply adding the same value (of order $1/n$) to each entry of the adjacency matrix. This regularization was proposed in the analysis of complex networks, where its beneficial effects were observed empirically. The current work justifies these empirical predictions. It establishes the validity of one of the simplest and fastest proposed approaches to community detection in sparse networks -- regularized spectral clustering. Our proof of concentration is based on Grothendieck inequality combined with paving arguments.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2015 program





For program information, contact the JSM Registration Department or phone (888) 231-3473.

For Professional Development information, contact the Education Department.

The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.

2015 JSM Online Program Home