论文标题
KRON降低和有效图的有效电阻
Kron Reduction and Effective Resistance of Directed Graphs
论文作者
论文摘要
在网络理论中，有效电阻的概念是图表上的距离度量，将全局网络属性与节点之间的单个连接相关联。另外，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.
