|
 ABSTRACT
View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
David J. Aldous. Random walks on large graphs, 1988. Unpublished Monograph, Berkeley.
|
| |
2
|
R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovgsz, and C. Rackoff. Random walks, universM traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, p~ges 218-223, San Juan, Puerto Rico, October 1979.
|
| |
3
|
|
 |
4
|
A. Borodin , W. L. Ruzzo , M. Tompa, Lower bounds on the length of universal traversal sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.562-573, May 14-17, 1989, Seattle, Washington, United States
[doi> 10.1145/73007.73061]
|
| |
5
|
A. Z. Broder and A. R. Karlin. Bounds oIt covering times. In 29th Annual Symposium o~ Foundations of Computer Science, pages 479-- 487, White Plains, NY, October 1988.
|
| |
6
|
J.T. Cox. Coalescing random walks and vote:r model consensus times on the torus, 1987. unpublished manuscript, CorneU.
|
| |
7
|
Peter G. Doyle and J. Laurie Snell. Rando~ Walks and Electrical Networks. The Mathematical Association of America, 1984.
|
| |
8
|
J. N. Franklin. Matrix Theory. Prentice-Hall, 1968.
|
| |
9
|
|
| |
10
|
F. GSbel and A. A. Jagers. Random walks oll graphs. Stochastic Proces,~es and their Applications, 2:311-336, 1974.
|
| |
11
|
|
| |
12
|
Jeff D. Kahn, Nathan Linial, Noam Nisan, and Michael E. Saks. On the cover time of randoIn walks in graphs. Journal of Theoretical Probability, 1, 1989. To Appear.
|
| |
13
|
J.G. Kemeny, J. L. Snell. and A.W. KnapI~. Denumerable Markov Chains. The Universily Series in Higher Mathematics. Van Nostran(l, Princeton, NJ, 1966.
|
| |
14
|
H. J. Landau and A. M. Odlyzko. Bounc.s for eigenvalues of certain stochastic matrices. Linear Algebra and Its A2plications, 38:5-1~, 1981.
|
| |
15
|
Peter Mathews. Covering problems for random walks on spheres and finite groups. Technical Report TR 234, Stanford, Department of Statistics, 1985.
|
| |
16
|
J. C. Maxwell. A Treatise on Electricity and Magnetism. Clarendon, 1918.
|
| |
17
|
|
| |
18
|
Ronitt Rubinfeld. Personal communication. 1989.
|
| |
19
|
J.L. Synge. The fundamental theorem of electrical networks. Quarterly of Applied Math., 9:113-127, 1951.
|
| |
20
|
W. Thomson and P.G. TaR. Treatise on Natural Philosophy. Cambridge, 1879.
|
| |
21
|
David I. Zuckerman. A technique for lower bounding the cover time, 1989. Llnpublished manuscript, Berkeley.
|
CITED BY 32
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Coppersmith , P. Doyle , P. Raghavan , M. Snir, Random walks on weighted graphs, and applications to on-line algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.369-378, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
A. Borodin , W. L. Ruzzo , M. Tompa, Lower bounds on the length of universal traversal sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.562-573, May 14-17, 1989, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
Yair Bartal , Marek Chrobak , John Noga , Prabhakar Raghavan, More on random walks, electrical networks, and the harmonic k-server algorithm, Information Processing Letters, v.84 n.5, p.271-276, 16 December 2002
|
|
|
|
|
|
Noga Alon , Chen Avin , Michal Koucky , Gady Kozma , Zvi Lotker , Mark R. Tuttle, Many random walks are faster than one, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Chris Ding , Horst D. Simon , Rong Jin , Tao Li, A learning framework using Green's function and kernel regularization with application to recommender system, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
|
|
|
|
|
|
Luh Yen , Marco Saerens , Amin Mantrach , Masashi Shimbo, A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
|
|
|
|
|
|
Luh Yen , Francois Fouss , Christine Decaestecker , Pascal Francq , Marco Saerens, Graph nodes clustering with the sigmoid commute-time kernel: A comparative study, Data & Knowledge Engineering, v.68 n.3, p.338-361, March, 2009
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2