DBScholar

Back to papers

Fast Incremental and Personalized PageRank

Summary: Monte Carlo maintenance of global PageRank under adversarial edge updates in random order achieves O(n log m/ε²) total work, with deletions equally efficient. For power-law personalized PageRank, precomputed walks enable fast top-k queries and real-time distributed-network performance, validated on Twitter. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h82439787bf0b4b1e
Venue
VLDB
Year
2011
Pagerank
0.00016492651
Overall Rank
556 | 96.27%
DOI
10.14778/1920841.1920844

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{bahmani_vldb11,
        title = {{Fast Incremental and Personalized PageRank}},
        author = {Bahmani, Bahman and Chowdhury, Abdur and Goel, Ashish},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {3},
        pages = {173--184},
        doi = {10.14778/1920841.1920844},
        url = {https://doi.org/10.14778/1920841.1920844},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
964 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00012814643
1,368 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010901078
1,861 Efficient Ad-hoc Search for Personalized PageRank 2013 SIGMOD 9.4839542e-05
1,876 Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs 2014 VLDB 9.4535107e-05
2,103 BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 2017 SIGMOD 9.0420935e-05
2,185 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD 8.8920069e-05
2,395 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.5281025e-05
3,018 Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank 2023 VLDB 7.743467e-05
3,267 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 7.4739604e-05
3,655 Realtime Top-k Personalized PageRank over Large Graphs on GPUs 2020 VLDB 7.1254436e-05
3,896 FREDE: Anytime Graph Embeddings 2021 VLDB 6.9349294e-05
4,103 TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs 2018 SIGMOD 6.8040813e-05
4,148 A Benchmarking Study of Embedding-based Entity Alignment for Knowledge Graphs 2020 VLDB 6.7771314e-05
4,264 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.6947069e-05
4,781 Tornado: A System For Real-Time Iterative Analysis Over Evolving Data 2016 SIGMOD 6.4154314e-05
5,303 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.1867551e-05
5,918 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 5.9465067e-05
6,328 EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs 2023 SIGMOD 5.8110274e-05
6,584 Exact Single-Source SimRank Computation on Large Graphs 2020 SIGMOD 5.7417834e-05
6,791 Indexed Fast Network Proximity Querying 2018 VLDB 5.6796169e-05
7,408 Space-Efficient Random Walks on Streaming Graphs 2023 VLDB 5.5328449e-05
8,233 Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time 2023 VLDB 5.3714879e-05
8,384 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD 5.3406945e-05
9,955 Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs 2025 SIGMOD 5.1014161e-05
10,845 Sankofa: Online Query-adaptive Dynamic Graph Summaries 2026 VLDB 4.9769913e-05
11,539 A Lovasz-Simonovits Theorem for Hypergraphs with Application to Local Clustering 2024 SIGMOD 4.9769913e-05
12,132 Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice 2020 VLDB 4.9769913e-05
12,601 Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis 2012 PODS 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1,415 Estimating PageRank on Graph Streams 2008 PODS 0.00010732327
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,233 Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time 2023 VLDB
2 2,395 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB
3 1,415 Estimating PageRank on Graph Streams 2008 PODS
4 4,264 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD
5 4,562 Leveraging History for Faster Sampling of Online Social Networks 2015 VLDB
6 6,405 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD
7 1,368 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB
8 3,978 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB
9 8,232 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD
10 964 Fast Personalized PageRank on MapReduce 2011 SIGMOD