Logo PTI Logo FedCSIS

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

Annals of Computer Science and Information Systems, Volume 37

Towards modelling and analysis of longitudinal social networks

, ,

DOI: http://dx.doi.org/10.15439/2023F4965

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

Full text

Abstract. There are currently several approaches to managing longitudinal data in graphs and social networks. All of them influence the output of algorithms that analyse the data. We present an overview of limitations, possible solutions and open questions for different data schemas for temporal data in social networks, based on a generic RDF-inspired approach that is equivalent to existing approaches. While restricting the algorithms to a specific time point or layer does not affect the results, applying these approaches to a network with multiple time points requires either adapted algorithms or reinterpretation. Thus, with a generic definition of temporal networks as one graph, we will answer the question of how we can analyse longitudinal social networks with centrality measures. In addition, we present two approaches to approximate the change in degree and betweenness centrality measures over time.

References

  1. J. Leidwanger, C. Knappett, P. Arnaud, P. Arthur, E. Blake, C. Broodbank, T. Brughmans, T. Evans, S. Graham, E. S. Greene et al., “A manifesto for the study of ancient mediterranean maritime networks,” Antiquity, vol. 88, no. 342, 2014.
  2. S. de Valeriola, “Can historians trust centrality?” Journal of Historical Network Research, vol. 6, no. 1, 2021.
  3. I. Scholtes, N. Wider, R. Pfitzner, A. Garas, C. J. Tessone, and F. Schweitzer, “Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks,” Nature communications, vol. 5, no. 1, p. 5024, 2014.
  4. K. S. Xu and A. O. Hero, “Dynamic stochastic blockmodels: Statistical models for time-evolving networks,” in Social Computing, BehavioralCultural Modeling and Prediction: 6th International Conference, SBP 2013, Washington, DC, USA, April 2-5, 2013. Proceedings 6. Springer, 2013, pp. 201–210.
  5. P. Holme and J. Saramäki, “Temporal networks,” Physics reports, vol. 519, no. 3, pp. 97–125, 2012.
  6. G. Cencetti, F. Battiston, B. Lepri, and M. Karsai, “Temporal properties of higher-order interactions in social networks,” Scientific reports, vol. 11, no. 1, p. 7028, 2021.
  7. J. S. Yi, N. Elmqvist, and S. Lee, “Timematrix: Analyzing temporal social networks using interactive matrix-based visualizations,” Intl. Journal of Human–Computer Interaction, vol. 26, no. 11-12, pp. 1031–1051, 2010.
  8. M. Franzke, T. Emrich, A. Züfle, and M. Renz, “Pattern search in temporal social networks,” in Proceedings of the 21st International Conference on Extending Database Technology, 2018.
  9. S. Hanneke, W. Fu, and E. P. Xing, “Discrete temporal models of social networks,” Electronic Journal of Statistics, vol. 4, pp. 585–605, 2010.
  10. R. K. Pan and J. Saramäki, “Path lengths, correlations, and centrality in temporal networks,” Physical Review E, vol. 84, no. 1, p. 016105, 2011.
  11. D. Taylor, S. A. Myers, A. Clauset, M. A. Porter, and P. J. Mucha, “Eigenvector-based centrality measures for temporal networks,” Multi-scale Modeling & Simulation, vol. 15, no. 1, pp. 537–574, 2017.
  12. A. E. Sizemore and D. S. Bassett, “Dynamic graph metrics: Tutorial, toolbox, and tale,” NeuroImage, vol. 180, pp. 417–427, 2018.
  13. M. G. Everett and S. P. Borgatti, “The centrality of groups and classes,” The Journal of mathematical sociology, vol. 23, no. 3, pp. 181–201, 1999.
  14. S. Rasti and C. Vogiatzis, “Novel centrality metrics for studying essentiality in protein-protein interaction networks based on group structures,” Networks, vol. 80, no. 1, pp. 3–50, 2022.
  15. E.-Y. Yu, Y. Fu, X. Chen, M. Xie, and D.-B. Chen, “Identifying critical nodes in temporal networks by network embedding,” Scientific reports, vol. 10, no. 1, p. 12494, 2020.
  16. P. Cinaglia and M. Cannataro, “Network alignment and motif discovery in dynamic networks,” Network Modeling Analysis in Health Informatics and Bioinformatics, vol. 11, no. 1, p. 38, 2022.
  17. 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.
  18. C. Barats, V. Schafer, and A. Fickers, “Fading away... the challenge of sustainability in digital studies.” DHQ: Digital Humanities Quarterly, vol. 14, no. 3, 2020.
  19. D. Santoro and I. Sarpe, “Onbra: Rigorous estimation of the temporal betweenness centrality in temporal networks,” in Proceedings of the ACM Web Conference 2022, 2022, pp. 1579–1588.
  20. J. R. Hobbs and F. Pan, “An ontology of time for the semantic web,” ACM Transactions on Asian Language Information Processing (TALIP), vol. 3, no. 1, pp. 66–85, 2004.
  21. M. Grüninger, “Verification of the owl-time ontology,” in The Semantic Web–ISWC 2011: 10th International Semantic Web Conference, Bonn, Germany, October 23-27, 2011, Proceedings, Part I 10. Springer, 2011, pp. 225–240.
  22. V. Nicosia, J. Tang, C. Mascolo, M. Musolesi, G. Russo, and V. Latora, “Graph metrics for temporal networks,” Temporal networks, pp. 15–40, 2013.
  23. L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, pp. 35–41, 1977.
  24. T. Schweizer, Muster sozialer Ordnung: Netzwerkanalyse als Fundament der Sozialethnologie. Berlin: D. Reimer, 1996.
  25. M. O. Jackson, Social and Economic Networks. Princeton: University Press, 2010.
  26. D. J. Watts, “Networks, dynamics, and the small-world phenomenon,” American Journal of sociology, vol. 105, no. 2, pp. 493–527, 1999.
  27. B. Bollobás, C. Borgs, J. T. Chayes, and O. Riordan, “Directed scale-free graphs.” in SODA, vol. 3, 2003, pp. 132–139.
  28. 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.
  29. 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.
  30. S. Milgram, “The small world problem,” Psychology today, vol. 2, no. 1, pp. 60–67, 1967.
  31. D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.
  32. J. S. Kleinfeld, “The small world problem,” Society, vol. 39, no. 2, pp. 61–66, 2002.
  33. O. Riordan et al., “The diameter of a scale-free random graph,” Combinatorica, vol. 24, no. 1, pp. 5–34, 2004.
  34. F. Ma, X. Wang, and P. Wang, “Scale-free networks with invariable diameter and density feature: Counterexamples,” Physical Review E, vol. 101, no. 2, p. 022315, 2020.
  35. L. Gu, H. L. Huang, and X. D. Zhang, “The clustering coefficient and the diameter of small-world networks,” Acta Mathematica Sinica, English Series, vol. 29, no. 1, pp. 199–208, 2013.
  36. C. Martel and V. Nguyen, “Analyzing kleinberg’s (and other) small-world models,” in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004, pp. 179–188.