Contribution of directedness in graph spectra

Abstract

In graph analyses, directed edges are often approximated to undirected ones so that the adjacency matrices may be symmetric. However, such a simplification has not been thoroughly verified. In this study, we investigate how directedness affects the graph spectra by introducing random directization, which is an opposite operation of neglecting edge directions. We analytically reveal that uniformly random directization typically conserves the relative spectral structure of the adjacency matrix in the perturbative regime. The result of random directization implies that the spectrum of the adjacency matrix can be conserved after the directedness is ignored.