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.

本文分析了 Monte Carlo 方法在动态社交网络中增量计算 PageRank、个性化 PageRank 和类似的基于随机行走方法（重点关注 SALSA）时的效率，针对全局 PageRank 做出了重大改进，同时也可以同样高效地处理删除，并研究了顶部 k 个个性化 PageRank 的计算。