Personalized Pagerank with Accuracy Assurance Algorithm

A Personalized Pagerank with Accuracy Assurance Algorithm is a Personalized PageRank Algorithm that is based on a relevance measure.

• Context:
  • It was first developed and implemented by Fujiwara et al. (2012).
• Example(s):
  • …
• Counter-Example(s):
  • PPRGo Algorithm,
  • Edge-Weighted Personalized PageRank Algorithm,
  • Node-Weighted Personalized PageRank Algorithm.
• See: Random Walk Process, Random Graph Walk, PageRank Algorithm, PageRank Value, Random Walk NLP Algorithm, Random Walk Image Processing Algorithm.

---

---

References

2012

• (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 doi:10.1145/2339530.2339538.
  • QUOTE: 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.

---