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 条
[41]   Distance between the normalized Laplacian spectra of two graphs [J].
Das, Kinkar Ch. ;
Sun, Shaowei .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 530 :305-321
[42]   Graphs whose normalized Laplacian has three eigenvalues [J].
van Dam, E. R. ;
Omidi, G. R. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (10) :2560-2569
[43]   General Cheeger inequalities for p-Laplacians on graphs [J].
Keller, Matthias ;
Mugnolo, Delio .
NONLINEAR ANALYSIS-THEORY METHODS & APPLICATIONS, 2016, 147 :80-95
[44]   LIPSCHITZ REGULARITY OF GRAPH LAPLACIANS ON RANDOM DATA CLOUDS [J].
Calder, Jeff ;
Trillos, Nicolas Garcia ;
Lewicka, Marta .
SIAM JOURNAL ON MATHEMATICAL ANALYSIS, 2022, 54 (01) :1169-1222
[45]   A POSTERIORI ERROR ESTIMATES FOR MULTILEVEL METHODS FOR GRAPH LAPLACIANS [J].
Hu, Xiaozhe ;
Wu, Kaiyi ;
Zikatanov, Ludmil T. .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2021, 43 (05) :S727-S742
[46]   Intelligent fault diagnosis for rolling bearings based on graph shift regularization with directed graphs [J].
Gao, Yiyuan ;
Yu, Dejie .
ADVANCED ENGINEERING INFORMATICS, 2021, 47
[47]   On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs [J].
Wu, CW .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 402 :207-227
[48]   Graphs with the same determinant as a complete graph [J].
Olesky, DD ;
van den Driessche, P ;
Verner, JH .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2000, 312 (1-3) :191-195
[49]   On the spectrum of the normalized Laplacian for signed graphs: Interlacing, contraction, and replication [J].
Atay, Fatihcan M. ;
Tuncel, Hande .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 442 :165-177
[50]   Toughness and normalized Laplacian eigenvalues of graphs [J].
Huang, Xueyi ;
Das, Kinkar Chandra ;
Zhu, Shunlai .
APPLIED MATHEMATICS AND COMPUTATION, 2022, 425
12345