Abstract
In this work we study the topological properties of temporal hypergraphs. Hypergraphs provide a higher dimensional generalization of a graph that is capable of capturing multi-way connections. As such, they have become an integral part of network science. A common use of hypergraphs is to model events as hyperedges in which the event can involve many elements as nodes. This provides a more complete picture of the event, which is not limited by the standard dyadic connections of a graph. However, a common attribution to events is temporal information as an interval for when the event occurred. Consequently, a temporal hypergraph is born, which accurately captures both the temporal information of events and their multi-way connections. Common tools for studying these temporal hypergraphs typically capture changes in the underlying dynamics with summary statistics of snapshots sampled in a sliding window procedure. However, these tools do not characterize the evolution of hypergraph structure over time, nor do they provide insight on persistent components which are influential to the underlying system. To alleviate this need, we leverage zigzag persistence from the field of Topological Data Analysis (TDA) to study the change in topological structure of time-evolving hypergraphs. We apply our pipeline to both a cyber security and social network dataset and show how the topological structure of their temporal hypergraphs change and can be used to understand the underlying dynamics.
Information release number: PNNL-SA-181478.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Notice we use “topology” here in the formal sense, as distinct from how this is used informally in graph applications to refer to connectivity patterns in networks.
- 2.
HyperNetX: https://pnnl.github.io/HyperNetX.
- 3.
Dionysus2: https://mrzv.org/software/dionysus2/.
References
Adams, H., et al.: Persistence images: a stable vector representation of persistent homology. J. Mach. Learn. Res. 18(8), 1–35 (2017). http://jmlr.org/papers/v18/16-337.html
Agency, D.A.R.P.: Operationally transparent cyber (OpTC) data release (2020)
Aktas, M.E., Akbas, E., Fatmaoui, A.E.: Persistence homology of networks: methods and applications. Appl. Netw. Sci. 4(1), 1–28 (2019). https://doi.org/10.1007/s41109-019-0179-3
Amézquita, E.J., Quigley, M.Y., Ophelders, T., Munch, E., Chitwood, D.H.: The shape of things to come: topological data analysis and biology, from molecules to organisms. Dev. Dyn. 249(7), 816–833 (2020). https://doi.org/10.1002/dvdy.175
Baumgartner, J., Zannettou, S., Keegan, B., Squire, M., Blackburn, J.: The pushshift reddit dataset. PUSHSHIFT (2020). https://doi.org/10.5281/zenodo.3608135. Reddit-hazelnut prepared for the Social Network ProblemShop (Jan 24-Feb 4, 2022). Ottawa, Canada. Derivative of Reddit data obtained via pushshift.io API for the period January 1, 2019 to February 28
Bubenik, P.: Statistical topological data analysis using persistence landscapes. J. Mach. Learn. Res. 16(3), 77–102 (2015). http://jmlr.org/papers/v16/bubenik15a.html
Carlsson, G., de Silva, V.: Zigzag persistence. Found. Comput. Math. 10(4), 367–405 (2010). https://doi.org/10.1007/s10208-010-9066-0
Cencetti, G., Battiston, F., Lepri, B., Karsai, M.: Temporal properties of higher-order interactions in social networks. Sci. Rep. 11(1) (2021). https://doi.org/10.1038/s41598-021-86469-8
David Boyce, B.R.: Modeling Dynamic Transportation Networks. Springer, Berlin Heidelberg (2012)
Edelsbrunner, L.: Zomorodian: topological persistence and simplification. Discrete Comput. Geom. 28(4), 511–533 (2002). https://doi.org/10.1007/s00454-002-2885-2
Estrada, E., Rodríguez-Velázquez, J.A.: Subgraph centrality and clustering in complex hyper-networks. Phys. A: Stat. Mech. Appl. 364, 581–594 (2006). https://doi.org/10.1016/j.physa.2005.12.002
Feng, S., et al.: Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC Bioinf. 22(1), 1–21 (2021). https://doi.org/10.1186/s12859-021-04197-2
Fischer, M.T., Arya, D., Streeb, D., Seebacher, D., Keim, D.A., Worring, M.: Visual analytics for temporal hypergraph model exploration. IEEE Trans. Vis. Comput. Graph. 27(2), 550–560 (2021). https://doi.org/10.1109/tvcg.2020.3030408
Gasparovic, E., et al.: Homology of graphs and hypergraphs (2021). https://www.youtube.com/watch?v=XeNBysFcwOw
Golczynski, A., Emanuello, J.A.: End-to-end anomaly detection for identifying malicious cyber behavior through NLP-based log embeddings. arXiv preprint arXiv:2108.12276 (2021)
Hanselmann, M., Strauss, T., Dormann, K., Ulmer, H.: CANet: an unsupervised intrusion detection system for high dimensional can bus data. IEEE Access 8, 58194–58205 (2020)
Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79–87 (1997). https://doi.org/10.1016/s0895-7177(97)00050-2
Husein, I., Mawengkang, H., Suwilo, S., Mardiningsih: modeling the transmission of infectious disease in a dynamic network. J. Phys.: Conf. Ser. 1255(1), 012052 (2019). https://doi.org/10.1088/1742-6596/1255/1/012052
Joslyn, C.A., et al.: Hypernetwork science: from multidimensional networks to computational topology. In: Braha, D., et al. (eds.) ICCS 2020. SPC, pp. 377–392. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-67318-5_25
Khasawneh, F., Munch, E.: Chatter detection in turning using persistent homology. Mech. Syst. Signal Process. 70–71, 527–541 (2016). https://doi.org/10.1016/j.ymssp.2015.09.046
Munch, E.: A user’s guide to topological data analysis. J. Learn. Anal. 4(2), 47–61 (2017). https://doi.org/10.18608/jla.2017.42.6
Myers, A., Munch, E., Khasawneh, F.A.: Persistent homology of complex networks for dynamic state detection. Phys. Rev. E 100(2), 022314 (2019). https://doi.org/10.1103/physreve.100.022314
Myers, A., Muñoz, D., Khasawneh, F., Munch, E.: Temporal network analysis using zigzag persistence. EPJ Data Sci. 12(1), 6 (2022)
Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6(1), 1–38 (2017). https://doi.org/10.1140/epjds/s13688-017-0109-5
Ren, S.: Persistent homology for hypergraphs and computational tools—a survey for users. J. Knot Theory Ramifications 29(13), 2043007 (2020). https://doi.org/10.1142/s0218216520430075
Schäfer, B., Witthaut, D., Timme, M., Latora, V.: Dynamically induced cascading failures in power grids. Nat. Commun. 9(1), 1975 (2018). https://doi.org/10.1038/s41467-018-04287-5
Skaf, Y., Laubenbacher, R.: Topological data analysis in biomedicine: a review. J. Biomed. Inf. 130, 104082 (2022). https://doi.org/10.1016/j.jbi.2022.104082
Skyrms, B., Pemantle, R.: A dynamic model of social network formation. Proc. Natl. Acad. Sci. 97(16), 9340–9346 (2000). https://doi.org/10.1073/pnas.97.16.9340
Tempelman, J.R., Khasawneh, F.A.: A look into chaos detection through topological data analysis. Phys. D: Nonlinear Phenom. 406, 132446 (2020). https://doi.org/10.1016/j.physd.2020.132446
Tymochko, S., Munch, E., Khasawneh, F.: Using zigzag persistent homology to detect Hopf bifurcations in dynamical systems. Algorithms 13(11), 278 (2020). https://doi.org/10.3390/a13110278
Xu, M., Radhakrishnan, S., Kamarthi, S., Jin, X.: Resiliency of mutualistic supplier-manufacturer networks. Sci. Rep. 9(1), 1–10 (2019). https://doi.org/10.1038/s41598-019-49932-1
Yesilli, M.C., Chumley, M.M., Chen, J., Khasawneh, F.A., Guo, Y.: Exploring surface texture quantification in piezo vibration striking treatment (PVST) using topological measures. In: Volume 2: Manufacturing Processes; Manufacturing Systems. American Society of Mechanical Engineers (2022). https://doi.org/10.1115/msec2022-86659
Zomorodian, A., Carlsson, G.: Computing persistent homology. Discrete Comput. Geom. 33(2), 249–274 (2004). https://doi.org/10.1007/s00454-004-1146-y
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Myers, A., Joslyn, C., Kay, B., Purvine, E., Roek, G., Shapiro, M. (2023). Topological Analysis of Temporal Hypergraphs. In: Dewar, M., Prałat, P., Szufel, P., Théberge, F., Wrzosek, M. (eds) Algorithms and Models for the Web Graph. WAW 2023. Lecture Notes in Computer Science, vol 13894. Springer, Cham. https://doi.org/10.1007/978-3-031-32296-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-32296-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32295-2
Online ISBN: 978-3-031-32296-9
eBook Packages: Computer ScienceComputer Science (R0)