Search
Nonlinear Laplacian for digraphs and its applications to network analysis
Yoshida Y.  WSDM 2016 (Proceedings of the 9th ACM International Conference on Web Search and Data Mining, San Francisco, CA,  Feb 22-25, 2016) 483-492. 2016. Type: Proceedings
 Date Reviewed: Jul 28 2016
 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. Reviewer:  Svetlana Segarceanu Review #: CR144640 (1611-0825)
 Would you recommend this review? yes no
 Other reviews under "Graphs And Networks": Date Scale free interval graphsMiyoshi N., Shigezumi T., Uehara R., Watanabe O.  Theoretical Computer Science 410(45): 4588-4600, 2009. Type: Article Jan 29 2010 Detachments of complete graphsEdwards K.  Combinatorics, Probability and Computing 14(3): 275-310, 2005. Type: Article May 9 2007 GXL: a graph-based standard exchange format for reengineeringHolt R., Schürr A., Sim S., Winter A.  Science of Computer Programming 60(2): 149-170, 2006. Type: Article Apr 27 2007 more...

E-Mail This Printer-Friendly
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy