diameter of a graph with random edge weights

Question

Given a weighted directed graph $G=(V,E, w)$, suppose we generate a new graph $G'=(V,E,w')$ with the same vertices and edges, but now letting the weight of edge $(i,j)$ be an exponential random variable with mean $w_{ij}$. My question is: what is the expected diameter of $G'$?

Why I'm interested in this: I was intrigued by the observation that the expected diameter of $G'$ can be quite different from the diameter of $G$. Indeed, consider the following example: define $G$ by taking the complete graph $K_{n+1}$, picking an arbitrary vertex $a$, and assigning weight $n$ to any edge incident on $a$, and weight $1$ to every other edge. Then, the diameter of $G$ is $n$. On the other hand, the expected diameter of $G'$ is O(1) since we can expect one of the edges incident on $a$ to have small weight.

Answer 1

For the special case of the complete graph $K_n$ which you mention in your post, Svante Janson answered your question in this paper; the answer is that the weighted diameter grows like $3 \log n$ in probability.

There is also some very nice work by Bhamidi et. al on this question when the underlying graph is the giant component of Erdos--Renyi random graph $G_{n,c/n}$ with $c>1$ fixed, although they only prove lower bounds. Amini et. al. (link is to a PDF) have found the asymptotics of the weighted diameter for random graphs with a given degree sequence, under some conditions, for degree sequences which in particular result in graphs which are with high probability connected. Ding et.al. (Theorems 3.7 and 3.8 of the linked paper) prove quite refined estimates, and tail bounds, for the weighted diameter of random $d$-regular graphs, for $d \geq 3$. (Since random regular graphs are a special case of random graphs with a given degree sequence, the results of Amini et. al. and Ding et.al. have some overlap).

There is also related work, on the hopcount of randomly weighted graphs. The hopcount is what you get if you count the number of edges on the smallest-weight path. The primary interest of Bhamidi et. al. in fact seems to be hopcounts rather than weighted path lengths.

Answer 2

The diameter is defined as $$d(G') = \sup_{x,y \in G} \inf_{\gamma} \sum_{e \in \gamma} w_{e},$$ where the infimum is over all paths $\gamma$ connecting $x$ to $y$, and the sum is over the edges $e$ which $\gamma$ crosses. The graph structure is very crucial to this problem. If the graph is very connected (as in your example), then the diameter is essentially the maximum value of the variables $\{w_i\}$. A large fluctuation of a single $w_i$ will cause the diameter to be very large.

On the other hand, if you're dealing with something more like a lattice (e.g., a large, finite subset of $\mathbb Z^2$), then the diameter is a combination of many independent random variables. Large fluctuations of any single variable will be muted and not affect the diameter much, and limit theorems will apply. A variant of Kingman's subadditive ergodic theorem will show that $$d(G') \sim d(G).$$

Questions like this are very much in the realm of first-passage percolation. Check out this survey by Howard, as well as this one by Blair-Stahn on the arXiv.