# Reachability queries on uncertain graphs

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the likelihood that they lie in the same connected component.

If the only possible scores were discrete $0$ and $1$, then this problem reduces to the connected components listing or graph reachability problem. Is there any work on uncertain graphs that can solve this problem?

• Welcome to CS.SE! The problem is not well-defined. You haven't given us any basis for assigning an output score, or how the outputs should relate to the inputs; we could assign a score of 0.42 to every pair of vertices, and that would meet all of your requirements.
– D.W.
Mar 27 '17 at 17:37
• I suspect what you're going to need to do is to characterize the probabilistic process underlying this. Presumably, there is some random process that determines which vertices are in the same cluster; and some random process that describes how input scores (on edges) are generated, depending on the clustering. What are those processes? You'll need to figure that out and describe it in the question; with that information, one can start to consider algorithms. Until then, we can't answer your question without that kind of information.
– D.W.
Mar 27 '17 at 17:38
• @D.W.: It is indeed an open-ended problem. We are free to define reasonable metrics for similarity. I want to see what literature exists for DSUs on weighted graphs. Mar 29 '17 at 18:51
• I think that you should change your question into either 1. formally define the probability of the vertices being in the same set in terms of the initial given vertex probabilities and ask for an efficient algorithm to compute this or 2. Ask for an useful formalization of the probability the vertices are in the same set given the initial vertex probabilities. Right now, it seems this question is asking both, which is simply not easily answerable in this format. Just question 1 is perfectly answerable in this format and although question 2 is a bit more vague, it should be doable. Mar 31 '17 at 16:50
• Also, "But, I am not sure what literature exists for probabilistic graphs" is not a question. It is better to be explicit in your question about whether you mainly want a reference to some literature (the tag 'reference-request' may help) or simply some possible 'original' ideas. Mar 31 '17 at 16:51

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem: