RANDOM WALKS, CONDUCTANCE, AND RESISTANCE FOR THE CONNECTION GRAPH LAPLACIAN

被引：0

作者：

Cloninger, Alexander ^{[1
,2
]}

Mishne, Gal ^{[2
]}

Oslandsbotn, Andreas ^{[3
]}

Robertson, Sawyer J. ^{[1
,2
]}

Wan, Zhengchao ^{[2
]}

Wang, Yusu ^{[2
]}

机构：

[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA

[2] Univ Calif San Diego, Hahhoglu Data Sci Inst, La Jolla, CA 92093 USA

[3] Univ Oslo, Dept Informat, Oslo, Norway

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2024年 / 45卷 / 03期

关键词：

effective resistance; connection Laplacian; random walks; Dirichlet problem; Poisson problem; ALGORITHMS; TOPOLOGY;

D O I：

10.1137/23M1595400

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate the concept of effective resistance in connection graphs, expanding its traditional application from undirected graphs. We propose a robust definition of effective resistance in connection graphs by focusing on the duality of Dirichlet-type and Poisson-type problems on connection graphs. Additionally, we delve into random walks, taking into account both node transitions and vector rotations. This approach introduces novel concepts of effective conductance and resistance matrices for connection graphs, capturing mean rotation matrices corresponding to random walk transitions. Thereby, it provides new theoretical insights for network analysis and optimization.

引用

页码：1541 / 1572

页数：32

共 50 条

[1] RANDOM WALKS ON THE RANDOM GRAPH
Berestycki, Nathanael
Lubetzky, Eyal
Peres, Yuval
Sly, Allan
ANNALS OF PROBABILITY, 2018, 46 (01) : 456 - 490
[2] Restricted random walks on a graph
F. Y. Wu
H. Kunz
Annals of Combinatorics, 1999, 3 (2-4) : 475 - 481
[3] Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian
Schaub, Michael T.
Benson, Austin R.
Horn, Paul
Lippner, Gabor
Jadbabaie, Ali
SIAM REVIEW, 2020, 62 (02) : 353 - 391
[4] Reweighted Random Walks for Graph Matching
Cho, Minsu
Lee, Jungmin
Lee, Kyoung Mu
COMPUTER VISION-ECCV 2010, PT V, 2010, 6315 : 492 - 505
[5] Random walks on a finite graph with congestion points
Kang, MH
APPLIED MATHEMATICS AND COMPUTATION, 2004, 153 (02) : 601 - 610
[6] Resistance distance in graphs and random walks
Palacios, JL
INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2001, 81 (01) : 29 - 33
[7] Visual Tracking via Random Walks on Graph Model
Li, Xiaoli
Han, Zhifeng
Wang, Lijun
Lu, Huchuan
IEEE TRANSACTIONS ON CYBERNETICS, 2016, 46 (09) : 2144 - 2155
[8] Exact and approximate graph matching using random walks
Gori, M
Maggini, M
Sarti, L
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27 (07) : 1100 - 1111
[9] CURVATURE AND HIGHER ORDER BUSER INEQUALITIES FOR THE GRAPH CONNECTION LAPLACIAN
Liu, Shiping
Muench, Florentin
Peyerimhoff, Norbert
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (01) : 257 - 305
[10] Random walks and the effective resistance sum rules
Chen, Haiyan
DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) : 1691 - 1700

← 1 2 3 4 5 →