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).
Authors who publish with Vietnam Journal of Science and Technology agree with the following terms:
- The manuscript is not under consideration for publication elsewhere. When a manuscript is accepted for publication, the author agrees to automatic transfer of the copyright to the editorial office.
- The manuscript should not be published elsewhere in any language without the consent of the copyright holders. Authors have the right to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal’s published version of their work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are encouraged to post their work online (e.g., in institutional repositories or on their websites) prior to or during the submission process, as it can lead to productive exchanges or/and greater number of citation to the to-be-published work (See The Effect of Open Access).