K-step betweenness centrality

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: MELDA KEVSER AKGÜN

Danışman: Mustafa Kemal Tural

Özet:

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.