Probability $u, v$ are connected in a random graph model There is a random graph problem. Given an undirected graph $G(V,E)$ associated with $p_{uv}$ to denote the probability there is an edge between $u$ and $v$ ($p_{uv}$ are independent, maybe different for different $(u,v)$ ).
Given two nodes $x$, $y$. Ask what's the probability $x$ and $y$ are connected?
Can we compute it in polynomial time?
There is an example:
there are three nodes, A, B, C. $p_{AB} = 0.3, p_{AC} = 0.5, p_{BC} = 0.4.$ It means that, with the probability 0.3, A and B have an edge. With the probability 0.5, B and C have an edge, and so on. So, if we want to compute the probability where A and C are connected, we can conclude it is 0.5 + 0.5*0.3*0.4 = 0.56.
 A: The random graph model you describe is exactly the "random inhomogeneous graph model" studied in [0].
In particular your question reduces to "are $u$ and $v$ in the same component", which when there is a giant component is quite close to the question "do $u$ and $v$ belong to the giant component". 
You can check section 3.5 in [0], "distance between vertices", that gives upper and lower bounds on these probabilities.
If you want the exact probability, it seems unlikely that it can be computed in polynomial time, or anything significantly more efficient than enumerating all graphs and summing the probabilities of those where $u$ and $v$ are connected. 
[0] Bela Bollobas, Svante Janson, Oliver Riordan, "The phase transition in inhomogeneous random graphs", http://arxiv.org/abs/math/0504589
A: So $x$ and $y$ are connected with a path of length 1 with probability $p_{uv}$. Then $x$ and $y$ are connected with a path of length 2 with probability $p_{uv}^2$,  and so on...
So $$ P(X)=\sum_{k=1}^mp_{uv}^k=\frac{p_{uv}^{m+1}-1}{p_{uv}-1},$$
where $m$ is a path of maximum length in $G$. I am not sure this is correct because I am not counting all the paths of length $k$, just calculating the probability of a path of length $k$ existing.
Anyone with a better idea or modification to this idea out there?
