Authors: Peter Seely, Joseph Henderson, Benjamin Webb
Mentors: Benjamin Webb
Insitution: Brigham Young University
A longstanding result in spectral graph theory is that some of the eigenvalues of a network can be obtained by identifying equitable partitions within the graph's structure. We have discovered that the remaining eigenvalues can be recovered using theoretical constructs which we call Local Equitable Partitions (LEPs). We have developed a procedure to find LEPs in a way that allows us to efficiently compute a graph's spectrum using this theory. Our procedure finds LEPs by identifying patterns in the coarsest equitable partition of a graph. We utilize these LEPs in a novel algorithm for computing the spectrum of a graph. Under certain mild assumptions on the equitable partition, we can find eigenvalues of a graph faster using this method when compared to the standard method. This is potentially useful as many real-world data sets have nontrivial equitable partitions.