generate_random_paths#

generate_random_paths(G, sample_size, path_length=5, index_map=None, weight='weight', seed=None, *, source=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.
weightstring or None, optional (default=”weight”): The name of an edge attribute that holds the numerical value used as a weight. If None then each edge has weight 1.
seedinteger, random_state, or None (default): Indicator of random number generation state. See Randomness.
sourcenode, optional: Node to use as the starting point for all generated paths. If None then starting nodes are selected at random with uniform probability.

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

The generator yields sample_size number of paths of length path_length drawn from G:

>>> G = nx.complete_graph(5)
>>> next(nx.generate_random_paths(G, sample_size=1, path_length=3, seed=42))
[3, 4, 2, 3]
>>> list(nx.generate_random_paths(G, sample_size=3, path_length=4, seed=42))
[[3, 4, 2, 3, 0], [2, 0, 2, 1, 0], [2, 0, 4, 3, 0]]

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.wheel_graph(10)
>>> index_map = {}
>>> random_paths = list(
...     nx.generate_random_paths(G, sample_size=3, index_map=index_map, seed=2771)
... )
>>> random_paths
[[3, 2, 1, 9, 8, 7], [4, 0, 5, 6, 7, 8], [3, 0, 5, 0, 9, 8]]
>>> paths_containing_node_0 = [
...     random_paths[path_idx] for path_idx in index_map.get(0, [])
... ]
>>> paths_containing_node_0
[[4, 0, 5, 6, 7, 8], [3, 0, 5, 0, 9, 8]]