The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
The heat kernel as the pagerank of a graph
Open accessAbstract
The concept of pagerank was first started as a way for determining the ranking of Web pages by Web search engines. Based on relations in interconnected networks, pagerank has become a major tool for addressing fundamental problems arising in general graphs, especially for large information networks with hundreds of thousands of nodes. A notable notion of pagerank, introduced by Brin and Page and denoted by PageRank, is based on random walks as a geometric sum. In this paper, we consider a notion of pagerank that is based on the (discrete) heat kernel and can be expressed as an exponential sum of random walks. The heat kernel satisfies the heat equation and can be used to analyze many useful properties of random walks in a graph. A local Cheeger inequality is established, which implies that, by focusing on cuts determined by linear orderings of vertices using the heat kernel pageranks, the resulting partition is within a quadratic factor of the optimum. This is true, even if we restrict the volume of the small part separated by the cut to be close to some specified target value. This leads to a graph partitioning algorithm for which the running time is proportional to the size of the targeted volume (instead of the size of the whole graph).
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
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
Harary, F. (1969) · Cited by 10,739
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Self-citationLocal Graph Partitioning using PageRank Vectors
Andersen, R., Chung, F., & Lang, K. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.44 · Cited by 967
Self-citationA Lower Bound for the Smallest Eigenvalue of the Laplacian
Cheeger, J. (2015) · Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31) · doi:10.1515/9781400869312-013 · Cited by 961
On clusterings: Good, bad and spectral
Kannan, R., Vempala, S., & Vetta, A. (2004) · Journal of the ACM · doi:10.1145/990308.990313 · Cited by 834
Spielman, D. A., & Teng, S.-H. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007372 · Cited by 769
Random walks in a convex body and an improved volume algorithm
Lovász, L., & Simonovits, M. (1993) · Random Structures & Algorithms · doi:10.1002/rsa.3240040402 · Cited by 409
Introductio in analysin infinitorum
Euler, L. (1967) · doi:10.3931/e-rara-8740 · Cited by 377
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
Lovasz, L., & Simonovits, M. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89553 · Cited by 190
Coverings, Heat Kernels and Spanning Trees
Chung, F., & Yau, S. (1998) · The Electronic Journal of Combinatorics · doi:10.37236/1444 · Cited by 79
Self-citationDetecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm
Andersen, R., & Chung, F. (2007) · Springer eBooks · doi:10.1007/978-3-540-72504-6_1 · Cited by 52
Self-citationFour proofs for the Cheeger inequality and graph partition algorithms
Chung, F. (2007) · Cited by 40
Self-citation
Cited by
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Leiserson, M. D. M., Vandin, F., Wu, H.-T., Dobson, J. R., Eldridge, J. V., Thomas, J. L., Papoutsaki, A., Kim, Y., Niu, B., McLellan, M., et al. (2015) · Nature Genetics · doi:10.1038/ng.3168 · Cited by 903
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Random walks and diffusion on networks
Masuda, N., Porter, M. A., & Lambiotte, R. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.07.007 · Cited by 657
Gleich, D. F. (2015) · SIAM Review · doi:10.1137/140976649 · Cited by 646
Metadata
- Authors
- Chung, F.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2007-12-11
- Volume
- 104
- Issue
- 50
- Pages
- 19735-19740
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2171878761
- Cited by
- 254
- References
- 14
- FWCI
- 5.33
- Type
- journal article
- Language
- en
- Open access
- green
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.