WNCG Seminar Series: Fast Probability Estimation in Sparse Markov Models

Event Status
Scheduled

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.
Date and Time
May 15, 2015, All Day