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.

  • $\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$ – ofer zeitouni Nov 7 '15 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.