A Method to improve the time of computing Betweenness centrality in socical network graph

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

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.


Keywords


Betweenness centrality, mining graph data, analyzing social network

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).




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

Refbacks

  • There are currently no refbacks.


Index: Google Scholar; Crossref; VCGate; Asean Citation Index

Published by Vietnam Academy of Science and Technology