support `target` parameter for `generate_random_paths`

[Schefflera-Arboricola]

          Also, we can consider adding a `target` (ending node) parameter here too. btw, not a blocker for this PR :)

Originally posted by @Schefflera-Arboricola in #8002 (comment)

assumed pre-requisites:

• know how generate_random_paths works? --> you can read the documentation to understand this.

[LorentzFactor]

Is this particularly easy to do? It seems hard to constrain the end/target node because of the random nature of the walk. The dependence of the next step on the "future" would also lead to it no longer being a Markov process, I believe. That's pretty unusual for a random walk algorithm - so might warrant some consideration before implementing.

[dschult]

I don't think there is any dependence of the steps on where the walk ends. You just use the probabilities for each step... and you stop when that walk hits the target. I can imagine some very long walks though... :) Each walk is still very much Markovian.

[LorentzFactor]

Ah, yeah, did not consider the infinite case! And even in the case where we are concerned with walks of fixed length $T$ like in the panther paper, I'm now thinking it's Markovian, albeit not time-homogenous anymore.

Getting back to implementing target, if source is not specified, we could just 'reverse' the direction of time, and walk backward from the target node using the transposed transition matrix. So that doesn't seem too bad. :)

Implementing it still seems rather tricky to me if we need to support the case where source can also be specified. I can't think of any smarter way to do it than computing all paths of length $T$ between source and target, using the transition matrix to calculate their probabilities in the broader space of all paths of length $T$ starting from source, and normalizing.

[dschult]

It's actually fairly simple to find with a source and a target -- just don't use any mathematical equations :) Start at the source and pick neighbors randomly the way you always do. Keep going until you hit the target node. Yield the resulting path. That's the method folks used before Markov figured out how to "do the math" to compute long run probabilities. This is just a straight forward monte carlo simulation.

[LorentzFactor]

Ah, okay! So, in our case we're looking for paths specifically of exact length $T$, with target specifically being the $T$-th node in the path.

If I'm understanding correctly, this means there are two changes to be made:

1. Check if a path of exact length $T$ exist between source and target, and raise some exception if not.

2. We also currently perform a fixed number of random walks. To add target, and ensure we still return sample_size paths, we'll need to modify this to check if the final node of the path is indeed target, and if so, add the path to our samples, check the length, and break out of the loop once sample_size has been reached.

[amcandio]

Given that this is harder than users might realize, we should state it in the docs

[gulshan-123]

Clearly only target node given is symmetrical to only source node given.
If both source and target nodes are given, here is another method which involves some preprocessing in which no sampling will be wasted:

Let P be an n x n transition matrix, and define for each node v and remaining steps k the probability:

$$ h_k (v) = \text{Pr(reach target in exactly k steps | start at v)} $$

Compute h_k(v) using Dynamic Programming:

$$ h_0(v) = 1 \text{ for target node } v \text{, else 0} $$

$$ h_{k+1}(v) = \sum P[v][u] \cdot h_k(u) \text{ for each } u \text{ such that } v \rightarrow u \text{ is an edge} $$

Then sampling is done with weight (at node v, k steps are left):

$$ \text{Pr}(u | v, \text{must hit target in k}) = \frac{P[v][u] \cdot h_{k-1}(u)}{h_k(u)} $$

Note: if no path of length T exists, h[T, source] = 0. We may then raise error..

[rossbar]

There's a nice discussion here about how this might be done, but I don't think the why has been sufficiently addressed. Is this something that really a feature that needs to be added directly to generate_random_paths, or something better served by using the existing functionality?

For example, if I want to generate random walks (as noted in previous discussions, this function's name is a bit miscast) with a specific target I can do something like:

>>> G = nx.star_graph(10)
>>> walks = nx.generate_random_paths(G, sample_size=1000, path_length=6, source=1)
>>> target_node = 5
>>> targeted_walks = [p for p in gen if p[-1] == target_node]
>>> len(targeted_walks)  # random when unseeded, expect ~10% of sample_size
89

The above formulation gives the number of walks for a given sample size. If instead a user wanted a fixed number of random walks (and how many iterations it takes to achieve this), they could do something like:

>>> G = nx.star_graph(10)
>>> walks = nx.generate_random_paths(G, sample_size=1000, path_length=6, source=1)
>>> target_node = 5
>>> desired_num_walks = 3
>>> rws = []
>>> for sample_no, walk in enumerate(walks, start=1):
...     if walk[-1] == target_node:
...         rws.append(walk)
...     if len(rws) == desired_num_walks:
...         break
>>> rws
[[1, 0, 5, 0, 7, 0, 5], [1, 0, 4, 0, 6, 0, 5], [1, 0, 8, 0, 10, 0, 5]]
>>> sample_no
9

I chose star_graph on purpose to illustrate one of the pitfalls of "targeted" random walks. If you start on any of the leaf nodes of the star, then an odd number of steps in the walk will always land on the root node¹. In other words, for this specific graph half of all n-length walks are not possible!

>>> walks = nx.generate_random_paths(G, sample_size=1000, path_length=5, source=1)
>>> [p for p in walks if p[-1] == 5]
[]

Knowing that there's a path between the source and target nodes doesn't guarantee that there is a walk of a specific length between them!

IMO, adding a target option to this function is not necessarily a good idea. I think forcing users to be explicit about what exactly it is they want (examples of which above) is much clearer and in the end would be less error-prone.

Footnotes

1. And vice-versa: if you start on the root node, all even-length walks will end on the root node. ↩

[Maninder-sd]

@rossbar I think this a good point. It might be easier to just try sampling random walks and filtering out the ones that satisfies the users requirements. If the graph has more nodes, the user could sample more times and this might be faster than computing probabilities. However, it might be that there are only 1 or 2 (or 0 paths as you mention!) path from source to target of the specified length, say 100 long. In these exceptional cases, a very small number of the samples will meet users' requirements and users would have to guess what a good sample size should be. I think that it is beneficial to have code that can calculate the probabilities and also tell you if there is no such possible path. It could be code that is independent from the generate_random_paths function.

(I've never used the generate_random_paths function in a project before so I might not know what is the most common use case. This issue seemed doable for me so I gave it a shot.)

[rossbar]

We now have the random_walks generator to serve as the primary interface for generating random walks. I'm going to close this to discourage activity on generate_random_paths which is slated for some form of deprecation/renaming/being-made-private anyways.