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
Research works printed but not linked: 1
- berkhin, 0, Bookmark-coloring approach to personalized pagerank computing, Internet Mathematics
Cited by
Sorted by citations
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,912
Self-citationSchaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,679
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2013) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,531
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
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
