Spectral analysis in bipartite biregular graphs and community detection

Series: 
Stochastics Seminar
Thursday, September 14, 2017 - 15:05
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
Georgia Institute of Technology
,  
Organizer: 
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.