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
  Featured Reviewer  
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
Complete inverted files for efficient text retrieval and analysis
Blumer A., Blumer J., Haussler D., McConnell R., Ehrenfeucht A. Journal of the ACM 34(3): 578-595, 1987. Type: Article
Oct 1 1988
Deformable spanners and applications
Gao J., Guibas L., Nguyen A.  Computational geometry (Proceedings of the 20th Annual Symposium on Computational Geometry, Brooklyn, New York, USA, Jun 8-11, 2004)190-199, 2004. Type: Proceedings
Sep 13 2004
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Henzinger M., King V. Journal of the ACM 46(4): 502-516, 1999. Type: Article
Mar 1 2000

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy