An Approximate Flow Betweenness Centrality Measure for Complex Network

Jia-Rui LIU  Shi-Ze GUO  Zhe-Ming LU  Fa-Xin YU  Hui LI  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.727-730
Publication Date: 2013/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.727
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Information Network
complex network,  centrality,  flow betweenness centrality,  approximate flow betweenness centrality,  

Full Text: PDF>>
Buy this Article

In complex network analysis, there are various measures to characterize the centrality of each node within a graph, which determines the relative importance of each node. The more centrality a node has in a network, the more significance it has in the spread of infection. As one of the important extensions to shortest-path based betweenness centrality, the flow betweenness centrality is defined as the degree to which each node contributes to the sum of maximum flows between all pairs of nodes. One of the drawbacks of the flow betweenness centrality is that its time complexity is somewhat high. This Letter proposes an approximate method to calculate the flow betweenness centrality and provides experimental results as evidence.