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 条

[41] Random Walks and Bisections in Random Circulant Graphs
Mans, Bernard
Shparlinski, Igor E.
LATIN 2012: THEORETICAL INFORMATICS, 2012, 7256 : 542 - 555
[42] On the speed of Random Walks among Random Conductances
Berger, Noam
Salvi, Michele
ALEA-LATIN AMERICAN JOURNAL OF PROBABILITY AND MATHEMATICAL STATISTICS, 2013, 10 (02): : 1063 - 1083
[43] Collisions of random walks in dynamic random environments
Halberstam, Noah
Hutchcroft, Tom
ELECTRONIC JOURNAL OF PROBABILITY, 2022, 27
[44] MULTIPLE RANDOM WALKS IN RANDOM REGULAR GRAPHS
Cooper, Colin
Frieze, Alan
Radzik, Tomasz
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) : 1738 - 1761
[45] Random walks on a fractal solid
Kozak, JJ
JOURNAL OF STATISTICAL PHYSICS, 2000, 101 (1-2) : 405 - 414
[46] Counting trees with random walks
Iacobelli, Giulio
Figueiredo, Daniel R.
Barbosa, Valmir C.
EXPOSITIONES MATHEMATICAE, 2019, 37 (01) : 96 - 102
[47] Distributed Computation of Sparse Cuts via Random Walks
Das Sarma, Atish
Molla, Anisur Rahaman
Pandurangan, Gopal
PROCEEDINGS OF THE 16TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, 2015,
[48] Evolutionary Image Transition and Painting Using Random Walks
Neumann, Aneta
Alexander, Bradley
Neumann, Frank
EVOLUTIONARY COMPUTATION, 2020, 28 (04) : 643 - 675
[49] Return of Fibonacci random walks
Neunhaeuserer, Joerg
STATISTICS & PROBABILITY LETTERS, 2017, 121 : 51 - 53
[50] Random Walks on the Folded Hypercube
Chen, Hong
Li, Xiaoyan
Lin, Cheng-Kuan
JOURNAL OF INTERNET TECHNOLOGY, 2019, 20 (06): : 1987 - 1994

← 1 2 3 4 5 →