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 条

[21] Solving convex programs by random walks
Bertsimas, D
Vempala, S
JOURNAL OF THE ACM, 2004, 51 (04) : 540 - 556
[22] Simulation of distribution of random walks on a lattice
Jiang, J. G.
Huang, Y. N.
COMPUTER PHYSICS COMMUNICATIONS, 2009, 180 (02) : 177 - 179
[23] Tie knots, random walks and topology
Fink, TMA
Mao, Y
PHYSICA A, 2000, 276 (1-2): : 109 - 121
[24] RANDOM WALKS WITH RESTARTS FOR GRAPH-BASED CLASSIFICATION: TELEPORTATION TUNING AND SAMPLING DESIGN
Berberidis, Dimitris
Nikolakopoulos, Athanasios N.
Giannakis, Georgios B.
2018 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2018, : 2811 - 2815
[25] DEeP Random Walks
Moghaddam, Mandana Javanshir
Eslami, Abouzar
Navab, Nassir
MEDICAL IMAGING 2013: IMAGE PROCESSING, 2013, 8669
[26] ON THE RANGE OF RANDOM WALKS IN RANDOM ENVIRONMENT
ZHOU XIANYIN(Department of Mathematics
Chinese Annals of Mathematics, 1995, (01) : 131 - 138
[27] On the meeting of random walks on random DFA
Quattropani, Matteo
Sau, Federico
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2023, 166
[28] Disordered Random Walks
Pato, Mauricio P.
BRAZILIAN JOURNAL OF PHYSICS, 2021, 51 (02) : 238 - 243
[29] Random walks on random simple graphs
Hildebrand, M
RANDOM STRUCTURES & ALGORITHMS, 1996, 8 (04) : 301 - 318
[30] Bootstrap random walks
Collevecchio, Andrea
Hamza, Kais
Shi, Meng
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2016, 126 (06) : 1744 - 1760

← 1 2 3 4 5 →