Browsing by Subject "spectral expansion"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item An Empirical Study of Expander Graphs and Graph Expansion(2016-01-01) Lotts, Mark Allen; Chang, Richard; Computer Science and Electrical Engineering; Computer ScienceExpander 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.