2
$\begingroup$

Betweenness, roughly speaking, measures how many times a particular node or edge in a graph is part of the shortest path, when counting paths among all pairs of nodes. For nodes, it's easy to see that a star graph forces the central node to have a maximum betweenness as it lies between every pair of nodes.

I'm trying to determine if there exists a graph such that a particular edge is on every shortest path (and therefore has maximum edge betweenness). Obviously, for an undirected graph, there are a maximum of $\frac{n(n-1)}{2}$ shortest paths. But considering some small examples, I was unable to design a graph such that any edge actually achieved this max. Is such a (weighted) graph possible (by proof or construction), or can we find the actual maximum betweenness?

My use case is normalizing these edge betweenness scores. I could just use the number of shortest paths (which is what networkx and I suspect other implementations do), but if we can figure out what the actual max is (or some demonstrable estimates), I'd like to use that.

Edit: To clarify, I'm considering a weighted graph (possibly with zero weights allowed, though practically that's less interesting). But analyzing an unweighted graph may of course still be helpful.

$\endgroup$
2
  • 1
    $\begingroup$ If the graph contains any other edge, the two vertices of that other edge will have a shortest path between them that does not involve your edge. So the only graph that achieves the maximal edge betweenness is $K_2$. $\endgroup$ – Jaap Scherphuis Mar 10 at 16:08
  • $\begingroup$ @JaapScherphuis, I think that only applies if you have an unweighted graph. One can arrange three vertices (say, $ABC$) in a triangle with edge weights, $ AB, BC, CA = (1,1,3)$. Then the shortest path between $A$ and $C$ is $ABC$ rather than $AC$. $\endgroup$ – Dan Van Boxel Mar 10 at 19:42
1
$\begingroup$

Suppose that a shortest path from vertex $v$ to vertex $w$ in the graph uses edge $xy$: let's say the path goes $(v, \dots, x, y, \dots, w)$. Then distances from $v$ are strictly increasing along the path, and distances from $w$ are strictly decreasing: in particular, $d(v,x) < d(v,y)$ and $d(w,x) > d(w,y)$.

This means that all shortest paths using edge $xy$ must start at a vertex closer to $x$ than to $y$, and end at a vertex closer to $y$ than to $x$. If there are $n_x$ vertices of the first type, and $n_y$ of the second, then at most $n_x \cdot n_y$ pairs of vertices have a shortest path using edge $xy$.

With the constraint $n_x + n_y \le n$ and $n_x, n_y \ge 0$, $n_x \cdot n_y$ is maximized at $\lfloor \frac{n^2}{4}\rfloor$ when $n_x = n_y = \frac n2$ (for even $n$) or when $\{n_x, n_y\} = \{\frac{n-1}{2}, \frac{n+1}{2}\}$ (for odd $n$).

This bound is achievable for all $n$, by letting $xy$ be the only edge between two connected subgraphs, one with $n_x$ vertices and one with $n_y$ vertices.

$\endgroup$
2
  • $\begingroup$ This type of graph with a bottleneck does seem like the "obvious" representation of maximum edge betweenness. One potential wrinkle is if we allow zero-weight edges. Then $d(v,x) \leq d(v,y)$, meaning there might be a "skip". But I think then that other path might be the shortest (or tied for shortest, which would divide the score). Thanks! $\endgroup$ – Dan Van Boxel Mar 10 at 19:41
  • $\begingroup$ I did not realize that you allow weighted edges; with those, we indeed need to be more careful. If there are $n_z$ vertices at equal distance from $x$ and $y$, then I think at most half the shortest paths from such a vertex use edge $xy$, so the edge's betweenness is at most $n_x n_y + \frac12(\binom {n_z}{2} + n_x n_z + n_y n_z)$, which is harder to optimize but probably gives a similar answer. $\endgroup$ – Misha Lavrov Mar 10 at 19:54

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.