Logo PTI Logo FedCSIS

Communication Papers of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 49

Predicting Centrality Measures in Complex Networks Utilizing Markov Chains

, ,

DOI: http://dx.doi.org/10.15439/2026F9619

Citation: Anchal Gera, ,

Full text

Abstract. Centrality measures are of critical importance for the identification of influential nodes in networks. However, classical metrics such as degree and betweenness are static and thus fail to capture temporal dynamics. The present paper introduces a probabilistic framework for modelling centrality as a stochastic process using Markov chains. By discretising centrality values into states, transition probability matrices are learned from temporal data, enabling future centrality prediction. First-order and higher-order models were evaluated, with the results indicating that higher-order models improve accuracy, particularly for betweenness. The results of the study indicate that centrality is inherently dynamic and probabilistic. The proposed framework offers an interpretable method to forecast node importance and distinguish stable from volatile influencers in evolving networks.

References

  1. V. Sekara, A. Stopczynski, and S. Lehmann, “Fundamental structures of dynamic social networks,” Proceedings of the national academy of sciences, vol. 113, no. 36, pp. 9977–9982, 2016.
  2. J. Dörpinghaus, “Die soziale Netzwerkanalyse: Neue Perspektiven für die Auslegung biblischer Texte?” Biblisch erneuerte Theologie, vol. 5, pp. 75–96, 2021.
  3. F. Grando, L. Z. Granville, and L. C. Lamb, “Machine learning in network centrality measures: Tutorial and outlook,” ACM Computing Surveys (CSUR), vol. 51, no. 5, pp. 1–32, 2018.
  4. J. Dörpinghaus, “Digital theology: New perspectives on interdisciplinary research between the humanities and theology.” Interdisciplinary Journal of Research on Religion, vol. 18, p. 1, 2022.
  5. J. Dörpinghaus and M. Jacobs, “Semantic knowledge graph embeddings for biomedical research: Data integration using linked open data.” in SEMANTiCS (Posters & Demos), 2019.
  6. J. Dörpinghaus, S. Schaaf, and M. Jacobs, “Soft document clustering using a novel graph covering approach,” BioData mining, vol. 11, no. 1, p. 11, 2018.
  7. J. Dörpinghaus, J. Klein, J. Darms, S. Madan, and M. Jacobs, “Scaiviewa semantic search engine for biomedical research utilizing a microservice architecture.” in SEMANTiCS (Posters & Demos), 2018.
  8. J. Dörpinghaus, D. Samray, and R. Helmrich, “Challenges of automated identification of access to education and training in germany,” Information, vol. 14, no. 10, p. 524, 2023.
  9. M. P. Mangroliya, J. Doerpinghaus, and R. Rockenfeller, “Towards the analysis of errors in centrality measures in perpetuated networks,” pp. 417–428. [Online]. Available: https://annals-csis.org/Volume_39/ drp/4841.html
  10. H. T. Tu, T. T. Phan, and K. P. Nguyen, “Modeling information diffusion in social networks with ordinary linear differential equations,” Information Sciences, vol. 593, pp. 614–636, 2022.
  11. B. Tadić and R. Melnik, “Self-organised critical dynamics as a key to fundamental features of complexity in physical, biological, and social networks,” Dynamics, vol. 1, no. 2, pp. 181–197, 2021.
  12. W.-N. Chen, D.-Z. Tan, Q. Yang, T. Gu, and J. Zhang, “Ant colony optimization for the control of pollutant spreading on social networks,” IEEE Transactions on Cybernetics, vol. 50, no. 9, pp. 4053–4065, 2019.
  13. F. Menczer, S. Fortunato, and C. A. Davis, A First Course in Network Science, 1st ed. Cambridge University Press. [Online]. Available: https://www. cambridge.org/highereducation/books/first-course-in-network-science/ EE22722F27519D8BB1443C7225C57BAF#contents
  14. L. C. Freeman, The Development of Social Network Analysis: A Study in the Sociology of Science. Empirical Press ; BookSurge.
  15. M. E. J. Newman, Networks: An Introduction. Oxford University Press, 2010.
  16. L. C. Freeman, “Centrality in social networks: Conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215–239, 1978.
  17. L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, no. 1, pp. 35–41, 1977.
  18. D. F. Gleich and R. A. Rossi, “A Dynamical System for PageRank with Time-Dependent Teleportation,” Internet Mathematics, vol. 10, no. 1-2, pp. 188–217, Apr. 2014.
  19. C. E. Graafland, J. M. Gutiérrez, J. M. López, D. Pazó, and M. A. Rodríguez, “The probabilistic backbone of data-driven complex networks: An example in climate,” Scientific Reports, vol. 10, no. 1, p. 11484, Jul. 2020.
  20. N. Friedman, K. Murphy, and S. Russell, “Learning the Structure of Dynamic Probabilistic Networks.”
  21. G. Ghoshal and A.-L. Barabási, “Ranking stability and super-stable nodes in complex networks,” vol. 2, no. 1, p. 394. [Online]. Available: https://www.nature.com/articles/ncomms1396
  22. M. Ruan, X. Chen, and H. Zhou, “Centrality prediction based on K-order Markov chain in Mobile Social Networks,” vol. 12, no. 6, pp. 1662–1672. [Online]. Available: http://link.springer.com/10.1007/ s12083-019-00746-y
  23. S. Bartolucci, F. Caccioli, F. Caravelli, and P. Vivo, “Distribution of centrality measures on undirected random networks via the cavity method,” Proceedings of the National Academy of Sciences, vol. 121, no. 40, p. e2403682121, Oct. 2024.
  24. Markov-Chain based centralities and Space Syntax’ Angular Analysis: an initial overview and application, Krakow, Poland, 2023.
  25. J. G. Kemeny and J. L. Snell, Finite Markov Chains. Princeton, NJ: D. Van Nostrand, 1960.
  26. S. N. Mohammed and S. Gündüç, “TPM: Transition Probability Matrix – Graph Structural Feature based Embedding,” Mar. 2023.
  27. D.-W. Huang and Z.-G. Yu, “Dynamic-Sensitive centrality of nodes in temporal networks,” vol. 7, no. 1, p. 41454. [Online]. Available: https://www.nature.com/articles/srep41454
  28. J. Dorpinghaus, V. Weil, C. Duing, and M. W. Sommer, “Centrality measures in multi-layer knowledge graphs,” Annals of Computer Science and Information Systems, vol. 32, 2022.
  29. J. Dörpinghaus, V. Weil, and M. W. Sommer, “Towards modeling and analysis of longitudinal social networks: J. dörpinghaus et al.” Applied Network Science, vol. 9, no. 1, p. 52, 2024.
  30. S. P. Borgatti, “Centrality and network flow,” Social Networks, vol. 27, pp. 55–71, 2005.