2
$\begingroup$

Give a sparse random graph $G=(V,E)$, every edge $(u,v)\in E$ is associated with a weight $w(u,v)$. We assume each $w(u,v)$ is geometrically distributed with parameter $p_{u,v}$. The weight of a path from $u_0$ to $u_n$, i.e. $path(u_0,u_n)=(u_0, u_1, \cdots, u_n)$, is defined as $w(path(u_0,u_n))=w(u_0,u_1)+w(u_1,u_2)+\cdots + w(u_{n-1},u_n)$, which is also a random variable (the summation of a group of geometrically distributed random variables).

For any two nodes $x,y$ in $V$, there are two kinds of distance:

-1. $d_1 (x,y) = \mathbf{E}\min\{path(x,y)\}$, namely, first we find the shortest path from $x$ to $y$, then take expectation of the shortest path as the distance from $x$ to $y$.

-2. $d_2 (x,y)= \min\{\mathbf{E}path(x,y)\} $, namely, first we use $\mathbf{E}w(u,v) = 1/p_{u,v}$ as the weight of every edge, then find the shortest path.

Is there any work to describe the gap between $d_1 (x,y)$ and $d_2 (x,y)$? In what kinds of cases, $|d_1 (x,y)-d_2 (x,y)|$ is very small? As there is no additional topology on $G$, it is very hard for me to imagine the quantitative relationship between them. Thanks in advance for your help.

$\endgroup$
1
  • $\begingroup$ well, on a tree they are the same :-) In general (e.g., in the standard square lattice) they are very different. So I don't expect that with no further assumptions on $G$ you can say something meaningful. $\endgroup$ Nov 7, 2015 at 22:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.