Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Fete of Combinatorics and Computer SciencePageRank and Random Walks on Graphs

Fete of Combinatorics and Computer Science: PageRank and Random Walks on Graphs [We examine the relationship between PageRank and several invariants occurring in the study of random walks and electrical networks. We consider a generalized version of hitting time and effective resistance with an additional parameter which controls the ‘speed’ of diffusion. We will establish their connection with PageRank. Through these connections, a combinatorial interpretation of Page-Rank is given in terms of rooted spanning forests by using a generalized version of the matrix-tree theorem. Using PageRank, we will illustrate that the generalized hitting time leads to finding sparse cuts and efficient approximation algorithms for PageRank can be used for approximating hitting time and effective resistance.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Fete of Combinatorics and Computer SciencePageRank and Random Walks on Graphs

Part of the Bolyai Society Mathematical Studies Book Series (volume 20)
Editors: Katona, Gyula O. H.; Schrijver, Alexander; Szőnyi, Tamás; Sági, Gábor
Chung, Fan; Zhao, Wenbo
Fete of Combinatorics and Computer Science — Jan 31, 2011
Download PDF
19 pages

Loading next page...
 
/lp/springer-journals/fete-of-combinatorics-and-computer-science-pagerank-and-random-walks-dWxMEqGA2E
Publisher
Springer Berlin Heidelberg
Copyright
© János Bolyai Mathematical Society and Springer-Verlag 2010
ISBN
978-3-642-13579-8
Pages
43 –62
DOI
10.1007/978-3-642-13580-4_3
Publisher site
See Chapter on Publisher Site

Abstract

[We examine the relationship between PageRank and several invariants occurring in the study of random walks and electrical networks. We consider a generalized version of hitting time and effective resistance with an additional parameter which controls the ‘speed’ of diffusion. We will establish their connection with PageRank. Through these connections, a combinatorial interpretation of Page-Rank is given in terms of rooted spanning forests by using a generalized version of the matrix-tree theorem. Using PageRank, we will illustrate that the generalized hitting time leads to finding sparse cuts and efficient approximation algorithms for PageRank can be used for approximating hitting time and effective resistance.]

Published: Jan 31, 2011

Keywords: Random Walk; Electrical Network; Distinct Vertex; Effective Resistance; Commute Time

There are no references for this article.