Abstract by Joseph Drapeau
Necessary and Sufficient Conditions for Graph
The spectrum of real-world networks is of high interest because of its relationship to network dynamics and structure. We introduce a new method for analyzing networks by investigating the relationship between its symmetries, more generally equitable partitions, and spectrum. This is done by using Discrete Fourier Transforms to create an object called a Graph Fourier Transform (GFT). We prove that a graph has an equitable partition if and only if the GFT decomposes the adjacency matrix of the graph into strictly smaller matrices. Hence, the collective eigenvalues of these smaller matrices are the same as the eigenvalues of the original adjacency matrix. Given many real-world networks are highly symmetrical, our method shows promise since it utilizes a network’s symmetries.