The most efficient way of doing it is to use the transition matrix of a graph in CSR sparse format and, of course, there is a great package for that: csrgraph (pip install csrgraph
). Here is how you can do it:
import csrgraph as cg
import numpy as np
G = cg.csrgraph(G, threads=12)
node_names = G.names
walks = G.random_walks(walklen=10, # length of the walks
epochs=100, # how many times to start a walk from each node
start_nodes=None, # the starting node. It is either a list (e.g., [2,3]) or None. If None it does it on all nodes and returns epochs*G.number_of_nodes() walks
return_weight=1.,
neighbor_weight=1.)
The result is an array of size (epochs*number_of_nodes, walklen). More info on the function and its parameters can be found here.
On a graph of 2,130 nodes and 36,560 edges, it took me 0.5 seconds to generate 213,000 paths of length 20 with the snippet above:
>>> array([[ 0, 4, 1678, ..., 48, 728, 30],
[ 1, 57, 102, ..., 947, 456, 240],
[ 2, 156, 177, ..., 175, 1363, 539],
...,
[2127, 1655, 1656, ..., 1655, 1656, 2127],
[2128, 4, 1432, ..., 111, 32, 162],
[2129, 4, 521, ..., 1280, 180, 608]], dtype=uint32)
walks.shape
>>> (213000, 20)
The node names can be mapped back to their original format using the snippet below or other similar methods:
walks = np.vectorize(lambda x: node_names[x])(walks) # map to original node names
NOTE: This package does much more than just random walks, you might want to check their GitHub repo here