# Probability of two vertices being connected in a random graph

Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of undirected path existence between any two vertices $v$ and $u$ in such a graph? In particular I'm interested in relatively efficient algorithm for estimating this probabilities for all pairs of vertices.

This could be seen as transforming each link in this graph into undirected edge and then asking for being in the same connected component.

Although this problem seems to be quite common I could find it's instances only for some particular random graph models which didn't helped me.

I managed to get the probability of directed path existence, probably this could be used somehow, but definitely it's far from the answer since such a chain v -> x <- u is connected in my terms but there is no directed path between $v$ and $u$.

• You are probably aware that the keyword is "Percolation" --I mention it since you didn't. In Percolation theory it is customary to assume independence (distinct arcs being open are independent events). You are assuming it as well? Aug 2 '13 at 10:48
• I'm not sure that I understood you correctly. Do you mean that links are generated independently? If so, then yes, I should mention this in my question
– sbos
Aug 2 '13 at 11:48
• For clarification: Are you interested in the probability of directed path (you wrote undirected in the description)? If you are interested in directed path, I think you need the random graph to be connected, at least with some high probability. In the Erdos-Renyi case, that would mean that you need to have identical (and undirected) $a_{uv} \ge \frac{log N}{N}$. I think you could get, at the very least, good hints about how to do this for non-identical (undirected) $a_{uv}$ by say looking up [win.tue.nl/~rhofstad/NotesRGCN.pdf](R. van der Hofstad's notes on Random Graphs). Aug 17 '13 at 6:13

How about the Monte Carlo method? Generate $k\gg 1$ graphs at random, count how many of them have a path from $u$ to $v$, then divide by $k$.