Faster computation of successive bounds on the group betweenness centrality

We propose a method that computes bounds on the group betweenness centrality (GBC) of groups of vertices of a network. Once certain quantities related to the network are computed in the preprocessing step that takes O ( n 3 ) time, where n is the number of vertices in the network, our method can com...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2018-06, Vol.71 (4), p.358-380
Main Authors: Dinler, Derya, Tural, Mustafa Kemal
Format: Article
Language:English
Subjects:
betweenness
centrality
group betweenness
network analysis
Preprocessing
probability bounds
Run time (computers)
social networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a method that computes bounds on the group betweenness centrality (GBC) of groups of vertices of a network. Once certain quantities related to the network are computed in the preprocessing step that takes O ( n 3 ) time, where n is the number of vertices in the network, our method can compute bounds on the GBC of any number of groups of vertices successively, for each group requiring a running time proportional to the square of its size. Our method is an improvement of the method of Kolaczyk et al. [Social Networks, 31, 3 (2009)], which has to be restarted for each group making it less efficient for the successive GBC computations. In addition, the bounds used in our method are stronger and/or faster to compute. Our computational experiments show that in the search for a group of a certain size with the highest GBC value, our method reduces the number of candidate groups substantially and in some cases the optimal group can be found without exactly computing the GBC values which is computationally more demanding.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21817