Betweenness centrality in dense spatial networks

Area of Science:

• Network Science
• Graph Theory
• Computational Complexity

Background:

• Betweenness centrality (BC) is crucial for analyzing complex network structures.
• Calculating BC is computationally challenging, especially for large networks.
• Previous studies computed BC for infinite density limits, showing universal behavior.

Purpose of the Study:

• To develop a method for calculating BC in large networks at finite densities.
• To investigate the nonuniversal behavior of shortest paths in spatial networks.
• To provide a framework for understanding and computing BC in practical network scenarios.

Main Methods:

• Proposed an analytical expansion for BC at large and finite densities.
• Computed the lowest nontrivial order of the expansion.
• Validated the analytical results against numerical simulations on various graph types.

Main Results:

• The lowest order term in the expansion captures the 'straightness' of shortest paths.
• This 'straightness' is nonuniversal and depends on the specific graph construction.
• Excellent agreement was observed between analytical predictions and numerical simulations, even at low densities.

Conclusions:

• The proposed method offers a tractable approach to compute BC in large spatial networks.
• The findings highlight the nonuniversal nature of shortest path geometry in finite density networks.
• This work provides a valuable framework for network analysis and understanding graph properties.