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.