Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum path between nodes (if there is more than one minimum path we choose one arbitrarily). Then the total traffic in $G_{n}$ is equal to $N(N-1)/2$ where $N=N(n)=|G_{n}|$.

Given a node $v\in G_{n}$ we define $T_{n}(v)$ as the total traffic generated in the graph passing through $v$. In other words, $T_{n}(v)$ is the sum off all the geodesic paths in $G_{n}$ which are carrying traffic and contain the node $v$.

Let $T(G_{n})$ be the maximum load in the graph. More precisely, $$ T(G_{n})=\max_{v\in G_{n}} \{T_{n}(v)\}. $$

As Lukasz pointed out this question can be reformulated without talking about traffic. For instance, for each two vertices we choose a geodesic that connects them and then define $T_{n}(v)$ as the number of geodesics paths that pass through the node $v$.

My question is:

  • What can we say about the rate of growth of $T(G_{n})$?

  • Is there anything known in this direction?

  • 1
    $\begingroup$ Are the loads and traffic actually necessary to formulate the problem? Could you not say that for each two vertices you choose a geodesic which connects them and then you define $T_n(v)$ as the number of geodesics which pass through $v$? Also, to make the questions more focused, maybe you could define $T(G_n)$ as the minimum over (choices of geodesics) of the maximum over (vertices of $G_n$) of $T_n(v)$? $\endgroup$ – Łukasz Grabowski Dec 11 '11 at 14:30
  • $\begingroup$ Lukasz: Yes you could also define the problem in the way you are saying. Do you know if somebody has worked in this question? $\endgroup$ – ght Dec 11 '11 at 16:00
  • $\begingroup$ I don't; I can only suggest you might try to reformulate the question in the way I suggested because then it sounds - to me - like a fairly natural question to ask, and there are quite a few people on mathoverflow who should know if such a question about expanders has or hasn't been asked before. $\endgroup$ – Łukasz Grabowski Dec 12 '11 at 0:00
  • 1
    $\begingroup$ maybe you could also change the title to something more specific, like "number of geodesics passing through a vertex in an expander" $\endgroup$ – Łukasz Grabowski Dec 12 '11 at 0:05

My short answer: I think not much is known. But: here is the state of the art on related problems, as far as I am aware.

