- The Eigenspectra of Random Graphs: A Deterministic Approach via Edge Removal
Awards
Author(s):
Category:
Institution:
Region:
Winner Category:
Year:
Abstract:
- Random graphs provide important models for a range of social, technological, and biological systems. The structure of these graphs is represented by an adjacency matrix A, where Aij = 1 whenever node i and j are connected, and Aij = 0 otherwise. The eigenvalues of these matrices are important in determining the behaviors of networked systems, from the transition to chaos in random neural networks, to epidemic thresholds for infections propagating through human populations. While the distribution of the eigenvalues of random n×n matrices as n→ ∞ is well understood, not much is known about the eigenvalues of random n×n matrices at finite scale. Here, we present deterministic approaches to analyze the eigenspectra and investigate the connections between regular graphs and random graphs via patterned edge removal. When viewed in a sequential manner, the effects of systematic edge removal exhibit surprising regularity. This thesis introduces the problem along with our approaches and presents numerical investigations for n= 3,4,5 and n= 10. We express edge removal as matrix multiplication, find an analytical expression for the coefficients of the characteristic polynomial in terms of the matrix entries, and use simultaneous diagonalization in order to study this problem. Furthermore, we prove that the eigenspectrum of the complete graph with one edge removed is the same regardless of which edge we choose to remove. Finally, our numerical investigation suggests that when two edges are removed, there are four unique eigenspectra formed, including the trivial eigenspectrum, regardless of n.
Attached Documents: