This documents the development version of NetworkX. Documentation for the current release can be found here.


generate_random_paths(G, sample_size, path_length=5, index_map=None)[source]

Randomly generate sample_size paths of length path_length.

GNetworkX graph

A NetworkX graph


The number of paths to generate. This is R in [1].

path_lengthinteger (default = 5)

The maximum size of the path to randomly generate. This is T in [1]. According to the paper, T >= 5 is recommended.

index_mapdictionary, optional

If provided, this will be populated with the inverted index of nodes mapped to the set of generated random path indices within paths.

pathsgenerator of lists

Generator of sample_size paths each with length path_length.



Zhang, J., Tang, J., Ma, C., Tong, H., Jing, Y., & Li, J. Panther: Fast top-k similarity search on large networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Vol. 2015-August, pp. 1445–1454). Association for Computing Machinery.


Note that the return value is the list of paths:

>>> G = nx.star_graph(3)
>>> random_path = nx.generate_random_paths(G, 2)

By passing a dictionary into index_map, it will build an inverted index mapping of nodes to the paths in which that node is present:

>>> G = nx.star_graph(3)
>>> index_map = {}
>>> random_path = nx.generate_random_paths(G, 3, index_map=index_map)
>>> paths_containing_node_0 = [random_path[path_idx] for path_idx in index_map.get(0, [])]