A Bit of History
Claude Berge — already met in this series for his augmenting-path matching theorem (Part 16) and the Strong Perfect Graph Conjecture (Part 18) — formalized hypergraph theory as its own systematic field in his 1970s books, giving group-based relationships their own rigorous mathematical vocabulary distinct from ordinary graphs. Temporal networks were surveyed comprehensively by Petter Holme and Jari Saramäki in an influential 2012 review, "Temporal Networks," which helped consolidate a previously scattered set of time-varying-graph techniques into a coherent subfield. Mikko Kivelä and coauthors then published a unifying mathematical framework for multilayer networks in 2014, showing that many previously separate "multi-relational," "interdependent," and "multiplex" network models were all special cases of one general structure.
Hypergraphs
A hypergraph generalizes a graph by allowing each hyperedge to connect any number of vertices at once, not just two. Formally, a hypergraph is a pair \((V, E)\) where each hyperedge \(e \in E\) is an arbitrary non-empty subset of \(V\). Ordinary graphs are exactly the special case where every hyperedge has size 2.
Key Insight
Many real relationships are inherently group-based, not pairwise — a research paper's co-authorship involves however many authors wrote it; an email thread includes however many people were CC'd; a committee meeting involves everyone present. Forcing these onto an ordinary graph (e.g., connecting every pair of co-authors) discards the fact that they occurred together as a single group — information a hypergraph preserves natively.
Several graph concepts generalize naturally: a hypergraph's matching is a set of pairwise-disjoint hyperedges, and its coloring assigns colors to vertices so no hyperedge is entirely one color. Hypergraph coloring is considerably harder in general than graph coloring (Part 13), since a "conflict" can now involve arbitrarily many vertices simultaneously rather than just a pair.
Temporal Networks
A temporal network (also called a time-varying graph) associates each edge with one or more specific timestamps or time intervals, rather than treating connectivity as permanently fixed. This changes some of the most basic graph-theoretic questions in surprising ways: a temporal path from \(u\) to \(v\) must use edges in strictly increasing time order, meaning a path can exist in the "underlying" static graph while no valid temporal path exists at all — connectivity in the ordinary sense (Part 5-8) does not guarantee "reachability over time."
This distinction matters enormously for anything modeling real spreading processes — a disease, a rumor, a piece of information — since these can only travel forward through time along edges that were actually active when needed, not along edges that existed at some other unrelated moment.
Multilayer Networks
A multilayer network models multiple distinct types of relationships among the same (or overlapping) sets of entities simultaneously — for example, the same group of people connected by a "friendship" layer, a "coworker" layer, and a "family" layer all at once, each with potentially different edges. Kivelä et al.'s 2014 framework unifies several previously separate special cases:
- Multiplex networks: the same vertex set appears in every layer, connected only "vertically" to its own copies in other layers.
- Interdependent networks: different vertex sets across layers, with cross-layer dependency edges (e.g., a power grid layer and a communications-network layer that depend on each other).
- Temporal networks (again): can themselves be modeled as a special multilayer network, where each layer represents one time slice.
Real-World Applications
Epidemic Modeling on Temporal Contact Networks
Epidemiologists model disease spread using temporal networks of actual person-to-person contacts (who was near whom, and precisely when) rather than a static "who knows whom" graph, since a disease can only spread along a contact that was active at exactly the right moment — a temporal path, not merely a static one. This distinction proved critical to real contact-tracing systems developed during COVID-19, which needed to reconstruct genuine temporal transmission chains rather than simply flagging anyone ever connected in the underlying static social graph.
Exercises
- Model a 4-person email thread (all 4 people received every message) as a hypergraph, and contrast it with modeling the same thread as an ordinary graph connecting every pair.
- Construct a small example of a temporal network where a "path" exists in the underlying static graph, but no valid temporal path exists because the timestamps are in the wrong order.
- Describe, in your own words, the difference between a multiplex network and an interdependent network, using the friendship/coworker/family layer example.
- Challenge: Research how contact-tracing apps during the COVID-19 pandemic modeled temporal proximity data, and discuss whether they needed true temporal-path reasoning or a simpler static approximation.
Conclusion & Next Steps
Hypergraphs, temporal networks, and multilayer networks all relax a core assumption of the ordinary graphs this series has used throughout — pairwise, static, single-relationship-type edges — to better capture the messiness of real-world relational data. With these richer structures introduced, the series turns next to network science proper: the empirical study of what large real-world networks actually look like, and why.
Next in the Series
In Part 25: Network Science, the series turns to the empirical study of what large real-world networks actually look like, and why.