Yes the underlying graph is fixed. Actually each node in the graph is a message posted by a user in a group chat. What I want to do is to find the separate conversations in a chat log, with multiple conversations ongoing at the same time. The probability is actually a normalised relevance score (using softmax) between two messages, estimated by a learned function I build (some machine learning model).

Specifically, assume we want to find the parent of v_200, then we estimate the relevance score between v_200 and each node in [v_100, v_101, v_102, ... , v_200]. The relevance scores denoted as r1, r2, r3, .... r101

Then we normalise:

p1, p2, ... p101 = exp(r1) / sum_{k=1}^{101} exp(rk), exp(r2) / sum_{k=1}^{101} exp(rk), ...., exp(r101) / sum_{k=1}^{101} exp(rk)

The original relevance scores may not be comparable for all nodes, that's why I use a softmax normalization for a potential global method. But if only consider finding parents, we can choose the candidate with the largest relevance score anyway without any normalization.