Uniform edge betweenness centrality

Heather Newman, Hector Miranda, Rigoberto Flórez, Darren A. NarayanElectron. J. Graph Theory Appl 2020 · DOI

In the study of network topology, betweenness centrality serves as a vital metric for identifying the "bottlenecks" or "hubs" of a system. It measures how frequently an edge or node lies on the shortest path between all other pairs of vertices. Intuitively, high symmetry leads to uniform centrality: in an edge-transitive graph, where every edge is structurally identical to every other, each edge must naturally share the same betweenness value.

However, a more intriguing question arises: can a graph be structurally "messy" or asymmetric yet still maintain perfectly uniform edge betweenness? This paper explores this rare phenomenon, identifying the smallest examples and proving the existence of infinite families of such "unusually balanced" graphs.

The Computational Hunt for Rare Graphs

To understand the prevalence of uniform edge betweenness in the absence of high symmetry, the researchers conducted an exhaustive search of all connected graphs with up to 10 vertices. Utilizing Brendan McKay’s extensive graph databases and Wolfram Mathematica, they analyzed over 11.9 million unique structures.

The results highlighted the extreme rarity of this property. Out of the millions of candidates, only four non-edge-transitive graphs were found to possess uniform edge betweenness. Remarkably, none of these four were even vertex-transitive, meaning they lack even the basic symmetry where every node "looks" the same.

The four smallest non-edge-transitive graphs found to exhibit uniform edge betweenness centrality, discovered through an exhaustive search of nearly 12 million candidates.

These four graphs, ranging from 6 to 10 vertices, represent "accidental" balances where the distribution of shortest paths happens to equalize across all edges despite their different roles in the graph's overall architecture.

Key Insights: Shortest Path Orbits

The core "aha" moment of the research lies in the analysis of shortest path "orbits." Even when edges are fundamentally different—such as an "inner chord" versus an "outer chord" in a circulant graph—they can contribute equally to the total betweenness sum.

A detailed view of the 10-vertex non-vertex-transitive graph, illustrating the complex interplay of edges that results in uniform centrality despite a lack of high-level symmetry.

The authors demonstrated that for certain graphs, the set of shortest paths that specific edges do not participate in are isomorphic. This symmetry in the "unused" paths implies an equality in the "used" paths, ensuring uniform betweenness. This discovery challenges the assumption that uniform centrality is strictly a byproduct of edge-transitivity.

Proving Infinite Families

The most significant contribution of this work is the formal proof that these graphs are not merely isolated curiosities. By focusing on 2-circulant graphs—where vertices are arranged in a circle and connected at two specific distances—the authors used group theory to construct two infinite classes: $C_{18n-3}(1, 6n)$ and $C_{18n+3}(1, 6n)$.

Crucially, the authors demonstrated that these graphs are not "distance-regular," a common property that usually implies uniform centrality. This proves they belong to a distinct, previously uncharacterized class of balanced networks. They also identified the circulant graph $C_{15}(1, 6)$ as the smallest vertex-transitive graph that is uniform in edge betweenness but not edge-transitive.

Conclusion and Future Directions

This research expands our understanding of balance in network theory, proving that uniformity can emerge from asymmetry. While the authors have identified two infinite families, computational evidence suggests at least seven more classes of circulant graphs share this property. Future work remains to provide formal proofs for these conjectures and to explore whether similar phenomena exist in directed networks.

By identifying these "hidden symmetries," this paper provides new benchmarks for graph theorists and network scientists interested in the fundamental relationship between structure and centrality.

Summary updated

BibTeX
@article{newman2020uniform,
  author = {Heather Newman and Hector Miranda and Rigoberto Flórez and Darren A. Narayan},
  title = {{Uniform edge betweenness centrality}},
  journal = {Electron. J. Graph Theory Appl.},
  year = {2020},
  doi = {10.5614/ejgta.2020.8.2.7},
}
Figure