fastwalk
A multi-thread implementation of node2vec random walk.
Introduction
This repository provides a multi-thread implementation of node2vec random walk, with alias table based on LRU cache, it can process with limited memory usage, so that walking through a giant graph on a single machine can be possible.
Tested for a graph that contains 23 thousand nodes and 23 million edges, with parameter
--walk_length=80 --num_walks=10 --workers=20 --max_nodes=50000 --max_edges=100000 --p=10 --q=0.01
only 11GB memory used, and finished walking within 2 hours.
Visit https://blog.razrlele.com/p/2650 for more.
Prerequisites
- g++ 4.8+.
Usage
Prepare input data with format as below:
node1 node2 [edge_weight]
node2 node3 [edge_weight]
...
edge_weight is 1.0 as default.
compile:
make
run with:
./fastwalk --edge_list <path_to_edgelist> --output <path_to_output> --delimiter space --p 10 --q 0.01 --max_nodes 50000 --max_edges 50000 --workers 10
If you wanna walk faster, add more workers, if you wanna run with less memory consumption, decrease max_nodes or max_edges, checkout more information with
./fastwalk --help
Reference
node2vec: Scalable Feature Learning for Networks.
Aditya Grover and Jure Leskovec.
Knowledge Discovery and Data Mining, 2016.
https://arxiv.org/abs/1607.00653
Acknowledgements
I would like to thank Yuanyuan Zhu for discussions on the performance of node2vec, and thanks to Weichen Shen for his great work.