Normalized graph Laplacians for directed graphs

DOI10.1016/J.LAA.2012.01.020zbMATH Open1241.05066arXiv1107.4847OpenAlexW2963180298MaRDI QIDQ414701FDOQ414701

Frank Bauer

Publication date: 11 May 2012

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We consider the normalized Laplace operator for directed graphs with positive and negative edge weights. This generalization of the normalized Laplace operator for undirected graphs is used to characterize directed acyclic graphs. Moreover, we identify certain structural properties of the underlying graph with extremal eigenvalues of the normalized Laplace operator. We prove comparison theorems that establish a relationship between the eigenvalues of directed graphs and certain undirected graphs. This relationship is used to derive eigenvalue estimates for directed graphs. Finally we introduce the concept of neighborhood graphs for directed graphs and use it to obtain further eigenvalue estimates.

Full work available at URL: https://arxiv.org/abs/1107.4847

zbMATH Keywords

eigenvaluesdirected graphsdirected acyclic graphsneighborhood graphnormalized graph Laplace operator

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial matrix theory
• Inequalities: theory of majorization and its applications
• Geometric bounds for eigenvalues of Markov chains
• Laplacians and the Cheeger inequality for directed graphs
• A Recurring Theorem on Determinants
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• On bounds of extremal eigenvalues of irreducible and \(m\)-reducible matrices
• Synchronization in discrete-time networks with general pairwise coupling
• Bounds for eigenvalues of certain stochastic matrices
• Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
• On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs

Cited In (25)

• Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
• Hermitian normalized Laplacian matrix for directed networks
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• On the restricted numerical range of the Laplacian matrix for digraphs
• Deep learning and geometric deep learning: An introduction for mathematicians and physicists
• Hypergraph Laplace operators for chemical reaction networks
• Maximizing the smallest eigenvalue of a symmetric matrix: a submodular optimization approach
• Title not available (Why is that?)
• Diffusion operator and spectral analysis for directed hypergraph Laplacian
• On eigenvalues of Laplacian matrix for a class of directed signed graphs
• Title not available (Why is that?)
• Local phase synchronization and clustering for the delayed phase-coupled oscillators with plastic coupling
• The Geometric Meaning of Curvature: Local and Nonlocal Aspects of Ricci Curvature
• Generalized Ricci curvature and the geometry of graphs
• Geometric and spectral analysis on weighted digraphs
• Distributed point-to-point iterative learning control for multi-agent systems with quantization
• Spectral bounds of directed Cayley graphs of finite groups
• Spectral theory of the non-backtracking Laplacian for graphs
• On the graph Laplacian and the rankability of data
• Geometric and spectral properties of directed graphs under a lower Ricci curvature bound
• Spectral analysis of non-Hermitian matrices and directed graphs
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• The consensus problem in networks with transmission delays
• Kernels of directed graph Laplacians
• Distance matrix of weighted cactoid-type digraphs

This page was built for publication: Normalized graph Laplacians for directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414701)