Eigenvalues of directed graphs through cyclic structures

Networks and graphs are often studied using the eigenvalues of their adjacency matrices, an powerful mathematical tool with applications on fields as diverse as systems engineering, ecology, machine learning and neuroscience. As in those applications the exact graph structure is not known, we usually resort to random graphs to obtain properties of eigenvalues from known structural features. However, this theory is not intuitive and only few results are known. In this paper we tackle this problem by studying how cycles in the graph relate to eigenvalues. We start by deriving a simple relation between eigenvalues and cycle weights, and use it to study two structural features: The spectral radius of circulant graphs and the eigenvalue distribution of random graphs with motifs. During this study we empirically uncover to surprising phenomena. First, circulant directed networks have eigenvalues distributed in concentric circles around the origin. And second, the eigenvalues of a network with abundance of short cycles are confined to the interior of a k-ellipse, where k is the length of the cycles. Our approach offers an intuitive way to study eigenvalues on graphs and in the process reveals surprising connections between random matrix theory and classical planar geometry.