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

networkx.algorithms.similarity.panther_similarity Simple Paths