Hide/Show Apps

K-step betweenness centrality

Akgün, Melda Kevser
The notions of betweenness centrality (BC) and its extension group betweenness centrality (GBC) are widely used in social network analyses. We introduce variants of them; namely, the k-step BC and k-step GBC. The k-step GBC of a group of vertices in a network is a measure of the likelihood that at least one group member will get the information communicated between a randomly chosen pair of vertices through a randomly chosen shortest path within the first k steps of the start of the communication. The k-step GBC of a single vertex is the k-step BC of that vertex. The introduced centrality measures may find uses in applications where it is important or critical to obtain the information within a fixed time of the start of the communication. For the introduced centrality measures, we propose an algorithm that can compute successively the k-step GBC of several groups of vertices. Moreover, we propose a mixed integer programming formulation to compute the group that has the highest k-step GBC value and a heuristic approach to compute a group of vertices whose k-step GBC value is high. The performances of the proposed algorithms are evaluated through computational experiments on real and randomly generated networks.