# Maximum possible edge betweenness of a graph?

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.

• 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$. – Jaap Scherphuis Mar 10 at 16:08
• @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$. – Dan Van Boxel Mar 10 at 19:42

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.
• 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! – Dan Van Boxel Mar 10 at 19:41
• 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. – Misha Lavrov Mar 10 at 19:54