Aldous and Bhamidi consider the following model. Place independent exponential edge weights on the edges of the complete graph $K_n$; we view the weights as edge lengths. Then, for each pair $u,v$ of vertices, place a constant flow between them on the shortest path from $u$ to $v$. For each edge $e$, write $F_n(e)$ for the total flow along edge $e$ in the resulting network. Then for each fixed $z > 0$, as $n \to \infty$, \[ \frac{1}{n} \#\{e: F_n(e) > z\log n\} \to \int_0^{\infty}\mathbb{P}(W_1W_2e^{-u} > z)~du, \] where $W_1$ and $W_2$ are independent exponentials. (In fact, the paper proves a more detailed distributional convergence result.) In particular, typical edge congestion is $O(\log n)$; but the paper does not address maximum edge congestion. The paper also addresses vertex congestion (more directly linked to your question), showing a similar convergence result but with a more complicated term on the right-hand side of the convergence. As in the edge case, however, maximum vertex congestion is not treated, only typical congestion.

What follows is less relevant as it relates to global strategies for minimizing congestion, rather than greedy routing between nodes. I'm posting it anyway in case it's useful.

Alan Frieze has a survey on disjoint paths in expander graphs which may be of interest. Theorems 4 and 5 of that survey are results of Broder, Frieze and Upfal, which imply that in an expander, any set of at most $c n/\log^2 n$ pairs of vertices can be connected by disjoint paths, and that every pair can be connected by a path in such a way that the total congestion is $O(n \log n)$.

Finally, for a particular class of random expanders, something can be said about a fractional version (flows rather than paths; again, this allows global optimization). Given a connected, undirected graph $G=(V,E)$, a uniform flow of volume $\phi$ on $G$ is a collection $F$ of flows, one for each ordered pair $(v,w)$ of vertices of $G$, each having volume $\phi$. Given $f \in F$ and $e \in E$, write $f(e)$ for the flow through edge $e$ in $f$ (ignore direction so this is always non-negative). Then write \[ \chi(F)=\max_{e \in E} \sum_{f \in F} f(e) \] for the maximum flow across any edge of $G$, when all flows of $F$ are simultaneously active

Aldous, Mcdiarmid, and Scott have proved the following. Fix a non-negative random variable $C$ with $\mathbb{E}(C) < \infty$, and take G_n to be the complete graph $K_n$ each of whose edges $e$ is weighted with an independent copy $C_e$ of $C$. Let $\phi_n$ be the largest value such that there exists a uniform flow $F$ of volume $\phi_n$ on $G$ such that \[ \sum_{f \in F} f(e) \le C_e \] for all $e \in E(K_n)$. Then there is a positive constant $\phi_*$ such that $\phi_n \to \phi_*$ in probability.

Note that if $C$ takes some fixed value $M$ with probability $p$, and is $0$ with probability $1-p$, this is equivalent to requiring maximum congestion $\le M$ on the random graph $G_{n,p}$. Thus, this setting includes (edge) congestion-type bounds on at least some expander-like graphs.


If you take a sequence of really good expanders and add an edge between two vertices which are very far (add loops or double some edges to keep the graph regular if this is importnat), this will force a lot of traffic to go through this extra edge. My guess is that this will make $T(G_n) > \lambda diam(G_n)^2 \approx \log |G_n|^2$. It also seems that a counting argument shows that one has an upper bound of the same type.

  • 2
    $\begingroup$ Actually, it is not difficult to see that for any graph $G$ (expander or not) $T(G)\geq |G|-1$ and therefore your lower bound is too weak. This also shows that your proposed upper bound cannot work. $\endgroup$ – ght Dec 12 '11 at 14:49
  • $\begingroup$ Sorry I've messed my estimate, this construction gives significantly more geodesic paths going through the extra edge -- I think the number is $T(G_n) > n^{4/3}$ but I might be wrong.. $\endgroup$ – kassabov Dec 12 '11 at 23:41
  • 3
    $\begingroup$ Can you give some indication at least of why do you think this is the case? $\endgroup$ – ght Dec 13 '11 at 3:21

Well, from the way the problem was defined, $T(G_n)$ is at least $\theta_k(n \log n)$. Indeed, there are $\theta(n^2)$ paths that have average length $\theta(\log n)$ [I can elaborate if needed] passing through $n$ vertices.

Now the upper bound can be much larger. It can be as large as $\theta(n^2)$ and here is a proof (sketch). Indeed, first take a $k$-regular expander, and (to be really stupid) replace each edge $\{u,v\}$ with a path $P$ of (say) $(k-2)D$ vertices (for some large $D \in O(1)$) and put $D$ $k-2$-complete graphs on $P_{u,v}$ (so the first $k-2$ vertices of $P_{u,v}$ are all connected by a complete graph, then the next $k-2$ vertices, and so on and so forth. The resulting graph $G'$ is still $k$-regular, still an expander (with weakened expansion coefficients. The diameter is about a factor of $\frac{D}{k}$ larger though, at least $\frac{D}{k}\log_{k-1} n$ [all $k$-regular graphs have diameter at least $\log_{k-1} n$]. Then next let $Y$ be a complete $k$-ary tree added to $G'$. So now the diameter is reduced to about $2 \log_{k-1} (k-2)k^2 n$, and $\theta(n^2)$ shortest paths go through the root of $Y$. So here $T_n$ is close to the trivial upper bound of $n^2$.

However, the good news of expanders is that if a bound on the congestion is required AND you are willing to settle for paths only a constant factor larger than the shortest path, then you are in luck. More precisely, the complete graph $K_n$ can be embedded into an expander with congestion only $O(n \log n)$.

ETA: Just saw the time and date that this question was posted. Anyway I hope this answer is still useful to someone!


Your Answer

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

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