Mathematics, Discrete Optimization
Mathematics, Discrete Optimization

Evolution Models for Historical Networks

MATH+ identifier
EF5-6

Project heads
Benjamin Ducke (DAI), Max Klimm, Guillaume Sagnol

Project members
Maximilian Stahlberg

Project duration
04/2021 – 03/2024

Abstract
We study the evolution of historic and prehistoric networks using appropriate mathematical models. In archaeology, foundations and artifacts bear witness of past human settlements and the daily lives of their inhabitants. While artifacts can also provide proof of trade and social interaction between settlements, the exact trade routes and the development of social networks over time can rarely be recovered from the physical evidence alone. We would like to propose graph-theoretic models that generate plausible hypotheses of network formation, which may be used to explain the social or economic status of individual settlements or to discover likely contacts that could not be observed in the field.

Goals
We are looking for novel methods for the simulation of spatial network evolution with the following properties:

  • Plausibility: The method should be able to approximately recover the evolution of known historical networks.
  • Transparency: The method should make the core features of human decision making for spatial interaction visible.
  • Simplicity: The configuration should require few parameters that would ideally represent technical, cultural or economic quantities.

Approach
A possible starting point is a sequential road network evolution model proposed by Abraham et al. [1]. Based on the key assumption that long roads allow for faster travel than short ones, their method produces hierarchically structured networks with a constant highway dimension, a property that is empirically small in real world transportation networks. Focusing on this particular parameter, the authors disregard other properties of road networks, such as the tendency of new settlements to connect to existing roads. An extension of this model that would pursue additional or different properties appears attractive.

References

  1. Highway Dimension and Provably Efficient Shortest Path Algorithms (I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, R. F. Werneck) Journal of the ACM 63(5): 41:1–41:26, 2016.