Can I read Computing personalized PageRank quickly by exploiting graph structures on EtoBox?

Computing personalized PageRank quickly by exploiting graph structures by Takanori Maehara; Takuya Akiba; Yoichi Iwata; Ken-ichi Kawarabayashi is a Computer Science article available to read on EtoBox.

What is Computing personalized PageRank quickly by exploiting graph structures about?

We propose a new scalable algorithm that can compute Personalized PageRank (PPR) very quickly. The Power method is a state-of-the-art algorithm for computing exact PPR; however, it requires many iterations. Thus reducing the number of iterations is the main challenge. We achieve this by exploiting graph structures of web graphs and social networks. The convergence of our algorithm is very fast. In fact, it requires up to 7.5 times fewer iterations than the Power method and is up to five times faster in actual computation time. To the best of our knowledge, this is the first time to use graph structures explicitly to solve PPR quickly. Our contributions can be summarized as follows. 1. We provide an algorithm for computing a tree decomposition, which is more efficient and scalable than any previous algorithm. 2. Using the above algorithm, we can obtain a __core-tree decomposition__ of any web graph and social network. This allows us to decompose a web graph and a social network into (1) the __core__ , which behaves like an expander graph, and (2) a small tree-width graph, which behaves like a __tree__ in an algorithmic sense. 3. We apply a direct method to the small tree-width graph

Who reads Computing personalized PageRank quickly by exploiting graph structures?

Author

Takanori Maehara; Takuya Akiba; Yoichi Iwata; Ken-ichi Kawarabayashi

Publisher

ACM

Published

2014

Language

EN

Field

Computer Science (Physical Sciences)