The DOI matches its Crossref record; 22 of the 23 references it cites were found in a registry or an index.
Local Graph Partitioning using PageRank Vectors
Abstract
A local graph partitioning algorithm finds a cut near a specified starting vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance Phi and volume k, a PageRank vector with a certain starting distribution can be used to produce a set with conductance (O(radic(Phi log k)). We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most oslash, whose small side has volume at least 2bin time O(2 log m/(2blog2m/oslash2) where m is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance oslash and approximately optimal balance in time O(m log4m/oslash)
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
(1999) · Cited by 12,854
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
Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search
Haveliwala, T. H. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1208999 · Cited by 1,046
Kannan, R., Vempala, S., & Vetta, A. R. (2004) · Journal of the ACM · doi:10.1145/990308.990313 · Cited by 857
Spielman, D. A., & Teng, S. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007372 · Cited by 803
Schlenk, F. (2005) · De Gruyter eBooks · doi:10.1515/9783110199697.107 · Cited by 461
Adleman, L. M., & Huang, M.-D. A. (1992) · Lecture notes in mathematics · doi:10.1007/bfb0090191 · Cited by 437
SPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
Biggs, N. (1998) · Bulletin of the London Mathematical Society · doi:10.1112/s0024609397223611 · Cited by 437
Random walks in a convex body and an improved volume algorithm
Lovász, L., & Simonovits, M. (1993) · Random Structures and Algorithms · doi:10.1002/rsa.3240040402 · Cited by 418
Flagged first, then by citations
1 of the 23 references couldn’t be matched to a known paper.
Research works printed but not linked: 1
- berkhin, 0, Bookmark-coloring approach to personalized pagerank computing, Internet Mathematics
Cited by
Sorted by citations
Items 901–966 of 966
Advanced Topics in Graph Neural Networks
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.020
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.023
Graph Neural Networks for Complex Graphs
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.012
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.019
Deep Learning on Graphs: An Introduction
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.003
Beyond GNNs: More Deep Models on Graphs
Ma, Y., & Tang, J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108924184.013
A Structural Result for Personalized PageRank and its Algorithmic Consequences
Vial, D., & Subramanian, V. (2019) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3376930.3376956
Zhao, P. (2019) · Springer eBooks · doi:10.1007/978-3-319-77525-8_320
Community Detection in Networks Using Page Rank Vectors
Greeshma, V., & Suvarna Vani, K. (2015) · International Journal on Bioinformatics & Biosciences · doi:10.5121/ijbb.2015.5401
Murali, M. (2019) · doi:10.31979/etd.4cu5-yv9s
Neighborhood embedding and re-ranking of disease genes with ADAGIO
Erden, M., Gelement, M., Hakimjee, S. M., Levin, K. H., Sidhom, M.-J., Devkota, K., & Cowen, L. (2022) · ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB) · doi:10.1145/3535508.3545542
Deterministic Graph-Walking Program Mining
Belcak, P., & Wattenhofer, R. P. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22064-7_33
Maximal k -Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
Nalam, C., & Saranurak, T. (2023) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977554.ch8
Cache-Efficient Approach for Index-Free Personalized PageRank
Tsuchida, K., Matsumoto, N., Shin, A., & Kaneko, K. (2023) · IEEE Access · doi:10.1109/access.2023.3237738
Community Detection in Large Directed Graphs
Chen, S., & Bhatnagar, R. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-24094-2_12
Index-adaptive Triangle-Based Graph Local Clustering
Zhe, Y., Wei, Z., & Ji-rong, W. (2023) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2023.038531
Predicate-Augmented Personalized PageRank for Entity Typing in Knowledge Graphs
Zhang, M., Dai, J., Qiao, L., Zhong, C., & Wang, J. (2022) · IEEE Smart World Congress (SWC) · doi:10.1109/smartworld-uic-atc-scalcom-digitaltwin-pricomp-metaverse56740.2022.00266
Qiu, G., Tao, D., & Su, H. (2023) · Journal of Intelligent & Fuzzy Systems · doi:10.3233/jifs-232846
RetractedSingular Value Approximation and Sparsifying Random Walks on Directed Graphs
Ahmadinejad, A., Peebles, J., Pyne, E., Sidford, A., & Vadhan, S. (2023) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs57990.2023.00054
Ginkgo-P: General Illustrations of Knowledge Graphs for Openness as a Platform
Hill, B., Liu, L., & Tong, H. (2024) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3616855.3635701
GPPR: Geo-distributed Personalized PageRank Algorithm
Chen, Z., Ma, D., Wang, Y., & Yuan, Y. (2024) · International Journal of Software and Informatics · doi:10.21655/ijsi.1673-7288.00320
Enhancing recommender systems via data augmentation
Zhang, L. (2023) · doi:10.32657/10356/179298
Ge, J., Sun, H., Lin, Y., & He, L. (2024) · Expert Systems · doi:10.1111/exsy.13704
Transaction Tracking Based on Personalized PageRank Algorithm
Wu, Z., Liu, J., Wu, J., & Zheng, Z. (2024) · Big data management · doi:10.1007/978-981-97-4430-5_8
On the Scalability of Large Graph Methods for Kernel-Based Machine Learning*
Sun, Y. (2024) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton63246.2024.10735281
Detaching Range from Depth: Personalized Recommendation Meets Personalized PageRank
Hu, J., Xu, J. J., Chen, J., Qiao, L., Wang, J., Huang, F., & Li, C. (2024) · Lecture notes in computer science · doi:10.1007/978-981-96-0116-5_38
Performance Comparison of Estimation Methods in Network Analysis
Pirouz, M. (2024) · IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON) · doi:10.1109/uemcon62879.2024.10754752
A Detailed Review Analysis on Emerging Contaminants-Based Systems Using Intelligent Method
Tiwari, N. (2024) · Advances in intelligent systems and computing · doi:10.1007/978-981-97-6349-8_43
Alignment of Protein-Protein Interaction Networks
Milano, M., & Cinaglia, P. (2024) · Elsevier eBooks · doi:10.1016/b978-0-323-95502-7.00199-8
Chen, T., Ma, H., & Li, J. (2024) · International Conference on Systems and Informatics (ICSAI) · doi:10.1109/icsai65059.2024.10893824
Eigen Monte CarloPreprint
Aldridge, I. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5215261
Fast Probabilistic Core IdentificationPreprint
Aldridge, I. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5246787
Fast Probabilistic Core IdentificationPreprint
Aldridge, I. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5249479
Piñol, C., Curado, M., Vicent, J. F., & Banegas‐Luna, A. J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-99565-1_21
Core Trends in Complex Networks for Social Network Analysis
Pirouz, M. (2024) · IEEE Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON) · doi:10.1109/iemcon62851.2024.11093317
WalkSum: Graph Summarization for Accurate Random Walks
Okamatsu, K., Yamashita, T., & Kaneko, K. (2025) · International Conference on Ubiquitous and Future Networks · doi:10.1109/icufn65838.2025.11169864
Coarse-and-Learn: Efficient Online Node Labeling
Halder, S., Kumar, M., Sun, Y., & Kumar, S. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-4384-7_32
AMRaCut: Scalable Partitioning for Adaptive Mesh Refinement
Edippuliarachchi, B., Komen, D. F. V., & Sundar, H. (2025) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3712285.3759863
Experimental Analysis of Differential Privacy Strength in GNNs Over Bitcoin Transaction Networks
Ueda, M., Kondo, K., Hwang, S.-H., Jung, Y.-A., & Hwang, S.-W. (2025) · Journal of Digital Contents Society · doi:10.9728/dcs.2025.26.11.3139
Local Structure and Inference in Large Random Graphs
Kim, N. (2020) · Figshare · doi:10.1184/r1/13421732
Spectral Approach to Modern Algorithm Design
Kumar, A. (2020) · Figshare · doi:10.25394/pgs.12252191
Zheng, L., Ni, J., Zobel, C. W., & Birge, J. R. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5991354
A Comparative Study of Local Community Detection Algorithms in Static Graphs
Christopoulos, K., Tsiamis, G., & Tsichlas, K. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-13744-9_9
Aldridge, I. (2025) · Winter Simulation Conference · doi:10.1109/wsc68292.2025.11339108
Kamalipour, P., & Harutyunyan, H. A. (2025) · International Conference on Social Networks Analysis, Management and Security (SNAMS) · doi:10.1109/snams67467.2025.11391193
Scaling up Electrical Closeness Centrality Computation
Liao, M., Li, R.-H., Dai, Q., & Wang, G. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3670233
DGM: deep graph clustering with mincut for analysis of single-cell transcriptomics
Liu, X., Chen, X. B., Yang, W., & Yu, Y. (2026) · BMC Genomics · doi:10.1186/s12864-026-12694-y
LocAPS: Adaptive Positive Sampling for Network Embedding
Wu, A., Yu, Y., Li, C., Ma, Y., & Wang, Y. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3677006
Scalable Similarity Search Over Large Attributed Bipartite Graphs
Ou, X., Lin, L., Wang, Z., Yuan, P., & Li, R.-H. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3676380
Détection de communautés orientée sommet pour des réseaux mobiles opportunistes sociaux
Canu, M. (2017) · theses.fr (ABES) · doi:10.70675/5ffe4f73z4c22z4383za9bczec3fb7a9926c
AdaPush: An Adaptive Push Framework for Graph-Propagation Based Node Similarity Computation
Yang, Y., Li, R.-H., Liao, M., & Wang, G. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3681914
Graph-to-Tree: Topological Decomposition for Self-Supervised Learning
Wang, Y., Zhao, Y., Li, F., Wang, J., Wang, M., Li, L., Huang, M., Wang, Z., & Pan, S. (2026) · International World Wide Web Conference (WWW) · doi:10.1145/3774904.3792286
Multi-Course Integration Framework Based on Subject Knowledge Graphs
Yu, D., & Zhuang, Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11462843
(2022) · Emerald Group Publishing Limited eBooks · doi:10.1561/978-1-63828-051-420251011
S2RAF: A Semantic and Structure aware ReAsoning Framework for question answering over textual graphs
Luo, J., Hu, P., & Zhang, M. (2026) · Information Processing & Management · doi:10.1016/j.ipm.2026.104886
Fast Estimation of Pairwise Biharmonic Distance on Graphs
Liu, C., Zhou, X. Y., Zhang, B., Zehmakan, A. N., & Zhang, Z. (2026) · Proceedings of the ACM on Management of Data · doi:10.1145/3802058
Heterophily-Robust Patient-Similarity Graphs for Parkinson’s Screening from Voice
Srivastava, E., Ujjain, S., Gandhi, T. K., & Kumar, S. (2026) · International Conference on Intelligent Computing and Automation for Sustainable Solutions (ICASS) · doi:10.1109/icass69550.2026.11547453
FairFBC: Scalable Fair Fuzzy Clustering via Group-Balanced Anchor Graphs
Zhao, T., Chen, Y., Wu, P., Wen, C., Zhou, P., & Du, L. (2026) · International Conference on Multimedia Retrieval · doi:10.1145/3805622.3810706
Extreme Reachability of Continuous Time Random Walks on Networks
Ma, F., Hu, X., Ouyang, J., Pan, J., & Shi, H. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3818018
Faster and better quality conductance solutions with the incremental parametric cut algorithm
Hochbaum, D. S., Irribarra-Cortés, A., & Asín‐Achá, R. (2026) · Optimization and Engineering · doi:10.1007/s11081-026-10118-0
Fast and Accurate Random Walk Index Maintenance for Graph Merging
Fukuzawa, H., Yamashita, T., & Kaneko, K. (2026) · ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA) · doi:10.1145/3810460.3812775
Sankofa: Online Query-Adaptive Dynamic Graph Summaries
Bainson, A. B., Mortensen, K. O., Zaporojets, K., Mottin, D., & Karras, P. (2026) · Proceedings of the VLDB Endowment · doi:10.14778/3828612.3828641
Wu, H., Wang, H., Li, S., Wu, Y., Fan, M. Y., Liu, T., & Luo, X. (2026) · Proceedings of the ACM on software engineering. · doi:10.1145/3832127
Wang, H., & Oba, K. (2026) · Frontiers in Bioinformatics · doi:10.3389/fbinf.2026.1924703
Metadata
- Authors
- Andersen, R., Chung, F., & Lang, K.
- Affiliations
- University of California San Diego (US)
- Yahoo (United States) (US)
- Venue
- 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
- Publisher
- IEEE
- Published
- 2006
- Pages
- 475-486
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2086254934
- Cited by
- 967
- References
- 23
- Citations by year
- 2026: 20 · 2025: 40 · 2024: 46 · 2023: 57 · 2022: 55 · 2021: 84 · 2020: 71 · 2019: 72 · 2018: 63 · 2017: 61 · 2016: 69 · 2015: 65 · 2014: 52 · 2013: 55 · 2012: 50
- FWCI
- 13.60
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Keywords
- graph cuts, conductance, random walks
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
