A method to improve the time of computing betweenness centrality in social network graph
Keywords:Betweenness centrality, mining graph data, analyzing social network
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  in term of execution time.
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).
How to Cite
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Vietnam Journal of Sciences and Technology (VJST) is an open access and peer-reviewed journal. All academic publications could be made free to read and downloaded for everyone. In addition, articles are published under term of the Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA) Licence which permits use, distribution and reproduction in any medium, provided the original work is properly cited & ShareAlike terms followed.
Copyright on any research article published in VJST is retained by the respective author(s), without restrictions. Authors grant VAST Journals System (VJS) a license to publish the article and identify itself as the original publisher. Upon author(s) by giving permission to VJS either via VJS journal portal or other channel to publish their research work in VJS agrees to all the terms and conditions of https://creativecommons.org/licenses/by-sa/4.0/ License and terms & condition set by VJS.
Authors have the responsibility of to secure all necessary copyright permissions for the use of 3rd-party materials in their manuscript.