TY - GEN
T1 - DyBED
T2 - 2018 IEEE International Conference on Big Data, Big Data 2018
AU - Chehreghani, Mostafa Haghir
AU - Bifet, Albert
AU - Abdessalem, Talel
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/2
Y1 - 2018/7/2
N2 - An important index widely used to analyze social and information networks is betweenness centrality. In this paper, given a dynamic and directed graph G and a vertex r in G, we present the DyBED algorithm that updates the (approximate) betweenness centrality of r, when an update operation (vertex/edge insertion/deletion) occurs in G. Our algorithm first during pre-processing computes two subsets of the vertex set of G, called RF(r) and RT (r). The Cartesian product of these two sets defines the sample space of our algorithm. In other words, each sample is a pair, whose first element belongs to RF(r) and second element belongs to RT (r). Then after each update operation, DyBED updates the sets RF(r) and RT (r), the sampled pairs, the information stored for each sample and accordingly, the betweenness centrality of r. We theoretically and empirically evaluate DyBED and show that it yields significant improvement over existing work. In particular, our extensive experiments reveal that DyBED is orders of magnitude faster than most efficient existing algorithms.
AB - An important index widely used to analyze social and information networks is betweenness centrality. In this paper, given a dynamic and directed graph G and a vertex r in G, we present the DyBED algorithm that updates the (approximate) betweenness centrality of r, when an update operation (vertex/edge insertion/deletion) occurs in G. Our algorithm first during pre-processing computes two subsets of the vertex set of G, called RF(r) and RT (r). The Cartesian product of these two sets defines the sample space of our algorithm. In other words, each sample is a pair, whose first element belongs to RF(r) and second element belongs to RT (r). Then after each update operation, DyBED updates the sets RF(r) and RT (r), the sampled pairs, the information stored for each sample and accordingly, the betweenness centrality of r. We theoretically and empirically evaluate DyBED and show that it yields significant improvement over existing work. In particular, our extensive experiments reveal that DyBED is orders of magnitude faster than most efficient existing algorithms.
KW - Social network analysis
KW - approximate algorithm
KW - betweenness centrality
KW - directed graphs
KW - dynamic graphs
U2 - 10.1109/BigData.2018.8622452
DO - 10.1109/BigData.2018.8622452
M3 - Conference contribution
AN - SCOPUS:85062602139
T3 - Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018
SP - 2114
EP - 2123
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.
Y2 - 10 December 2018 through 13 December 2018
ER -