Kron Reduction and Effective Resistance of Directed Graphs
Kron Reduction and Effective Resistance of Directed Graphs
复制标题
有向图的 Kron 约简和有效阻力
DOI：
10.1137/22m1480823
复制
发表时间：
2023
影响因子：
1.5
通讯作者：
Sato Kazuhiro
中科院分区：
文献类型：
--
作者：
Sugiyama Tomohiro;Sato Kazuhiro
在网络理论中，有效电阻的概念是图上的距离度量，它将全局网络属性与节点之间的单个连接联系起来。此外，Kron约简方法是减少或消除所需节点的标准工具，它保留了原始图的互连结构和有效电阻。虽然这两个图论概念源于无向图上的电网络，但它们在其他许多领域也有许多应用。在这项研究中，我们提出了一个推广的有向图的Kron约化。此外，我们证明了这种约简方法保持了原图的结构，如强连通性或重量平衡。此外，我们推广的有效电阻的有向图使用马尔可夫链理论，这是不变的Kron减少。虽然我们的建议的有效电阻是不对称的，我们证明了它导致两个新的图度量一般强连通有向图。特别是，有效电阻捕获的通勤和覆盖时间强连接的重量平衡有向图。最后，我们比较我们的方法与现有的方法，并在随机情况下的命中概率度量和有效阻力。此外，我们证明了在双随机情况下的有效阻力是相同的阻力距离在遍历马尔可夫链。
In network theory, the concept of effective resistance is a distance measure on a graph that relates the global network properties to individual connections between nodes. In addition, the Kron reduction method is a standard tool for reducing or eliminating the desired nodes, which preserves the interconnection structure and the effective resistance of the original graph. Although these two graph-theoretic concepts stem from the electric network on an undirected graph, they also have a number of applications throughout a wide variety of other fields. In this study, we propose a generalization of a Kron reduction for directed graphs. Furthermore, we prove that this reduction method preserves the structure of the original graphs, such as the strong connectivity or weight balance. In addition, we generalize the effective resistance to a directed graph using Markov chain theory, which is invariant under a Kron reduction. Although the effective resistance of our proposal is asymmetric, we prove that it induces two novel graph metrics in general strongly connected directed graphs. In particular, the effective resistance captures the commute and covering times for strongly connected weight balanced directed graphs. Finally, we compare our method with existing approaches and relate the hitting probability metrics and effective resistance in a stochastic case. In addition, we show that the effective resistance in a doubly stochastic case is the same as the resistance distance in an ergodic Markov chain.
登录
查看更多内容
关于拉普拉斯伪逆的性质
DOI：
10.1109/cdc45484.2021.9683525
发表时间：
2021
期刊：
2021 60th IEEE Conference on Decision and Control (CDC)
影响因子：
--
作者：
Angela Fontan;C. Altafini
通讯作者：
C. Altafini
统计物理中的离散数学 - 入门讲座
DOI：
10.1007/978-3-8348-9329-1
发表时间：
2009
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl
有向图有效阻力的新概念——第一部分：定义和性质
影响因子：
6.8
作者：
G. F. Young;L. Scardovi;Naomi Ehrich Leonard
通讯作者：
Naomi Ehrich Leonard
关于矩阵方程 Ax = λBx
影响因子：
1.3
作者：
I. Erdelyi
通讯作者：
I. Erdelyi
影响因子：
1.5
作者：
Katherine E. Fitch
通讯作者：
Katherine E. Fitch