Spectral analysis in bipartite biregular graphs and community detection

This thesis concerns to spectral gap of random regular graphs and consists of two main con- tributions. 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. Secondly, we use a spectral algorithm to recover hidden communities in a random network model we call regular stochastic block model. We rely on a technique introduced recently by Massoullie, which we develop here for random regular graphs.

Author dc:creator

• Brito, Gerandy

Advisors dc:contributor.advisor

• Dumitriu, Ioana
• Hoffman, Christopher

• community detection
• regular graphs
• spectral analysis
• spectral gap
• Mathematics

Statement dc:rights

• CC BY-NC

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1773/40636

OAI identifier oai:identifier

oai:digital.lib.washington.edu:1773/40636