Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time \(O\big (\frac{\log (\epsilon ^{-1})\log n}{\epsilon ^3\log \log (\epsilon ^{-1})}\big )\), assuming performing a random walk step and sampling from a distribution with bounded support take constant time.
Computing heat kernel pagerank and a local clustering algorithm
Published 2014 in European journal of combinatorics (Print)
ABSTRACT
PUBLICATION RECORD
- Publication year
2014
- Venue
European journal of combinatorics (Print)
- Publication date
2014-10-15
- Fields of study
Mathematics, Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
CONCEPTS
- bounded-length random walks
Random walks that are truncated after a fixed maximum number of steps.
- bounded-support sampling
Sampling from a distribution whose possible outcomes lie in a finite support, assumed here to take constant time.
- constant-time random-walk step
The elementary operation of advancing one step in a random walk, assumed to cost constant time in the analysis.
- graph
The vertex-and-edge structure on which pagerank values are estimated.
- heat kernel pagerank
A PageRank-style score on a graph defined through an exponential weighting of walk lengths.
- sublinear-time algorithm
An algorithm whose running time grows slower than linearly with the size of the input graph.
REFERENCES
Showing 1-37 of 37 references · Page 1 of 1
CITED BY
Showing 1-37 of 37 citing papers · Page 1 of 1