Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
K-step betweenness centrality
Download
index.pdf
Date
2019
Author
Akgün, Melda Kevser
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
193
views
114
downloads
Cite This
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.
Subject Keywords
Computer algorithms.
,
Keywords: Betweenness centrality
,
Group betweenness
,
Network analysis
,
Social networks
,
k-step betweenness.
URI
http://etd.lib.metu.edu.tr/upload/12623902/index.pdf
https://hdl.handle.net/11511/44039
Collections
Graduate School of Natural and Applied Sciences, Thesis
Suggestions
OpenMETU
Core
k-step betweenness centrality
Akgun, Melda Kevser; Tural, Mustafa Kemal (Springer Science and Business Media LLC, 2020-03-01)
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 tha...
Faster Computation of Successive Bounds on the Group Betweenness Centrality
Dinler, Derya; Tural, Mustafa Kemal (2017-12-06)
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 pro...
Faster computation of successive bounds on the group betweenness centrality
DİNLER, DERYA; Tural, Mustafa Kemal (2018-06-01)
We propose a method that computes bounds on the group betweenness centrality (GBC) of groups of vertices of a network. Once certain quantities related to the network are computed in the preprocessing step that takes O(n(3)) time, where n is 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 of Kolaczyk et al....
K-partitioning of Signed or Weighted Bipartite Graphs
Omeroglu, Nurettin B.; Toroslu, İsmail Hakkı; Gokalp, Sedat; Davulcu, Hasan (2013-09-14)
In this work, K-partitioning of signed or weighted bipartite graph problem has been introduced, which appears as a real life problem where the partitions of bipartite graph represent two different entities and the edges between the nodes of the partitions represent the relationships among them. A typical example is the set of people and their opinions, whose strength is represented as signed numerical values. Using the weights on the edges, these bipartite graphs can be partitioned into two or more clusters...
K-SVMeans: A hybrid clustering algorithm for multi-type interrelated datasets
Bolelli, Levent; Ertekin Bolelli, Şeyda; Zhou, Ding; Giles, C. Lee (2007-01-01)
Identification of distinct clusters of documents in text collections has traditionally been addressed by making the assumption that the data instances can only be represented by homogeneous and uniform features. Many real-world data, on the other hand, comprise of multiple types of heterogeneous interrelated components, such as web pages and hyperlinks, online scientific publications and authors and publication venues to name a few. In this paper, we present K-SVMeans, a clustering algorithm for multi-type ...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. K. Akgün, “K-step betweenness centrality,” Thesis (M.S.) -- Graduate School of Natural and Applied Sciences. Industrial Engineering., Middle East Technical University, 2019.