{"id":{"repo_id":"washington","oai_identifier":"oai:digital.lib.washington.edu:1773/40636"},"canonical_url":"https://search.dev.ndltd.org/etd/washington/oai:digital.lib.washington.edu:1773/40636","repository":{"repo_id":"washington","name":"University of Washington","base_url":"https://digital.lib.washington.edu/server/oai/request"},"display":{"title":"Spectral analysis in bipartite biregular graphs and community detection","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Brito, Gerandy"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Dumitriu, Ioana","Hoffman, Christopher"],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-10-26","date_published":"2017-10-26","updated_at":"2026-07-24T05:58:01Z","subjects":["community detection","regular graphs","spectral analysis","spectral gap","Mathematics"],"languages":["en_US"],"rights":["CC BY-NC"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1773/40636","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Dumitriu, Ioana","Hoffman, Christopher"]},{"key":"dc:creator","label":"Author","values":["Brito, Gerandy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-10-26T20:51:45Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-10-26T20:51:45Z"]},{"key":"dc:date.issued","label":"Date","values":["2017-10-26"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["community detection","regular graphs","spectral analysis","spectral gap","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["CC BY-NC"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["Brito_washington_0250E_17725.pdf"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1773/40636"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph.D.)--University of Washington, 2017-08"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Spectral analysis in bipartite biregular graphs and community detection"]}]}],"canonical_facts":{"dc:contributor.advisor":["Dumitriu, Ioana","Hoffman, Christopher"],"dc:creator":["Brito, Gerandy"],"dc:date.accessioned":["2017-10-26T20:51:45Z"],"dc:date.available":["2017-10-26T20:51:45Z"],"dc:date.issued":["2017-10-26"],"dc:description":["Thesis (Ph.D.)--University of Washington, 2017-08"],"dc:description.abstract":["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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["Brito_washington_0250E_17725.pdf"],"dc:identifier.uri":["http://hdl.handle.net/1773/40636"],"dc:language.iso":["en_US"],"dc:rights":["CC BY-NC"],"dc:subject":["community detection","regular graphs","spectral analysis","spectral gap","Mathematics"],"dc:title":["Spectral analysis in bipartite biregular graphs and community detection"],"dc:type":["Thesis"]},"updated_at":"2026-07-24T05:58:01Z"}