Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
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)
Bookmark and Share
Graphs And Networks (E.1 ... )
Graph Algorithms (G.2.2 ... )
Markov Processes (G.3 ... )
Would you recommend this review?
Other reviews under "Graphs And Networks": Date
Scale free interval graphs
Miyoshi N., Shigezumi T., Uehara R., Watanabe O.  Theoretical Computer Science 410(45): 4588-4600, 2009. Type: Article
Jan 29 2010
Detachments of complete graphs
Edwards K.  Combinatorics, Probability and Computing 14(3): 275-310, 2005. Type: Article
May 9 2007
GXL: a graph-based standard exchange format for reengineering
Holt R., Schürr A., Sim S., Winter A.  Science of Computer Programming 60(2): 149-170, 2006. Type: Article
Apr 27 2007

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