k-step betweenness centrality

Akgun M. K., TURAL M. K.

COMPUTATIONAL AND MATHEMATICAL ORGANIZATION THEORY, vol.26, no.1, pp.55-87, 2020 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 26 Issue: 1
  • Publication Date: 2020
  • Doi Number: 10.1007/s10588-019-09301-9
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, Metadex, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.55-87
  • Keywords: Betweenness, Centrality, Group betweenness, Network analysis, Social networks, k-step betweenness, EFFICIENT ALGORITHMS, SOCIAL NETWORKS
  • Middle East Technical University Affiliated: Yes


The notions of betweenness centrality (BC) and 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 pairs of vertices through shortest paths 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. The performance of the proposed algorithm is evaluated through computational experiments. The use of the new BC measures leads to an earlier control of the information (virus, malware, or rumor) before it spreads through the network.