A method to improve the time of computing betweenness centrality in social network graph

Nguyen Xuan Dung; Doan Van Ban; Do Thi Bich Ngoc

doi:10.15625/2525-2518/57/3/13166

Author affiliations

Authors

Nguyen Xuan Dung Hanoi Open University, B101 Nguyen Hien Str., Hai Ba Trung Dist., Ha Noi, Viet Nam
Doan Van Ban Viet Nam Academy of Science and Technology, 18 Hoang Quoc Viet, Cau Giay Dist., Ha Noi, Viet Nam
Do Thi Bich Ngoc Posts and Telecommunications Institute of Technology, 122 Hoang Quoc Viet Str., Cau Giay Dist., Ha Noi, Viet Nam

DOI:

https://doi.org/10.15625/2525-2518/57/3/13166

Keywords:

Betweenness centrality, mining graph data, analyzing social network

Abstract

The Betweenness centrality is an important metric in the graph theory and can be applied in the analyzing social network. The main researches about Betweenness centrality often focus on reducing the complexity. Nowadays, the number of users in the social networks is huge. Thus, improving the computing time of Betweenness centrality to apply in the social network is neccessary. In this paper, we propose the algorithm of computing Betweenness centrality by reduce the similar nodes in the graph in order to reducing computing time. Our experiments with graph networks result shows that the computing time of the proposed algorithm is less than Brandes algorithm. The proposed algorithm is compared with the Brandes algorithm [3] in term of execution time.

Downloads

Download data is not yet available.

References

D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating Betweenness centrality. In WAW, (2007).

D. A. Bader and K. Madduri. Parrallel algorithm for evaluating centrality indices in real-world networks. In ICPP, (2006).

U.Brandes. A faster algorithm for Betweenness centrality. Journal of Mathematical Sociology, 25(2):163-177, (2001).

U. Brandes and C. Pich. Centrality estimation in large networks. International Journal of Bifurcation and Chaos, (2007).

Mikhail Chernoskutov, Yves Ineichen, Costas Bekas, Heuristic Algorithm for Approximation Betweenness centrality Using Graph Coarsening, 4th International Young Scientists Conference on Computational Science, Elsevier B.V, Volume 66, Pages 83-92, (2015).

N. Edmonds, T. Hoefler, and A. Lumsdaine. A space efficient parallel algorithm for computing betweenness centrality in distributed memory. In HiPC, (2010).

Dora Erdos, Vatche Ishakian, Azer Bestavros, Evimaria Terzi. A divide and Conquer Algorithm for Betweenness Centrality, (2015).

L. C. Freeman. A set of measures of centrality based on Betweenness centrality. Sociometry, 40(1), Pages 35-41,(1977).

L. C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks 1:215-239,(1978).

Steven Fleuren. Using preprocessing to speed up Brandes’ betweenness centrality algorithm, (2018).

R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In ALENEX, (2008).

M. Newman. A measure of Betweenness centrality centrality based on random walks. Social Networks, 27(1):39-54, (2005).

M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Physical Review E, 69(026113),(2004).

K. Mudduri, D. Ediger, K. Jiang, D. A. Bader, and D. G. Chavarria-Miranda. A faster paralel algorithm and effcient multithreaded implementations for evaluating Betweenness centrality on massive datasets. In IPDPS, (2009).

Rami Puzis, Polina Zilberman, Yuval Elovici, Shlomi Dolev and Ulrik Brandes, Heuristics for Speeding up Betweenness centrality Computation, ASE/IEEE International Conference on Privacy, Security, Risk and Trust, (2012).

M. Riondato and E. M. Kornaropoulos. Fast approximation of Betweenness centrality through sampling WSDM’14, pages 413-422, (2014).

A. E. Sariyuce, E. Saule, K. Kaya, and U. V. Catalyurek. Shattering and compressing networks for Betweenness centrality. In SDM, (2013).

G. Tan, D. Tu and N. Sum. A parallel algorithm for computing Betweenness centrality. In ICPP, (2009).

R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications. SIGMOD’(98).

Zhang, Berg, Marie, Malik: “SVM-KNN: Discriminative nearest neighbor classification for visual category recognition”, In IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Volume 2, pages 2126-2136, (2006).