The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Fast incremental and personalized PageRank
Abstract
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 ε, the expected total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is [EQUATION]. 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 [EQUATION] total time and the Monte Carlo method needs O ( mn /ε) total time; both are prohibitively expensive. 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 α < 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-α)/α )). 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135 · cited 2×
“Notice that this is a weaker assumption on the network evolution model than most of the popular models, such as the Preferential Attachment model [4].”
BackgroundResult(1999) · Cited by 12,854
Introduction to information retrieval
(2009) · Choice Reviews Online · doi:10.5860/choice.46-2715 · Cited by 12,278
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Amazon.com recommendations: item-to-item collaborative filtering
Linden, G., Smith, B., & York, J. (2003) · IEEE Internet Computing · doi:10.1109/mic.2003.1167344 · Cited by 5,403
Introduction to Social Network Methods
Hanneman, R. A. (2001) · Cited by 3,956
The link prediction problem for social networks
Liben-Nowell, D., & Kleinberg, J. (2003) · Proceedings of the twelfth international conference on Information and knowledge management · doi:10.1145/956863.956972 · Cited by 1,612
Haveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Google news personalization: scalable online collaborative filtering
Das, A. S., Datar, M., Garg, A., & Rajaram, S. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242610 · Cited by 1,511
Scaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195 · cited 7×
“Linear algebraic methods: These methods mainly use techniques from linear and matrix algebra, perhaps with some application of structural properties of the networks of interest (e.g., the world wide web) [8,9,16, 19–22,24,25,27–29,35,41–43].”
BackgroundMethodInfluentialCombating Web Spam with TrustRank
Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50052-8 · Cited by 1,085
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
Extrapolation methods for accelerating PageRank computations
Kamvar, S. D., Haveliwala, T. H., Manning, C. D., & Golub, G. H. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775190 · Cited by 407
SALSA: the stochastic approach for link-structure analysis
Lempel, R., & Moran, S. (2001) · ACM Transactions on Information Systems · doi:10.1145/382979.383041 · Cited by 362
(2003) · Cited by 312
Link analysis ranking: algorithms, theory, and experiments
Borodin, A., Roberts, G. O., Rosenthal, J. S., & Tsaparas, P. (2005) · ACM Transactions on Internet Technology · doi:10.1145/1052934.1052942 · Cited by 308
Stable algorithms for link analysis
Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001) · Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/383952.384003 · Cited by 286
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
Fogaras, D., Rácz, B., Csalogány, K., & Sarlós, T. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129104 · Cited by 282
Adaptive methods for the computation of PageRank
Kamvar, S., Haveliwala, T., & Golub, G. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2003.12.008 · Cited by 271
Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2007) · SIAM Journal on Numerical Analysis · doi:10.1137/050643799 · Cited by 250 · cited 3×
“Our algorithm is a Monte Carlo method [2] that works by maintaining a small number of short random walk segments starting at each node in the social graph.”
BackgroundMethodInfluentialLink Prediction on Evolving Data Using Matrix and Tensor Factorizations
Acar, E., Dunlavy, D., & Kolda, T. G. (2009) · IEEE ... International Conference on Data Mining workshops · doi:10.1109/icdmw.2009.54 · Cited by 184
Fast online SVD revisions for lightweight recommender systems
Brand, M. (2003) · Proceedings of the 2003 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972733.4 · Cited by 178
Scalable proximity estimation and link prediction in online social networks
Song, H. H., Cho, T. W., Dave, V., Zhang, Y., & Qiu, L. (2009) · Proceedings of the 9th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1644893.1644932 · Cited by 177
Ranking systems: the PageRank axioms
Altman, A., & Tennenholtz, M. (2005) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1064009.1064010 · Cited by 158
A uniform approach to accelerated PageRank computation
McSherry, F. (2005) · International World Wide Web Conference (WWW) · doi:10.1145/1060745.1060829 · Cited by 139
What is this page known for? Computing Web page reputations
Rafiei, D., & Mendelzon, A. O. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00078-5 · Cited by 126
Link Prediction Based on Graph Topology: The Predictive Value of Generalized Clustering CoefficientPreprint
Huang, Z. (2010) · SSRN Electronic Journal · doi:10.2139/ssrn.1634014 · Cited by 125
Local methods for estimating pagerank values
Chen, Y., Gan, Q., & Suel, T. (2004) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1031171.1031248 · Cited by 106
Updating Markov Chains with an Eye on Google's PageRank
Langville, A. N., & Meyer, C. D. (2006) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/040619028 · Cited by 105
Proximity Tracking on Time-Evolving Bipartite Graphs
Tong, H., Papadimitriou, S., Yu, P. S., & Faloutsos, C. (2008) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972788.64 · Cited by 92
To randomize or not to randomize: space optimal summaries for hyperlink analysis
Sarlós, T., Benczúr, A. A., Csalogány, K., Fogaras, D., & Rácz, B. (2006) · International World Wide Web Conference (WWW) · doi:10.1145/1135777.1135823 · Cited by 84
Estimating PageRank on graph streams
Sarma, A. D., Gollapudi, S., & Panigrahy, R. (2008) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1376916.1376928 · Cited by 76
Updating pagerank with iterative aggregation
Langville, A. N., & Meyer, C. D. (2004) · Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters - WWW Alt. '04 · doi:10.1145/1013367.1013491 · Cited by 64 · cited 3×
“First, the performance of these methods heavily depends on the partitioning of the network, and as pointed out in [27], a bad choice of this partitioning can cause these methods to be as slow as the power iteration.”
MethodIn-Degree and PageRank: Why Do They Follow Similar Power Laws?
Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2007) · Internet Mathematics · doi:10.1080/15427951.2007.10129293 · Cited by 62 · cited 3×
“…observe that not only do the global PageRank scores and in-degrees follow the same power-laws (as previously proved under mild assumptions in the literature [33]), but also the personalized PageRanks follow power-laws with average exponent roughly equal to the exponent for PageR-ank and in-degree.”
BackgroundResultInfluentialComparing the effectiveness of hits and salsa
Najork, M. (2007) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/1321440.1321465 · Cited by 45
Fast Incremental and Personalized PageRankPreprint
Bahmani, B., Chowdhury, A., & Goel, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1006.2880 · Cited by 27
Self-citationUpdating pagerank using the group inverse and stochastic complementation
Langville, A. N., & Meyer, C. D. (2002) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 15
Updating the stationary vector of an irreducible Markov chain
Langville, A. N., & Meyer, C. D. (2002) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 8
Cited by
Gleich, D. F. (2015) · SIAM Review · doi:10.1137/140976649 · Cited by 646
Simplicial closure and higher-order link prediction
Benson, A. R., Abebe, R., Schaub, M. T., Jadbabaie, A., & Kleinberg, J. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1800683115 · Cited by 548
WTF: the who to follow service at Twitter
Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., & Zadeh, R. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488433 · Cited by 461
Self-citationStreaming graph partitioning for large distributed graphs
Stanton, I., & Kliot, G. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339722 · Cited by 446
Evolutionary Network Analysis: A Survey
Aggarwal, C., & Subbian, K. (2014) · ACM Computing Surveys · doi:10.1145/2601412 · Cited by 313
Metadata
- Authors
- Bahmani, B., Chowdhury, A., & Goel, A.
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2010-12
- Volume
- 4
- Issue
- 3
- Pages
- 173-184
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2051381393
- Cited by
- 327
- References
- 39
- FWCI
- 9.93
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.