Send to

Choose Destination
Sci Rep. 2017 Apr 20;7:46491. doi: 10.1038/srep46491.

Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks.

Author information

College of Electrical and Information Engineering, Hunan University, Changsha 410082, China.
School of Information Science and Engineering, Central South University, Changsha 410083, China.
Department of Electrical and Computer Engineering, Baylor University, Waco 76798-7356, Texas, USA.


Betweenness centrality is an indicator of a node's centrality in a network. It is equal to the number of shortest paths from all vertices to all others that pass through that node. Most of real-world large networks display a hierarchical community structure, and their betweenness computation possesses rather high complexity. Here we propose a new hierarchical decomposition approach to speed up the betweenness computation of complex networks. The advantage of this new method is its effective utilization of the local structural information from the hierarchical community. The presented method can significantly speed up the betweenness calculation. This improvement is much more evident in those networks with numerous homogeneous communities. Furthermore, the proposed method features a parallel structure, which is very suitable for parallel computation. Moreover, only a small amount of additional computation is required by our method, when small changes in the network structure are restricted to some local communities. The effectiveness of the proposed method is validated via the examples of two real-world power grids and one artificial network, which demonstrates that the performance of the proposed method is superior to that of the traditional method.

Supplemental Content

Full text links

Icon for Nature Publishing Group Icon for PubMed Central
Loading ...
Support Center