Normalized graph Laplacians for directed graphs

被引：46
作者：
Bauer, Frank [1 ]
机构：
[1] Max Planck Inst Math Sci, D-04103 Leipzig, Germany
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2012年 / 436卷 / 11期
关键词：
Directed graphs; Normalized graph Laplace operator; Eigenvalues; Directed acyclic graphs; Neighborhood graph; EIGENVALUES; MATRICES; BOUNDS;
D O I：
10.1016/j.laa.2012.01.020
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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. (C) 2012 Elsevier Inc. All rights reserved.
引用
收藏
页码：4193 / 4222
页数：30
相关论文
共 50 条
[31]   GRAPH LIMITS AND SPECTRAL EXTREMAL PROBLEMS FOR GRAPHS* [J].
Liu, Lele .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (01) :590-608
[32]   A spectral graph convolution for signed directed graphs via magnetic Laplacian [J].
Ko, Taewook ;
Choi, Yoonhyuk ;
Kim, Chong -Kwon .
NEURAL NETWORKS, 2023, 164 :562-574
[33]   Deformed Laplacians and spectral ranking in directed networks [J].
Fanuel, M. ;
Suykens, J. A. K. .
APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2019, 47 (02) :397-422
[34]   The normalized Laplacian polynomial of rooted product of graphs [J].
Heydari, Abbas .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (04)
[35]   Extremal normalized Laplacian spectral radii of graphs [J].
Sun, Shaowei ;
Chen, Mengsi .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 679 :261-274
[36]   Normalized distance Laplacian matrices for signed graphs [J].
Roy, Roshni T. ;
Germinal, K. A. ;
Hameed, Shahul K. .
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2023, 8 (03) :445-456
[37]   Spectral approximation of Gaussian random graph Laplacians and applications to pattern recognition [J].
Airani, Rajeev ;
Kamble, Sachin .
PATTERN RECOGNITION, 2025, 164
[38]   On Lossy Compression of Directed Graphs [J].
Bustin, Ronit ;
Shayevitz, Ofer .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (04) :2101-2122
[39]   BLADE: Biased Neighborhood Sampling based Graph Neural Network for Directed Graphs [J].
Virinchi, Srinivas ;
Saladi, Anoop .
PROCEEDINGS OF THE SIXTEENTH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING, WSDM 2023, VOL 1, 2023, :42-50
[40]   On the normalized spectrum of threshold graphs [J].
Banerjee, Anirban ;
Mehatari, Ranjit .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 530 :288-304
12345