Spectral analysis in bipartite biregular graphs and community detection

Stochastics Seminar
Thursday, September 14, 2017 - 15:05
1 hour (actually 50 minutes)
Skiles 006
Georgia Institute of Technology
This talk concerns to spectral gap of random regular graphs. First, we prove that almost all bipartite biregular graphs are almost Ramanujan by providing a tight upper bound for the non trivial eigenvalues of its adjacency operator, proving Alon's Conjecture for this family of graphs. Also, we use a spectral algorithm to recover hidden communities in a random network model we call regular stochastic block model. Our proofs rely on a technique introduced recently by Massoullie, which we developed for random regular graphs.