Spectral theory of the non-backtracking Laplacian for graphs

被引：4
|
作者：
Jost, Juergen [1 ,2 ]
Mulas, Raffaella [1 ,3 ]
Torres, Leo [1 ]
机构：
[1] Max Planck Inst Math Sci, Leipzig, Germany
[2] Santa Fe Inst Sci Complex, Santa Fe, NM USA
[3] Vrije Univ Amsterdam, Amsterdam, Netherlands
来源：
DISCRETE MATHEMATICS | 2023年 / 346卷 / 10期
关键词：
Non-backtracking random walks; Spectral graph theory; Non-backtracking matrix; Laplacian eigenvalues; CENTRALITY;
D O I：
10.1016/j.disc.2023.113536
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We introduce a non-backtracking Laplace operator for graphs and we investigate its spectral properties. With the use of both theoretical and computational techniques, we show that the spectrum of this operator captures several structural properties of the graph in a more precise way than the classical operators that have been studied so far in the literature, including the non-backtracking matrix. & COPY; 2023 Elsevier B.V. All rights reserved.
引用
收藏
页数：19
相关论文
共 50 条
  • [1] ON THE NON-BACKTRACKING SPECTRAL RADIUS OF GRAPHS
    LIN, H. O. N. G. Y. I. N. G.
    ZHOU, Bo
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2022, 38 : 254 - 265
  • [2] There is no going back: Properties of the non-backtracking Laplacian
    Mulas, Raffaella
    Zhang, Dong
    Zucal, Giulio
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 680 : 341 - 370
  • [3] Minimizing Spectral Radius of Non-Backtracking Matrix by Edge Removal
    Zhang, Zuobai
    Zhang, Zhongzhi
    Chen, Guanrong
    PROCEEDINGS OF THE 30TH ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT, CIKM 2021, 2021, : 2657 - 2667
  • [4] Non-backtracking PageRank
    Arrigo, Francesca
    Higham, Desmond J.
    Noferini, Vanni
    JOURNAL OF SCIENTIFIC COMPUTING, 2019, 80 (03) : 1419 - 1437
  • [5] Some spectral properties of the non-backtracking matrix of a graph
    Glover, Cory
    Kempton, Mark
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 618 : 37 - 57
  • [6] Non-backtracking PageRank
    Francesca Arrigo
    Desmond J. Higham
    Vanni Noferini
    Journal of Scientific Computing, 2019, 80 : 1419 - 1437
  • [7] Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
    Bordenave, Charles
    Lelarge, Marc
    Massoulie, Laurent
    2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, : 1347 - 1357
  • [8] NON-BACKTRACKING ALTERNATING WALKS
    Arrigo, Francesca
    Higham, Desmond J.
    Noferini, Vanni
    SIAM JOURNAL ON APPLIED MATHEMATICS, 2019, 79 (03) : 781 - 801
  • [9] Non-backtracking random walks mix faster
    Alon, Noga
    Benjamini, Itai
    Lubetzky, Eyal
    Sodin, Sasha
    COMMUNICATIONS IN CONTEMPORARY MATHEMATICS, 2007, 9 (04) : 585 - 603
  • [10] Length Spectrum Theory, Non-backtracking Cycles, and Two Graph Analysis Tasks
    Eliassi-Rad, Tina
    PROCEEDINGS OF THE 2ND ACM SIGMOD JOINT INTERNATIONAL WORKSHOP ON GRAPH DATA MANAGEMENT EXPERIENCES & SYSTEMS (GRADES) AND NETWORK DATA ANALYTICS (NDA) 2019, 2019,
12345