Evolution Models for Historical Networks
Project description
Our knowledge of prehistoric and ancient road networks is fragmentary:
contemporary maps are rarely available and far from modern standards of
precision. Some roads may be textually referenced and some are found to be
still in use today while the remains of others can only be spotted from the
air or sparsely sampled via groundpenetrating radar or excavation. Modern
maps of ancient networks thus emerge as a conglomeration of data from many
sources.
To predict missing links in incomplete networks and to better understand the
principles that drive the evolution of ancient road networks, we develop and
study domainspecific mathematical models.
A sequential model of network formation
We propose a novel model based on three simplifying assumptions concerning
the growth of ancient road networks:
Modeling assumptions

Roads are added in sequence as their construction is fast compared to
the lifespan of a network.

Traveling through the wilderness is prohibitively difficult, so
the road network will eventually contain adequate connections between
all pairs of significant settlements.

The course of connections optimizes a tradeoff between road
construction and travel costs.
Our model assumes a maximal network \(G = (V, E)\) of possible road
segments equipped with a terrain cost \(c \colon E \to
\mathbb{R}_{> 0}\), and a set of connections \(K \subseteq
\mathcal{P}_2(V)\) to establish, normally given as all pairs \(K =
\mathcal{P}_2(S)\) over a set of settlements \(S \subseteq V\). If
these connections are brought into an order \(\pi \in S(K)\), then a
subgraph of \(G\) emerges from the following procedure, parameterized by
\(\alpha \in [0, 1]\):
Network formation
 Initialize the set of roads \(R := \emptyset\).

For every connection \(\{u, v\} = \pi_i\) in order of \(\pi\):

Find a leastcost \(u\)\(v\)path \(P \subseteq E\) in \(G\)
according to edge costs \(c\).

For every edge \(e \in P\) with \(e \notin R\):
 Reduce the edge's cost to \(c(e) := \alpha c(e)\).
 Update \(R := R \cup \{e\}\).
 Return the road network \(G[R]\).
Key insights
We find that the oldest connections are by far the most influential: they
quickly form a backbone that dictates the development of the network as a
whole. While we can show that identifying a construction order
with desirable properties (low cost or good agreement with spatial
evidence) is a computationally hard task, this observation enables us to
compress the younger history and identify plausible orders heuristically.
In a case study of the Roman road network on Sardinia, the outcome is in
good agreement with reconstructions from the literature.
References
2023
 Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis (Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke, and Max Klimm)
PNAS Nexus, 2(2), 2023.
@article{StahlbergSagnolDucke+2022,
author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
title = {Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential CostBenefit Analysis},
journal = {PNAS Nexus},
year = {2023},
volume = {2},
number = {2},
doi = {10.1093/pnasnexus/pgac313},
}
The construction of ancient road networks spanned generations and exhibits temporal path dependence that is not fully captured by established network formation models that are used to support archaeological reasoning. We introduce an evolutionary model that captures explicitly the sequential nature of road network formation: A central feature is that connections are added successively and according to an optimal cost–benefit tradeoff with respect to existing connections. In this model, the network topology emerges rapidly from early decisions, a trait that makes it possible to identify plausible road construction orders in practice. Based on this observation we develop a method to compress the search space of pathdependent optimization problems. We use this method to show that the model's assumptions on ancient decision making allow the reconstruction of partially known road networks from the Roman era in good detail and from sparse archaeological evidence. In particular, we identify missing links in the major road network of ancient Sardinia that are in good agreement with expert predictions.
Outreach

Challenge 20 of the
MATH+ Advent Calendar 2021 is a winterthemed
riddle about spatiotemporal reasoning, aimed at school students.

An
article in the German newspaper Tagesspiegel
discusses our results.
Data and source code
Available at
GitLab.