Name
Abstract | ||
|---|---|---|
Personalize PageRank (PPR) is an effective relevance (proximity) measure in graph mining. The goal of this paper is to efficiently compute single node relevance and top-k/highly relevant nodes without iteratively computing the relevances of all nodes. Based on a "random surfer model", PPR iteratively computes the relevances of all nodes in a graph until convergence for a given user preference distribution. The problem with this iterative approach is that it cannot compute the relevance of just one or a few nodes. The heart of our solution is to compute single node relevance accurately in non-iterative manner based on sparse matrix representation, and to compute top-k/highly relevant nodes exactly by pruning unnecessary relevance computations based on upper/lower relevance estimations. Our experiments show that our approach is up to seven orders of magnitude faster than the existing alternatives. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2339530.2339538 | KDD |
Keywords | Field | DocType |
efficient personalized pagerank,relevant node,accuracy assurance,iterative approach,personalize pagerank,existing alternative,lower relevance estimation,graph mining,ppr iteratively,effective relevance,pruning unnecessary relevance,single node relevance,sparse matrix | Convergence (routing),Graph,PageRank,Data mining,Computer science,Theoretical computer science,Artificial intelligence,Sparse matrix,Machine learning,Computation | Conference |
Citations | PageRank | References |
27 | 0.91 | 31 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yasuhiro Fujiwara | 1 | 292 | 25.43 |
| Makoto Nakatsuji | 2 | 225 | 13.16 |
| Takeshi Yamamuro | 3 | 50 | 3.66 |
| Hiroaki Shiokawa | 4 | 153 | 12.82 |
| Makoto Onizuka | 5 | 369 | 33.84 |