WNCG Seminar Series: Fast Probability Estimation in Sparse Markov Models

Friday, May 15, 2015
2:00pm - 3:00pm
UTA 7.532

A fundamental problem in Markov Chains is estimating the probability of transitioning to a given terminal state in k steps from some initial distribution. This has received added attention in recent years due to the success of PageRank and related Markov-Chain based centrality measures for networks. Standard approaches to this problem use linear-algebraic methods (power iteration) or Monte Carlo. Both however need order 1/p running time for estimating probabilities on the order of p; moreover, neither can be adapted for a single terminal state, but rather, give estimates for the entire distribution. This is particularly problematic for estimating Personalized PageRank, an ego-centric generalization of PageRank, which has long been recognized as an effective measure for ranking search results, but is rarely used in practice as existing algorithms do not scale well to large networks. 

I'll present a new bi-directional algorithm which combines linear algebraic techniques with random walks, and show that in sparse graphs, it returns an accurate estimate of transition probabilities of the order of p in time O(1/\sqrt{p}). In particular, our approach provides the first algorithm for PageRank estimation with running-time which is sublinear in network size. More importantly, experiments show that in practice, our algorithm is much faster than existing algorithms (for example, it is 100 times faster on the Twitter 2010 network). 
Joint work with Peter Lofgren, Ashish Goel and C. Seshadri.


Postdoctoral Researcher
Stanford University

Sid Banerjee is currently a postdoctoral researcher in the Department of Management Science and Engineering at Stanford University, where he is hosted by Ramesh Johari and Ashish Goel. He will be joining the Operations Research Department at Cornell as an assistant professor in July 2015. An alumni of WNCG, Dr. Banerjee completed his PhD under the guidance of WNCG Profs. Sanjay Shakkottai and Sujay Sanghavi. His research interests include stochastic modeling and the design of algorithms and incentives for large-scale systems.