Faster Computation of Successive Bounds on the Group Betweenness Centrality

2017-12-06
Dinler, Derya
Tural, Mustafa Kemal
Numerous measures have been introduced in the literature for the identification of central nodes in a network, e.g., group degree centrality, group closeness centrality, and group betweenness centrality (GBC) [1]. The GBC of a group of vertices measures the influence the group has on communications between every pair of vertices in the network assuming that information flows through the shortest paths. Given a group size, the problem of finding a group of vertices with the highest GBC is a combinatorial problem. We propose a method that computes bounds on the GBC of groups of vertices of a network. Once certain quantities related to the network are computed in the preprocessing step taking time proportional to the cube of 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 in [2] which has to be restarted for each group making it less efficient for the computation of the GBC of groups successively. In addition, the bounds used in our method are stronger and/or faster to compute in general. Our computational experiments on randomly generated and real-life networks 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.
Citation Formats
D. Dinler and M. K. Tural, “Faster Computation of Successive Bounds on the Group Betweenness Centrality,” presented at the 10th International Statistics Congress (ISC2017), (6 - 08 Aralık 2017), 2017, Accessed: 00, 2021. [Online]. Available: http://www.istkon.net/v2/wp-content/uploads/2017/12/ISTKON10-Abstract-Book-1.pdf.