Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks

Area of Science:

• Network Science
• Computational Complexity
• Graph Theory

Background:

• Betweenness centrality measures a node's importance in a network by counting shortest paths through it.
• Calculating betweenness centrality in large, real-world networks with hierarchical structures is computationally complex.
• Existing methods struggle with the scale and hierarchical nature of modern complex networks.

Purpose of the Study:

• To propose a novel hierarchical decomposition approach for accelerating betweenness centrality computation in complex networks.
• To leverage local structural information within hierarchical communities for improved efficiency.
• To provide a method suitable for parallel computation and efficient updates.

Main Methods:

• A hierarchical decomposition strategy is introduced to partition complex networks.
• The method utilizes local community structures to optimize shortest path calculations.
• The approach is designed with a parallel architecture for enhanced scalability.

Main Results:

• The proposed method significantly speeds up betweenness centrality calculations.
• Performance improvements are particularly notable in networks with numerous homogeneous communities.
• The method demonstrates superior performance compared to traditional approaches on real-world power grids and artificial networks.

Conclusions:

• The hierarchical decomposition approach offers an effective and efficient solution for computing betweenness centrality in complex networks.
• This method provides substantial computational advantages, especially for large-scale, hierarchically structured networks.
• The parallel nature and efficiency in handling local changes make it highly applicable to dynamic network analysis.