An Empirical Study of Expander Graphs and Graph Expansion

Simple item page
dc.contributor.advisorChang, Richard
dc.contributor.authorLotts, Mark Allen
dc.contributor.departmentComputer Science and Electrical Engineering
dc.contributor.programComputer Science
dc.date.accessioned2019-10-11T13:42:51Z
dc.date.available2019-10-11T13:42:51Z
dc.date.issued2016-01-01
dc.description.abstractExpander graphs are commonly studied objects in computer science and mathematics that are found in the proofs of many important theorems. The vast majority of these theoretical uses of expanders rely on probabilistic statements of existence and do not grapple with the challenge of creating expander graphs or validating their expansion properties. In this paper, we will define expander graphs and describe different ways their expansion can be measured. We will discuss applications of expander graphs and provide empirical evidence of how they can be used in practice. We will also outline the difficulties of computing exact expansion rates and the hardness of estimating these rates, relating these problems to well-known results and conjectures in complexity theory. Using our own implementation of graph creation and verification algorithms, we will gain an empirical understanding of expander graphs, utilizing high-performance computing resources and repurposing well-known statistical methods to analyze expansion. We will show that, given an arbitrary graph, its potential to be used as an expander can be measured and bounded by employing community detection algorithms that seek to maximize modularity.
dc.genretheses
dc.identifierdoi:10.13016/m2xipz-dold
dc.identifier.other11454
dc.identifier.urihttp://hdl.handle.net/11603/15484
dc.languageen
dc.relation.isAvailableAtThe University of Maryland, Baltimore County (UMBC)
dc.relation.ispartofUMBC Computer Science and Electrical Engineering Department Collection
dc.relation.ispartofUMBC Theses and Dissertations Collection
dc.relation.ispartofUMBC Graduate School Collection
dc.relation.ispartofUMBC Student Collection
dc.rightsThis item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu
dc.sourceOriginal File Name: Lotts_umbc_0434M_11454.pdf
dc.subjectcommunity detection
dc.subjectedge expansion
dc.subjectexpander graph
dc.subjectgraph expansion
dc.subjectmodularity
dc.subjectspectral expansion
dc.titleAn Empirical Study of Expander Graphs and Graph Expansion
dc.typeText
dcterms.accessRightsDistribution Rights granted to UMBC by the author.

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Lotts_umbc_0434M_11454.pdf
Size:
686.85 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
LottsM_Empirical_Open.pdf
Size:
50.32 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

UMBC Theses and Dissertations