Faster Computation of Successive Bounds on the Group Betweenness Centrality
Derya Dinler
Department of Industrial Engineering, METU

Abstract
Identification of central (key) vertices in a network is an essential problem in network analysis. One of the measures introduced for this problem is the group betweenness centrality (GBC). 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 group of vertices with the highest GBC is a combinatorial problem. We propose a method that computes bounds on the GBC. 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 a method from the literature 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 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 gives the optimal group without exactly computing the GBC values which is computationally more demanding.
This study is a joint work with Mustafa Kemal Tural.

Short Bio
Derya Dinler is a Ph.D. candidate in the Department of Industrial Engineering, METU, where she has been working as a research and teaching assistant since 2011. She received her B.S. degree from the Department of Industrial Engineering, METU and her M.S. degree from the Department of Operational Research, METU, in 2011 and 2013, respectively. Her main research interests are location problems, network analysis, clustering, heuristics and evolutionary algorithms.

Venue
Friday, April 6, 2018 at 4.00 pm in IE03