Efficient Random Walk Computation, and Ranking Mechanisms on the Web

Random walks are a fundamental tool used widely across several areas of computer science – theory, web algorithms, distributed networks, as well as mathematics and statistical physics. On the web and in distributed graphs, random walks are used for several algorithmic applications such as sampling, ranking, mining similarity, estimating connectivity, and graph partitioning.

In the first part of the talk, I will present our work on performing random walks on large graphs presented as edge streams. The naive technique for performing a random walk of length ℓ requires O(ℓ) passes over the input stream. We present the first nontrivial technique that shows how to perform such walks in O(√ℓ) passes. We show how this technique can be used to estimate PageRank vectors in O(n) space and O(√M) passes, where n is the number of nodes in the graph, and M is the mixing time. In comparison, a standard implementation of PageRank requires O(n) space and O(M) passes. In subsequent work, we use this technique to obtain sub-linear time algorithms for computing random walks on distributed networks. These techniques have shown how to break past the longstanding linear-time barrier and perform random walks much more efficiently.

In the latter part of the talk, I will briefly present work on understanding user feedback based ranking mechanisms employed on the web. Such ranking mechanisms are ubiquitous, for e.g., ranking on youtube, forums, social networks, digg, question-answering sites etc. The main metric used to evaluate a mechanism is the ranking accuracy vs. the cost of reviews. We show that for many reasonable probability models, the widely used thumbs (or stars) based mechanisms cannot produce approximately accurate rankings with bounded reviews per item. We provide a ranking mechanism based on pairwise comparisons which achieves approximate rankings with bounded cost. We have a system Shout Velocity (http://shoutvelocity.com), which is a twitter-like forum, and implements a comparison based ranking mechanism.