Fast Incremental and Personalized PageRank

Details Fast Incremental and Personalized PageRank Fast Incremental and Personalized PageRank

2010-06-15

arxiv.org/abs/1006.2880v2

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evolving social networks. We assume that the graph of friendships is stored in distributed shared memory, as is the case for large social networks such as Twitter. For global PageRank, we assume that the social network has $n$ nodes, and $m$ adversarially chosen edges arrive in a random order. We show that with a reset probability of $\epsilon$, the total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is $O(\frac{n\ln m}{\epsilon^{2}})$. This is significantly better than all known bounds for incremental PageRank. For instance, if we naively recompute the PageRanks as each edge arrives, the simple power iteration method needs $\Omega(\frac{m^2}{\ln(1/(1-\epsilon))})$ total time and the Monte Carlo method needs $O(mn/\epsilon)$ total time; both are prohibitively expensive. Furthermore, we also show that we can handle deletions equally efficiently. We then study the computation of the top $k$ personalized PageRanks starting from a seed node, assuming that personalized PageRanks follow a power-law with exponent $\alpha < 1$. We show that if we store $R>q\ln n$ random walks starting from every node for large enough constant $q$ (using the approach outlined for global PageRank), then the expected number of calls made to the distributed social network database is $O(k/(R^{(1-\alpha)/\alpha}))$. We also present experimental results from the social networking site, Twitter, verifying our assumptions and analyses. The overall result is that this algorithm is fast enough for real-time queries over a dynamic social network.

Affiliated with

Also associated with

No associations

Rating

Fast Incremental and Personalized PageRank does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Incremental and Personalized PageRank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Incremental and Personalized PageRank will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104234