Logo PTI Logo FedCSIS

Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 39

Towards the analysis of errors in centrality measures in perpetuated networks

, ,

DOI: http://dx.doi.org/10.15439/2024F4841

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 417–428 ()

Full text

Abstract. Centrality measures are essential tools for analyzing the structure and dynamics of graphs, such as knowledge or social networks. They reveal the significance and influence of individual nodes. However, their accuracy can be influenced by data quality, algorithms, and network properties. This study investigates errors in centrality measures within perpetuated networks. It focuses on network resilience and how these re- sults may be used to develop efficient algorithms for centrality measures. It also investigates how perturbation strategies impact network resilience and predict connectivity in the perturbed network. By employing centrality measures (degree, betweenness, closeness, eigenvector), we identify critical nodes that significantly affect network connectivity and information flow. Additionally, statistical tests (Kolmogorov-Smirnov, Crame ́r-von Mises) assess network robustness and pinpoint critical transition points. This study, by outlining methods for error identification, quantifica- tion, and mitigation, offers valuable insights for enhancing net- work resilience across various domains, including infrastructure design and social network analysis.

References

  1. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: Structure and dynamics,” Physics reports, vol. 424, no. 4-5, pp. 175–308, 2006.
  2. J. Dörpinghaus, S. Klante, M. Christian, C. Meigen, and C. Düing, “From social networks to knowledge graphs: A plea for interdisciplinary approaches,” Social Sciences & Humanities Open, vol. 6, no. 1, p. 100337, 2022.
  3. S. P. Borgatti, “Centrality and network flow,” Social networks, vol. 27, no. 1, pp. 55–71, 2005.
  4. M. E. J. Newman, Networks: An Introduction. Oxford University Press, 2010.
  5. J. Dörpinghaus, A. Stefan, B. Schultz, and M. Jacobs, “Context mining and graph queries on giant biomedical knowledge graphs,” Knowledge and Information Systems, vol. 64, no. 5, pp. 1239–1262, 2022.
  6. J. Dörpinghaus, V. Weil, and M. W. Sommer, “Towards modelling and analysis of longitudinal social networks,” Annals of Computer Science and Information Systems, vol. 37, pp. 81–89, 2023.
  7. J. Dörpinghaus, T. Hübenthal, and J. Faber, “A novel link prediction approach on clinical knowledge graphs utilising graph structures,” in 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2022, pp. 43–52.
  8. A. Dahhani, I. Alloui, S. Monnet, and F. Vernier, “A graph matching algorithm to extend wise systems with semantic,” in 2023 18th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2023, pp. 411–420.
  9. L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215–239, 1978.
  10. R. Albert, H. Jeong, and A. Barabasi, “Error and attack tolerance of complex networks,” Nature, 2000.
  11. A. D. Broido and A. Clauset, “Scale-free networks are rare,” Nature communications, vol. 10, no. 1, pp. 1–12, 2019.
  12. T. B. Arnold and J. W. Emerson, “Nonparametric goodness-of-fit tests for discrete null distributions,” R Journal, vol. 3, no. 2, pp. 34–39, 2011.
  13. A. Clauset, C. R. Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data,” SIAM review, vol. 51, no. 4, pp. 661–703, 2009.
  14. R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, pp. 47–77, 2002.
  15. S. Wandelt, X. Sun, D. Feng, M. Zanin, and S. Havlin, “A comparative analysis of approaches to network-dismantling,” Scientific Reports, vol. 8, p. 13513, 2018.
  16. E. Jenelius and L.-G. Mattsson, Resilience of Transport Systems, 05 2020.
  17. P. Holme, B. Kim, C. Yoon, and S. Han, “Attack vulnerability of complex networks,” Physical Review E, 2002.
  18. J. Smith and L. Johnson, “Edge removal and network reconstruction in biological networks,” PLoS ONE, vol. 10, no. 7, p. e0131180, 2015.
  19. M. Bellingeri, D. Bevacqua, F. Scotognella, and et al., “A comparative analysis of link removal strategies in real complex weighted networks,” Scientific Reports, vol. 10, no. 1, p. 3911, 2020.
  20. V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Physical Review Letters, vol. 87, no. 19, p. 198701, 2001.
  21. Y. Yang, T. Nishikawa, and A. E. Motter, “Small vulnerable sets determine large network cascades in power grids,” Science, vol. 358, 2017.
  22. J. L. Caldu-Primo, E. R. Alvarez-Buylla, and J. Davila-Velderrain, “Structural robustness of mammalian transcription factor networks reveals plasticity across development,” Scientific Reports, vol. 8, no. 1, pp. 1–15, 2018.
  23. L. K. Gallos, R. Cohen, P. Argyrakis, A. Bunde, and S. Havlin, “Stability and topology of scale-free networks under attack and defense strategies,” Physical Review Letters, vol. 94, no. 18, p. 188701, 2005.
  24. M. Zanin and F. Lillo, “Modelling the air transport with complex networks: A short review,” The European Physical Journal Special Topics, vol. 215, pp. 5–21, 2013.
  25. J. Dörpinghaus, V. Weil, C. Düing, and M. W. Sommer, “Centrality measures in multi-layer knowledge graphs,” Annals of Computer Science and Information Systems, vol. 32, pp. 163–170, 2022.
  26. C. N. Schneider and I. Koutsopoulos, “Mitigation of malicious attacks on networks,” Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 2011.
  27. M. Bellingeri, D. Cassi, and S. Vincenzi, “Efficiency of attack strategies on complex model and real-world networks,” Physica A: Statistical Mechanics and its Applications, vol. 414, p. 174–180, Nov. 2014. [Online]. Available: http://dx.doi.org/10.1016/j.physa.2014.06.079
  28. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Network robustness and fragility: Percolation on random graphs,” Physical Review Letters, vol. 85, no. 25, p. 5468, 2000.
  29. X. Chen and J. Li, “Community detection in complex networks using edge-deleting with restrictions,” Physica A: Statistical Mechanics and its Applications, vol. 519, pp. 181–194, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0378437118315358
  30. F. Baltar and I. Brunet, “Unintended consequences and new challenges of online social systems: Methods, challenges, and applications,” Journal of Information Technology & Politics, vol. 9, no. 1, pp. 1–20, 2012.
  31. S. Aliakbary, J. Habibi, and A. Movaghar, “Quantification and comparison of degree distributions in complex networks,” in 7th International Symposium on Telecommunications (IST), Tehran, Iran, September 2014.
  32. M. Faloutsos, P. Faloutsos, and C. Faloutsos, “The structure of the internet graph,” IEEE/ACM Transactions on Networking, vol. 7, no. 3, pp. 397–412, 1999.
  33. “Table of critical values for the two-sample test,” https://web.archive.org/web/20130613002106/http://www.soest.hawaii.edu/wessel/courses/gg313/Critical KS.pdf, memento from June 13, 2013 in the Internet Archive. [Online]. Avail- able: https://web.archive.org/web/20130613002106/http://www.soest.hawaii.edu/wessel/courses/gg313/Critical_KS.pdf
  34. I. M. Chakravarti, R. G. Laha, and J. Roy, Engineering Statistics Handbook. New York, NY: John Wiley and Sons, 1967.
  35. G. Kossinets and D. J. Watts, “Empirical analysis of an evolving social network,” Science, vol. 311, pp. 88–90, 2006.
  36. H. Cramér, “On the composition of elementary errors,” Skandinavisk Aktuarietidskrift, vol. 11, pp. 141–180, 1928.
  37. R. von Mises, Wahrscheinlichkeit, Statistik und Wahrheit. Vienna, Austria: Julius Springer, 1928.
  38. T. W. Anderson, “On the distribution of the two-sample cramer-von-mises criterion,” The Annals of Mathematical Statistics, pp. 1148–1159, 1962.
  39. M. A. Stephens, “Edf statistics for goodness of fit and some comparisons,” Journal of the American Statistical Association, vol. 69, no. 347, pp. 730–737, 1974.
  40. A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” Proceedings of the 7th Python in Science Conference (SciPy 2008), vol. 11, pp. 11–15, 2008.
  41. P. Erdös and A. Rényi, “On random graphs, i,” Publicationes Mathematicae (Debrecen), vol. 6, pp. 290–297, 1959.
  42. E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959.
  43. A. L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.
  44. D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.
  45. M. E. Newman, Networks. Oxford University Press, 2018.
  46. E. Estrada, “Subgraph centrality in complex networks,” Physical Review E, vol. 71, no. 5, p. 056103, 2005.
  47. M. Newman, The Structure and Dynamics of Networks. Princeton University Press, 2003.