Logo PTI Logo FedCSIS

Communication Papers of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 32

Centrality Measures in multi-layer Knowledge Graphs

, , ,

DOI: http://dx.doi.org/10.15439/2022F43

Citation: Communication Papers of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 32, pages 163170 ()

Full text

Abstract. Knowledge graphs play a central role for linkingdifferent data which leads to multiple layers. Thus, they are widely used in big data integration, especially for connecting data from different domains. Few studies have investigated the questions how multiple layers within graphs impact methods and algorithms developed for single-purpose networks, for example social networks. This manuscript investigates the impact on the centrality measures of graphs with multiple layers compared to a those measures in single-purpose graphs. In particular, (a) we develop an experimental environment to (b) evaluate two different centrality measures --- degree and betweenness centrality --- on random graphs inspired by social network analysis: small-world and scale-free networks. The presented approach (c) shows that the graph structures and topology has a great impact on its robustness for additional data stored. Although the experimental analysis of random graphs allows us to make some basic observations we will (d) make suggestions for additional research on particular graph structures that have a great impact on the stability of networks.


  1. estimations offer us a first impression of problematic graph D. Suárez, J. M. Dı́az-Puente, and M. Bettoni, “Risks identification and management related to rural innovation projects through social networks analysis: A case study in spain,” Land, vol. 10, no. 6, p. 613, 2021.
  2. L. M. Berhan, A. L. Adams, W. L. McKether, and R. Kumar, “Board 14: Social networks analysis of african american engineering students at a pwi and an hbcu–a comparative study,” in 2019 ASEE Annual Conference & Exposition, 2019.
  3. C. Rollinger, “Amicitia sanctissime colenda,” Freundschaft und soziale Netzwerke in der Späten Republik, 2014.
  4. J. Dörpinghaus and A. Stefan, “Knowledge extraction and applications utilizing context data in knowledge graphs,” in 2019 Federated Conference on Computer Science and Information Systems (FedCSIS). IEEE, 2019, pp. 265–272.
  5. G. Rossetti, S. Citraro, and L. Milli, “Conformity: A path-aware homophily measure for node-attributed networks,” IEEE Intelligent Systems, vol. 36, no. 1, pp. 25–34, 2021.
  6. D. Fensel, U. Şimşek, K. Angele, E. Huaman, E. Kärle, O. Panasiuk, I. Toma, J. Umbrich, and A. Wahler, Introduction: What Is a Knowledge Graph? Cham: Springer International Publishing, 2020, pp. 1–10. [Online]. Available: https://doi.org/10.1007/978-3-030-37439-6_1
  7. L. Ehrlinger and W. Wöß, “Towards a definition of knowledge graphs.” SEMANTiCS (Posters, Demos, SuCCESS), vol. , no. 48, 2016.
  8. H. Paulheim, “Knowledge graph refinement: A survey of approaches and evaluation methods,” Semantic web, vol. 8, no. 3, pp. 489–508, 2017.
  9. M. A. Rodriguez and P. Neubauer, “The graph traversal pattern,” in Graph data management: Techniques and applications. IGI Global, 2012, pp. 29–46.
  10. ——, “Constructions from dots and lines,” Bulletin of the American Society for Information Science and Technology, vol. 36, no. 6, pp. 35–41, 2010.
  11. R. Diestel, Graphentheorie. Berlin: Springer, 2012, vol. 4. Auflage, korrigierter Nachdruck 2012.
  12. J. Matoušek, J. Nešetřil, and H. Mielke, Diskrete Mathematik. Berlin: Springer, 2007.
  13. M. O. Jackson, Social and Economic Networks. Princeton: University Press, 2010.
  14. D. J. Watts, “Networks, dynamics, and the small-world phenomenon,” American Journal of sociology, vol. 105, no. 2, pp. 493–527, 1999.
  15. L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215–239, 1978.
  16. P. J. Carrington, J. Scott, and S. Wasserman, Models and methods in social network analysis, ser. Structural Analyses in the Social Sciences, 27. Cambridge: University Press, 2005, vol. .
  17. L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, pp. 35–41, 1977.
  18. D. R. White and S. P. Borgatti, “Betweenness centrality measures for directed graphs,” Social networks, vol. 16, no. 4, pp. 335–346, 1994.
  19. T. Schweizer, Muster sozialer Ordnung: Netzwerkanalyse als Fundament der Sozialethnologie. Berlin: D. Reimer, 1996.
  20. P. Bonacich, “Factoring and weighting approaches to status scores and clique identification,” Journal of mathematical sociology, vol. 2, no. 1, pp. 113–120, 1972.
  21. S. P. Borgatti, “Centrality and network flow,” Social networks, vol. 27, no. 1, pp. 55–71, 2005.
  22. M. Ditsworth and J. Ruths, “Community detection via katz and eigenvector centrality,” arXiv preprint https://arxiv.org/abs/1909.03916, 2019.
  23. B. Bollobás, C. Borgs, J. T. Chayes, and O. Riordan, “Directed scale-free graphs.” in SODA, vol. 3, 2003, pp. 132–139.
  24. B. Bollobás and O. M. Riordan, “Mathematical results on scale-free random graphs,” Handbook of graphs and networks: from the genome to the internet, pp. 1–34, 2003.
  25. M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” Journal of complex networks, vol. 2, no. 3, pp. 203–271, 2014.
  26. M. Newman and D. Watts, “Renormalization group analysis of the small-world network model,” Physics Letters A, vol. 263, no. 4, pp. 341–346, 1999. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0375960199007574
  27. J. Aarstad, H. Ness, and S. A. Haugland, “In what ways are small-world and scale-free networks interrelated?” in 2013 IEEE International Conference on Industrial Technology (ICIT). IEEE, 2013, pp. 1483–1487.
  28. K. Klemm and V. M. Eguiluz, “Growing scale-free networks with small-world behavior,” Physical Review E, vol. 65, no. 5, p. 057102, 2002.