TY - GEN
T1 - An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms
AU - Chehreghani, Mostafa Haghir
AU - Bifet, Albert
AU - Abdessalem, Talel
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/2
Y1 - 2018/7/2
N2 - One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no comprehensive and in-depth analysis and comparison of these algorithms in the literature. In this paper, we first present a generic algorithm that is used to express different approximate algorithms in terms of probability distributions. Using this generic algorithm, we show that interestingly existing methods have the same theoretical accuracy. Then, we present an extension of distance-based sampling to group betweenness centrality, which is based on a new notion of distance between a single vertex and a set of vertices. In the end, to empirically evaluate efficiency and accuracy of different algorithms, we perform experiments over several real-world networks. Our extensive experiments reveal that those approximate algorithms that are based on shortest path sampling are orders of magnitude faster than those algorithms that are based on pair sampling, while these two types of algorithms have almost comparable empirical accuracy.
AB - One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no comprehensive and in-depth analysis and comparison of these algorithms in the literature. In this paper, we first present a generic algorithm that is used to express different approximate algorithms in terms of probability distributions. Using this generic algorithm, we show that interestingly existing methods have the same theoretical accuracy. Then, we present an extension of distance-based sampling to group betweenness centrality, which is based on a new notion of distance between a single vertex and a set of vertices. In the end, to empirically evaluate efficiency and accuracy of different algorithms, we perform experiments over several real-world networks. Our extensive experiments reveal that those approximate algorithms that are based on shortest path sampling are orders of magnitude faster than those algorithms that are based on pair sampling, while these two types of algorithms have almost comparable empirical accuracy.
KW - Social network analysis
KW - approximate algorithm
KW - group betweenness centrality
KW - sampling
KW - shortest path
U2 - 10.1109/BigData.2018.8622133
DO - 10.1109/BigData.2018.8622133
M3 - Conference contribution
AN - SCOPUS:85062619934
T3 - Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
SP - 2104
EP - 2113
BT - Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
A2 - Abe, Naoki
A2 - Liu, Huan
A2 - Pu, Calton
A2 - Hu, Xiaohua
A2 - Ahmed, Nesreen
A2 - Qiao, Mu
A2 - Song, Yang
A2 - Kossmann, Donald
A2 - Liu, Bing
A2 - Lee, Kisung
A2 - Tang, Jiliang
A2 - He, Jingrui
A2 - Saltz, Jeffrey
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Conference on Big Data, Big Data 2018
Y2 - 10 December 2018 through 13 December 2018
ER -