Performance Evaluation of Betweenness Centrality Using Clustering Methods
Abstract
Betweenness centrality measure is used as a general measure of centrality, which can be applied in many scientific fields like social networks, biological networks, telecommunication networks or even in any area that can be well modelled using complex networks where it is important to identify more influential nodes. In this paper, we propose using different clustering algorithms to improve the computation of betweenness centrality over large networks. The experiments show how to achieve faster evaluation without altering the overall computational complexity.
References
[2] Bader, D. A., Kintali, S., Madduri, K., and Mihail, M. Approximating betweenness centrality. In International Workshop on Algorithms and Models for the Web-Graph (2007), Springer, pp. 124–137.
[3] Bavelas, A. Communication patterns in task-oriented groups. The journal of the acoustical society of America 22, 6 (1950), 725–730.
[4] Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008, 10 (2008), P10008.
[5] Bonald, T., Charpentier, B., Galland, A., and Hollocou, A. Hierarchical graph clustering using node pair sampling. arXiv preprint arXiv:1806.01664 (2018).
[6] Brandes, U. A faster algorithm for betweenness centrality. Journal of mathematical sociology 25, 2 (2001), 163–177.
[7] Freeman, L. C. A set of measures of centrality based on betweenness. Sociometry (1977), 35–41.
[8] Gasteiger, J., and Zupan, J. Neural networks in chemistry. Angewandte Chemie International Edition in English 32, 4 (1993), 503–527.
[9] Gonzalez-Diaz, H., Vilar, S., Santana, L., and Uriarte, E. Medicinal chemistry and bioinformatics-current trends in drugs discovery with networks topological indices. Current Topics in Medicinal Chemistry 7, 10 (2007), 1015–1029.
[10] Hagberg, A., Swart, P., and S Chult, D. Exploring network structure, dynamics, and function using networkx. Tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
[11] Irani, D., Balduzzi, M., Balzarotti, D., Kirda, E., and Pu, C. Reverse social engineering attacks in online social networks. In International conference on detection of intrusions and malware, and vulnerability assessment (2011), Springer, pp. 55–74.
[12] Leskovec, J., and Krevl, A. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
[13] Mason, O., and Verwoerd, M. Graph theory and networks in biology. IET systems biology 1, 2 (2007), 89–119.
[14] Newman, M. E. A measure of betweenness centrality based on random walks. Social networks 27, 1 (2005), 39–54.
[15] Newman, M. E., and Girvan, M. Finding and evaluating community structure in networks. Physical review E 69, 2 (2004), 026113.
[16] Rossi, R. A., and Ahmed, N. K. The network data repository with interactive graph analytics and visualization. In AAAI (2015).
[17] Sen, S., and Wang, J. Analyzing peer-to-peer traffic across large networks. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment (2002), pp. 137–150.
[18] van Dongen, S. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, 2000.
[19] Zaki, M. J., and Meira, W. Data mining and analysis: fundamental concepts and algorithms. Cambridge University Press, 2014.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
When the article is accepted for publication, I, as the author and representative of the coauthors, hereby agree to transfer to Studia Universitatis Babes-Bolyai, Series Informatica, all rights, including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author specifically retain: the right to make further copies of all or part of the published article for my use in classroom teaching; the right to reuse all or part of this material in a review or in a textbook of which I am the author; the right to make copies of the published work for internal distribution within the institution that employs me.
