<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

Published Online: Mar 31, 2016

Page range: 29 - 43

Received: Jan 27, 2015

Accepted: Jan 30, 2016

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

Keywords
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

Published Online: Mar 31, 2016

Page range: 29 - 43

Received: Jan 27, 2015

Accepted: Jan 30, 2016

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

KeywordsGraph, 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.

Keywords
Graph, Monte Carlo, PageRank, Random Walk