Random Walks and Electrical Networks
Random Walks and Electrical Networks
复制标题
DOI：
10.1090/stml/002/09
复制
发表时间：
1984-12
期刊：
影响因子：
--
通讯作者：
Peter G. Doyle;J. L. Snell
中科院分区：
文献类型：
--
作者：
Peter G. Doyle;J. L. Snell
We present an intriguing connection between random walks and electricity flow in networks. This phenomena has been known for several years, going back to the nineteenth century. A comprehensive manuscript on this connection is by Doyle and Snell, available online. Our coverage of this connection will closely follow Lovasz’s survey on random walks. We will introduce the notion of effective resistance between two nodes in a graph, which has found several applications recently, including in graph sparsification. More recently, the connection between electrical flows and random walks has been instrumental in obtaining near-linear time algorithms for network flows — considered among the breakthrough results in the field.
