Faster computation of successive bounds on the group betweenness centrality

Date

2018-06-01

Author

DİNLER, DERYA
Tural, Mustafa Kemal

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

136
views

0
downloads

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. [Social Networks, 31, 3 (2009)], which has to be restarted for each group making it less efficient for the successive GBC computations. In addition, the bounds used in our method are stronger and/or faster to compute. Our computational experiments 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

Betweenness, Centrality, Group betweenness, Network analysis, Probability bounds, Social networks

URI

https://hdl.handle.net/11511/49002

Journal

NETWORKS

DOI

https://doi.org/10.1002/net.21817

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

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 ...
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...
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 residue multiplication modulo 521-bit mersenne prime and application to ECC Ali, Shoukat; Cenk, Murat; Department of Cryptography (2017) We present faster algorithms for the residue multiplication modulo 521-bit Mersenne prime on 32- and 64-bit platforms by using Toeplitz Matrix-Vector Product (TMVP). The total arithmetic cost of our proposed algorithms is less than the existing algorithms and we select the ones, 32- and 64-bit residue multiplication, with the best timing results on our testing machine(s). For the 64-bit residue multiplication we have presented three versions of our algorithm along with their arithmetic cost and from impleme...
Efficient interleaved Montgomery modular multiplication for lattice-based cryptography AKLEYLEK, SEDAT; Tok, Zaliha Yuce (2014-01-01) In this paper, we give modified version of interleaved Montgomery modular multiplication method for lattice-based cryptography. With the proposed algorithms, we improve the multiplication complexity and embed the conversion operation into the algorithm with almost free cost. We implement the proposed methods for the quotient ring (Z/qZ)[x]/(x(n) - 1) and (Z/pZ)[x]/(x(n) + 1) on the GPU (NVIDIA Quadro 600) using the CUDA platform. NTRUEncrypt is accelerated approximately 35% on the GPU by using the proposed ...

Citation Formats

D. DİNLER and M. K. Tural, “Faster computation of successive bounds on the group betweenness centrality,” NETWORKS, pp. 358–380, 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/49002.