Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks for the references! –  alex Sep 1 '10 at 17:54

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.

share|improve this answer
1  
Thanks for the references; will check them out. In the very connected case, my intuition says that the opposite of your statement is true: even if one $w_{ij}$ is large, the existence of many paths between any two vertices will insure that the diameter is not strongly affected. –  alex Jun 16 '10 at 5:25
    
Oops, you're absolutely right. It should be the opposite of what I said: the diameter should cluster on small values. Say you want to connect x to y. There's the one-edge path which connects them, and there are O(|G|) two-edge paths. There is a very high chance that one of them will have a very small weight. –  Tom LaGatta Jun 16 '10 at 5:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.