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 lengthpath_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 lengthpath_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 lengthpath_length
drawn fromG
:>>> 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]]