Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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!