KONECT
KONECT > Plots > Complex eigenvalues of the asymmetric adjacency matrix

Complex eigenvalues of the asymmetric adjacency matrix

The adjacency matrix of an undirected graph is symmetric and therefore its eigenvalues are real. For directed graphs however, the adjacency matrix $$\mathbf A$$ is asymmetric, and in the general case its eigenvalues are complex. We thus plot, for directed graphs, the top-$$k$$ complex eigenvalues by absolute value of the adjacency matrix $$\mathbf A$$.

Three properties can be read off the complex eigenvalues: whether a graph is nearly acyclic, whether a graph is nearly symmetric, and whether a graph is nearly bipartite. If a directed graph is acyclic, its adjacency matrix is nilpotent and therefore all its eigenvalues are zero. The complex eigenvalue plot can therefore serve as a test for networks that are nearly acyclic: the smaller the absolute value of the complex eigenvalues of a directed graph, the nearer it is to being acyclic. When a directed network is symmetric, i.e., all directed edges come in pairs connecting two nodes in opposite direction, then the adjacency matrix $$\mathbf A$$ is symmetric and therefore all its eigenvalues are complex. Thus, a nearly symmetric directed network has complex eigenvalues that are near the real line. Finally, the eigenvalues of a bipartite graph are symmetric around the imaginary axis. In other words, if $$a+bi$$ is an eigenvalue, then so is $$-a+bi$$ when the graph is bipartite. Thus, the amount of symmetric along the imaginary axis is an indicator for bipartivity. Note that bipartivity here takes into account edge directions: There must be two groups such that all (or most) directed edges go from the first group to second.