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 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.

arXiv comment15 pages, 12 figures

References in corpus (17)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Stochastic blockmodels and community structure in networks
• Spectral redemption: clustering sparse networks
• Mapping change in large networks
• Clustering and Community Detection in Directed Networks: A Survey
• Patterns of link reciprocity in directed networks
• Graph spectra and the detectability of community structure in networks
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices
• Cavity approach to the spectral density of non-Hermitian sparse matrices
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Subsampling bootstrap of count features of networks
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Unperturbed: spectral analysis beyond Davis-Kahan
• Linear stability analysis for large dynamical systems on directed random graphs
• Eigenvector dynamics under perturbation of modular networks