WNCG Seminar Series: Fast Probability Estimation in Sparse Markov Models

Friday, May 15, 2015
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.


Photo: Prof. Sid Banerjee
Assistant Professor
Cornell University

Sid Banerjee is an Assistant Professor in the School of Operations Research and Information Engineering (ORIE) at Cornell, as well as a field member in the CS and ECE Departments and the Center for Applied Mathematics. His research is on stochastic modeling and control, and the design of algorithms and incentives for large-scale systems. He got his PhD in ECE from UT Austin, and worked as a postdoctoral researcher in the Social Algorithms Lab at Stanford, as well as a technical consultant at Lyft. His work is supported by an NSF CAREER award, and grants from the NSF and ARL.