Note

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

networkx.algorithms.similarity.generate_random_paths

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

Randomly generate sample_size paths of length path_length.

Parameters
GNetworkX graph

A NetworkX graph

sample_sizeinteger

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.

Returns
pathsgenerator of lists

Generator of sample_size paths each with length path_length.

References

1(1,2)

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. https://doi.org/10.1145/2783258.2783267.

Examples

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, [])]