Nonlinear Laplacian for Digraphs and its Applications to Network Analysis

Reviewer: Svetlana Segarceanu

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. The task stands to define a suitable spectral framework for directed graphs, namely to infer concepts like the Laplacian matrix, eigenvalue and eigenvector, Rayleigh quotient of a Markov operator, and in and out conductance. The first part is introductory, where some examples stress the utility of directed graphs and requisites for investigating and formalizing this topic. An interesting application is the directed graph-based clustering approach. The next section provides a highly formalized theoretical framework for directed graphs. The Laplacian and the normalized Laplacian are defined locally as the Laplacian of an induced undirected graph on the vertex set. Therefore, the Laplacian is nonlinear and does not agree with the traditional eigenvalues and eigenvector definitions, but these notions are redefined to generalize to the traditional one. The estimated Rayleigh quotient depends upon the in and out degrees of the graph. A positive of the presentation is the revision of corresponding terminology, concepts, and steps related to undirected graphs. An important part of the presentation concerns the practical matter of commuting eigenvalues and eigenvectors for a convenient implementation. To settle this issue, the authors use heat equation simulation applied as a numerical method for differential equations. The last part of the paper investigates the structure of a number of networks processed using Chang's and the present representations, and analyzes several aspects of spectral properties, expansion, and adjacency matrices. This part is accompanied by technical implementation details and expressive graphical illustrations of the output. The work is noteworthy for its endeavor to place directed graph theory into a general pattern, for its concision and clarity, and for the originality of the solution and high-level formalization. Online Computing Reviews Service