<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">Speaker:&nbsp;<a href="http://web.stanford.edu/~sidb/">Siddhartha Bannerjee</a><br><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><p>Title: Scaling Social Search - PageRank Estimation for Large Networks<br></p><p>When and Where: 29th August (Friday) at 2:00 PM in Room 402 in the CS bldg.</p><div>Abstract:<br></div><p dir="ltr">Although effective search is one of the great successes of the internet, social search lags far behind. A major hurdle is the complexity of existing algorithms for estimating Personalized PageRank -- a generalization of PageRank which measures centrality with respect to a fixed node in a network. In particular, to estimate PageRank values up to the required accuracies, existing algorithms need time which scales linearly in the network size -- this renders them infeasible for real-time social search.</p><p dir="ltr">In this talk, I will present FAST-PPR, the first algorithm for Personalized PageRank estimation with an average running-time guarantee which is sublinear in the network size. This speedup is achieved via a combination of linear algebraic techniques and random walks; this new approach may prove useful in other estimation problems on networks. Moreover, I'll present detailed empirical studies on numerous large networks, wherein FAST-PPR dramatically outperforms existing algorithms -- for example, with target nodes sampled according to popularity, on the 2010 Twitter graph with 1.5 billion edges, FAST-PPR has a 160 factor speedup compared to the state-of-the-art.</p><p dir="ltr">Joint work with Peter Lofgren, Ashish Goel and C. Seshadri. Paper available at&nbsp;<a href="http://arxiv.org/abs/1404.3181" target="_blank">http://arxiv.org/abs/1404.3181</a>.</p></div></div></div></div></body></html>