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?