<abstract xmlns="http://www.w3.org/1999/xhtml"><p>This paper describes a novel Monte Carlo based random walk to compute PageRanks of nodes in a large graph on a single PC. The target graphs of this paper are ones whose size is larger than the physical memory. In such an environment, memory management is a difficult task for simulating the random walk among the nodes. We propose a novel method that partitions the graph into subgraphs in order to make them fit into the physical memory, and conducts the random walk for each subgraph. By evaluating the walks lazily, we can conduct the walks only in a subgraph and approximate the random walk by rotating the subgraphs. In computational experiments, the proposed method exhibits good performance for existing large graphs with several passes of the graph data.</p></abstract>

This paper describes a novel Monte Carlo based random walk to compute PageRanks of nodes in a large graph on a single PC. The target graphs of this paper are ones whose size is larger than the physical memory. In such an environment, memory management is a difficult task for simulating the random walk among the nodes. We propose a novel method that partitions the graph into subgraphs in order to make them fit into the physical memory, and conducts the random walk for each subgraph. By evaluating the walks lazily, we can conduct the walks only in a subgraph and approximate the random walk by rotating the subgraphs. In computational experiments, the proposed method exhibits good performance for existing large graphs with several passes of the graph data.

An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC

National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

Foundations of Computing and Decision Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

This paper describes a novel Monte Carlo based random walk to compute PageRanks of nodes in a large graph on a single PC. The target graphs of this paper are...

An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC

Publié en ligne: 31 mars 2016

Pages: 29 - 43

Reçu: 27 janv. 2015

Accepté: 30 janv. 2016

DOI: https://doi.org/10.1515/fcds-2016-0002

Mots clés
Graph, Monte Carlo, PageRank, Random Walk

© 2016 Tomohiro Sonobe, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC

Publié en ligne: 31 mars 2016

Pages: 29 - 43

Reçu: 27 janv. 2015

Accepté: 30 janv. 2016

DOI: https://doi.org/10.1515/fcds-2016-0002

Mots clésGraph, Monte Carlo, PageRank, Random Walk

© 2016 Tomohiro Sonobe, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
Graph, Monte Carlo, PageRank, Random Walk