2012 EfficientPersonalizedPagerankwi

• (Fujiwara et al., 2012) ⇒ Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, and Makoto Onizuka. (2012). "Efficient Personalized Pagerank with Accuracy Assurance". In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 [http://dx.doi.org/10.1145/2339530.2339538 doi:10.1145/2339530.2339538

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Efficient+Personalized+Pagerank+with+Accuracy+Assurance
• http://dl.acm.org/citation.cfm?id=2339530.2339538&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; personalized pagerank; relevance computation

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 EfficientPersonalizedPagerankwi	Yasuhiro Fujiwara Makoto Nakatsuji Takeshi Yamamuro Hiroaki Shiokawa Makoto Onizuka			Efficient Personalized Pagerank with Accuracy Assurance				10.1145/2339530.2339538		2012