Abstract
As data structures and mathematical objects used for complex systems modeling, hypergraphs sit nicely poised between on the one hand the world of network models, and on the other that of higher-order mathematical abstractions from algebra, lattice theory, and topology. They are able to represent complex systems interactions more faithfully than graphs and networks, while also being some of the simplest classes of systems representing topological structures as collections of multidimensional objects connected in a particular pattern. In this paper we discuss the role of (undirected) hypergraphs in the science of complex networks, and provide a mathematical overview of the core concepts needed for hypernetwork modeling, including duality and the relationship to bicolored graphs, quantitative adjacency and incidence, the nature of walks in hypergraphs, and available topological relationships and properties. We close with a brief discussion of two example applications: biomedical databases for disease analysis, and domain-name system (DNS) analysis of cyber data.
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
Notes
- 1.
- 2.
Hypergraph calculations shown in this paper were produced using PNNL’s open source hypergraph analytical capabilities HyperNetX (HNX, https://github.com/pnnl/HyperNetX) and the Chapel Hypergraph Library (CHGL, https://github.com/pnnl/chgl); and additionally diagrams were produced in HNX.
- 3.
Typically the concept of a bipartite graph is used here, which is a graph that admits to at least one bicoloring function. The resulting differences are interesting, but not significant for this paper.
- 4.
- 5.
- 6.
- 7.
- 8.
https://github.com/callahantiff/PheKnowLator, downloaded on 03/05/20, see also https://github.com/callahantiff/PheKnowLator/wiki/v2-Data-Sources.
- 9.
References
Aksoy, S.G., Joslyn, C.A., Marrero, C.O., Praggastis, B., Purvine, E.A.: Hypernetwork science via high-order hypergraph walks. EPJ Data Sci. 9, 16 (2020)
Alon, N.: Transversal numbers of uniform hypergraphs. Graphs Comb. 6(1), 1–4 (1990)
Ausiello, G., Fanciosa, P.G., Frigioni, D.: Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach. In: ICTCS 2001, LNCS, vol. 2202, pp. 312–328 (2001)
Barabási, A.L.: Network Science. Cambridge University Press, Cambridge (2016)
Barber, M.J.: Modularity and community detection in bipartite networks. Phys. Rev. E 76(6) (2007). https://doi.org/10.1103/physreve.76.066102
Berge, C., Minieka, E.: Graphs and Hypergraphs. North-Holland (1973)
Chung, F.: The laplacian of a hypergraph. Expanding graphs (DIMACS series), pp. 21–36 (1993)
Cooper, J., Dutle, A.: Spectra of uniform hypergraphs. Linear Algebr. Its Appl. 436(9), 3268–3292 (2012)
Devine, K., Boman, E., Heaphy, R., Bisseling, R., Catalyurek, U.: Parallel hypergraph partitioning for scientific computing. In: Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. IEEE (2006). https://doi.org/10.1109/ipdps.2006.1639359
Dewar, M., Healy, J., Pérez-Giménez, X., Prałat, P., Proos, J., Reiniger, B., Ternovsky, K.: Subhypergraphs in non-uniform random hypergraphs. Internet Math. (2018). https://doi.org/10.24166/im.03.2018
Dinur, I., Regev, O., Smyth, C.: The hardness of 3-uniform hypergraph coloring. Combinatorica 25(5), 519–535 (2005)
Dörfler, W., Waller, D.A.: A category-theoretical approach to hypergraphs. Archiv der Mathematik 34(1), 185–192 (1980). https://doi.org/10.1007/bf01224952
Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. AMS (2000)
Estrada, E., Rodríguez-Velázquez, J.A.: Subgraph centrality and clustering in complex hyper-networks. Phys. A: Stat. Mech. Its Appl. 364, 581–594 (2006). https://doi.org/10.1016/j.physa.2005.12.002
Fong, B., Spivak, D.I.: Hypergraph categories (2019)
Gallo, G., Longo, G., Pallottino, S.: Directed hypergraphs and applications. Discret. Appl. Math. 42, 177–201 (1993)
Iacopini, I., Petri, G., Barrat, A., Latora, V.: Simplicial models of social contagion. Nat. Commun. 10, 2485 (2019)
jamie.riden: How Fast-Flux Service Networks Work. http://www.honeynet.org/node/132. Last accessed 26 Nov 2018
Javidian, M.A., Lu, L., Valtorta, M., Qang, Z.: On a hypergraph probabilistic graphical model (2018). https://arxiv.org/abs/1811.08372
Johnson, J.: Hypernetworks in the Science of Complex Systems. Imperial College Press, London (2013)
Joslyn, C.A., Aksoy, S., Arendt, D., Firoz, J., Jenkins, L., Praggastis, B., Purvine, E.A., Zalewski, M.: Hypergraph analytics of domain name system relationships. In: Kaminski, B., et al. (eds.) 17th Workshop on Algorithms and Models for the Web Graph (WAW 2020). Lecture Notes Comput. Sci. 12901, 1–15. Springer (2020)
Karypis, G., Kumar, V.: Multilevel k-way hypergraph partitioning. VLSI Des. 11(3), 285–300 (2000). https://doi.org/10.1155/2000/19436
Kirkland, S.: Two-mode networks exhibiting data loss. J. Complex Netw. 6(2), 297–316 (2017). https://doi.org/10.1093/comnet/cnx039
Klamt, S., Haus, U.U., Theis, F.: Hypergraphs and cellular networks. PLoS Comput. Biol. 5(5), e1000,385 (2009)
Krivelevich, M., Sudakov, B.: Approximate coloring of uniform hypergraphs. J. Algorithms 49(1), 2–12 (2003)
Larremore, D.B., Clauset, A., Jacobs, A.Z.: Efficiently inferring community structure in bipartite networks. Phys. Rev. E 90(1) (2014). https://doi.org/10.1103/physreve.90.012805
Latapy, M., Magnien, C., Vecchio, N.D.: Basic notions for the analysis of large two-mode networks. Soc. Netw. 30(1), 31–48 (2008). https://doi.org/10.1016/j.socnet.2007.04.006
Leal, W., Restrepo, G.: Formal structure of periodic system of elements. Proc. R. Soc. A. 475 (2019). https://doi.org/10.1098/rspa.2018.0581
Minas, M.: Hypergraphs as a unifrom diagram representation model. In: Proceedings of the 6th International Workshop on Theory and Applications of Graph Transformations (2000). ftp://ftp.informatik.uni-erlangen.de/local/inf2/Papers/tagt98.pdf
Patania, A., Petri, G., Vaccarino, F.: Shape of collaborations. EPJ Data Sci. 6, 18 (2017)
Robins, G., Alexander, M.: Small worlds among interlocking directors: network structure and distance in bipartite graphs. Comput. Math. Organ. Theory 10(1), 69–94 (2004). https://doi.org/10.1023/b:cmot.0000032580.12184.c0
Rödl, V., Skokan, J.: Regularity lemma for k-uniform hypergraphs. Random Struct. Algorithms 25(1), 1–42 (2004)
Schmidt, M.: Functorial approach to graph and hypergraph theory (2019)
Acknowledgements
PNNL-SA-152208. This work was also partially funded under the High Performance Data Analytics (HPDA) program at the Department of Energy’s Pacific Northwest National Laboratory. Pacific Northwest National Laboratory is operated by Battelle Memorial Institute under Contract DE-ACO6-76RL01830.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Joslyn, C.A. et al. (2021). Hypernetwork Science: From Multidimensional Networks to Computational Topology. In: Braha, D., et al. Unifying Themes in Complex Systems X. ICCS 2020. Springer Proceedings in Complexity. Springer, Cham. https://doi.org/10.1007/978-3-030-67318-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-030-67318-5_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-67317-8
Online ISBN: 978-3-030-67318-5
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)