Faster Computation of Successive Bounds on the Group Betweenness Centrality

Date

2017-12-06

Author

Dinler, Derya
Tural, Mustafa Kemal

Metadata

Show full item record

Item Usage Stats

140
views

0
downloads

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 problem. We propose a method that computes bounds on the GBC of groups of vertices of a network. 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 the method in [2] 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 on randomly generated and real-life networks 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 the optimal group can be found without exactly computing the GBC values which is computationally more demanding.

Subject Keywords

centrality, betweenness, social networks, probability bounds

URI

http://www.istkon.net/v2/wp-content/uploads/2017/12/ISTKON10-Abstract-Book-1.pdf
https://hdl.handle.net/11511/85244

Conference Name

10th International Statistics Congress (ISC2017), (6 - 08 Aralık 2017)

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

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-step betweenness centrality Akgün, Melda Kevser; Tural, Mustafa Kemal; Department of Industrial Engineering (2019) 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-ste...
Faster computation of successive bounds on the group betweenness centrality Dinler, Derya; Tural, Mustafa Kemal (null; 2017-07-17) 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 urn:x-wiley:00283045:media:net21817:net21817-math-0001 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 ...
A survey on multidimensional persistence theory Karagüler, Dilan; Pamuk, Semra; Department of Mathematics (2021-8) Persistence homology is one of the commonly used theoretical methods in topological data analysis to extract information from given data using algebraic topology. Converting data to a filtered object and analyzing the topological features of each space in the filtration, we will obtain a way of representing these features called the shape of data. This will give us invariants like barcodes or persistence diagrams for the data. These invariants are stable under small perturbations. In most applications, we n...
A simplified MAP channel estimator for OFDM systems under Rayleigh fading ÇÜRÜK, SELVA; Tanık, Yalçın (2010-06-01) This paper presents a simplified Maximum A Posteriori (SMAP) channel estimator to be used in orthogonal frequency division multiplexing (OFDM) systems under the Rayleigh fading assumption for the subchannels, using a parametric correlation model and assuming that the channel is frequency selective and slowly time varying. Expressions for the mean-square error (MSE) of estimations are derived to evaluate the performance of the estimator. The relation between the correlation of subchannels taps and error vari...

Citation Formats

D. Dinler and M. K. Tural, “Faster Computation of Successive Bounds on the Group Betweenness Centrality,” presented at the 10th International Statistics Congress (ISC2017), (6 - 08 Aralık 2017), 2017, Accessed: 00, 2021. [Online]. Available: http://www.istkon.net/v2/wp-content/uploads/2017/12/ISTKON10-Abstract-Book-1.pdf.