Performance Evaluation of Betweenness Centrality Using Clustering Methods

  • B. Szabari Eötvös Loránd University, Budapest, Hungary
  • A. Kiss J. Selye University, Komárno, Slovakia

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

[1] Aberer, K., Hauswirth, M., and Salehi, A. Infrastructure for data processing in large-scale interconnected sensor networks. In 2007 International Conference on Mobile Data Management (2007), IEEE, pp. 198–205.
[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.
Published
2020-07-09
How to Cite
SZABARI, B.; KISS, A.. Performance Evaluation of Betweenness Centrality Using Clustering Methods. Studia Universitatis Babeș-Bolyai Informatica, [S.l.], v. 65, n. 1, p. 59-74, july 2020. ISSN 2065-9601. Available at: <http://www.cs.ubbcluj.ro/~studia-i/journal/journal/article/view/51>. Date accessed: 05 dec. 2020. doi: https://doi.org/10.24193/subbi.2020.1.05.
Section
Articles