Nonlinear Laplacian for digraphs and its applications to network analysis

摘要

This paper relates to spectral graph theory and more specifically concerns the case of digraphs, directed graphs. It proposes an alternative framework to existing digraph approaches, such as Chung's, or the Diplacian, relying on stationary probabilities, by manipulating instead characteristics of the graph's configuration. The purpose of the work is to reproduce and demonstrate the properties of undirected graphs concerning matrices associated to the graph, such as the adjacency or Laplacian matrices, their eigenvalues, and eigenvectors, in order to make the theory pertinent and consistent. The most important undertaking is to prove the fundamental Cheeger's inequality, essential to an accomplished spectral graph theory, which relates the spectral properties of the associated matrices to the geometrical properties of the graph.