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.
Three Ways Ordinary Graphs Can Lose Information
An ordinary graph answers one question very well: which pairs of vertices are connected? The three models in this part keep the graph idea but relax a different assumption. A hypergraph asks who participated together; a temporal network asks when a connection was usable; a multilayer network asks what kind of relationship the connection belongs to.
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.
Additional context: if every hyperedge has exactly k vertices, the hypergraph is called k-uniform. Ordinary simple graphs are therefore exactly 2-uniform hypergraphs. This is a useful memory bridge: a hypergraph does not replace graph theory so much as widen the allowed edge size.
One Four-Person Event Is Not the Same as Six Pairwise Events
A common way to turn a hypergraph into an ordinary graph is the 2-section or clique projection: connect two vertices whenever they appear together in some hyperedge. That can be useful, but it loses information. A single four-person meeting and six separate two-person meetings both become the same complete graph on four vertices.
The Incidence View: Turn Hyperedges into Nodes
Another useful representation keeps the group information intact: build a bipartite incidence graph. Put the original vertices on one side, create one node for every hyperedge on the other, and connect a vertex to the hyperedge-nodes it belongs to. This lets you reuse many ordinary bipartite-graph ideas without pretending that a group interaction was merely a collection of independent pairs.
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.
Convention note: temporal-graph literature sometimes allows nondecreasing timestamps when multiple transfers may happen at the same recorded time. This article keeps the stricter increasing-time convention from the definition above. Either way, the essential rule is causal order: later steps cannot use edges from the past.
The Same Static Path Can Be Usable or Impossible
Suppose the underlying graph contains the path A-B-C-D. That is not enough. The edge times must line up in the order the traveler, message, or infection needs them.
Temporal Reachability Can Be Directional Without Directed Edges
A particularly useful intuition is that time itself creates direction. Even if every contact is undirected when it occurs, A may be able to reach D through a sequence of later and later contacts while D cannot retrace that route back to A because those earlier contacts have already passed. Temporal reachability can therefore fail to be symmetric even when every individual edge is symmetric.
Additional context: this leads naturally to optimization questions such as earliest-arrival paths (reach the destination as soon as possible), fastest paths (minimize elapsed travel time), and latest-departure paths (leave as late as possible while still arriving by a deadline). They are all “shortest-path-like” questions, but their state includes time.
Memory Aid: Static Connectivity Is Permission; Temporal Connectivity Is a Schedule
The static graph says which transfers are possible at some time. A temporal path proves that those transfers can actually be chained in causal order.
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.
Layers Can Mean Repeated Entities or Entirely Different Systems
Why Flattening Layers Can Invent Paths That Do Not Exist
If you merge every layer into one ordinary graph, you may create a path that silently switches relationship type at every step. That might be acceptable for some questions (“can these people reach one another by any relation?”), but wrong for others (“can information travel using coworker links only?”). Layer-aware paths can constrain which layer transitions are allowed and what they cost.
Choosing the Right Model
These representations are not competitors. They answer different questions, and real systems often need more than one at once. A useful diagnostic is to ask what information would become impossible to recover if I collapsed the data into an ordinary graph?
| Question you need to preserve | Natural model | What an ordinary graph may lose |
|---|---|---|
| Who participated in the same group event? | Hypergraph | Which pairwise links came from the same event |
| Could influence actually travel in causal order? | Temporal network | Timestamp order and waiting constraints |
| Which relationship or infrastructure carried the link? | Multilayer network | Layer identity and allowed cross-layer transitions |
| All three at once | Higher-order temporal multilayer model | Group, time, and context simultaneously |
- Hypergraph
Edge size can exceed 2. - Temporal
Path validity depends on time order. - Multilayer
Edges live in relationship contexts. - Projection
Useful, but often lossy. - Incidence view
Group membership becomes bipartite structure. - Model choice
Preserve the information your question needs.
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.
Richer models can go further: a classroom, household, or meeting can be represented as a time-stamped group contact (hypergraph + temporal information), while separate layers can distinguish household, workplace, transit, and healthcare contacts. The point is not to use the richest possible model automatically, but to preserve the mechanisms that matter to the question being studied.
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. The deeper lesson is about representation: collapsing rich data into a plain graph can make algorithms easier, but it can also erase the exact group, time, or context information your question depends on. 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.