Spectral Algorithms for Verifying Generative Properties in Large, Asymmetric Graphs

Abstract

In this research spectral methods were developed to quantify the generators of large connected asymmetrical graphs (i.e. the connectivity, clustering and score distributions). The connectivity was called out using the eigenvalue distribution and eigenvector properties from the adjacency matrix, laplacian matrix, and incidence matrix; while quantifying the structure of the network, identifying important network nodes and their communities and calculating the variance of the network using a generative process. The implementation of the algorithms were done separately with different programming languages (i.e. python (NetworkX, NumPy, SciPy), MATLAB, R); all took advantage of sparse matrices providing a lot of efficiency when working with very large datasets. The experiments performed using the algorithms measured how accurately the algorithms were able to reproduce the behaviour and properties of real-world networks using performance benchmarks as a comparison. The results provide significant advances to spectral graph theory and have provided a significant amount of capability towards the robust analysis of directed networks and for the development of resilience models and community detection.