*Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke and Max Klimm*

The growth of infrastructure networks is driven and constrained by economic, political, and social phenomena whose impact can be studied through mathematical models. An aspect rarely modeled is how a network is shaped by the historical path of its gradual formation, as early links may form a backbone that affects the course of subsequent connections. We study here a model that considers such path dependence in concert with economic considerations to explain the formation of ancient road networks, and we develop algorithmic tools to allow for historical paths to be estimated. When a possible construction history is inferred from sparse archaeological evidence, the model can make reasonable predictions about links not yet discovered.

**As a start, what is your academic background, and how did you come to this project
**

*I studied computer science at TU Berlin but did my master’s thesis **at the math department where I was supervised by one of the project heads, Guillaume Sagnol. The project was attractive as it combined programming tasks that I already felt comfortable with with theoretical fields I wanted to learn more about: network science and its abstract cousin, graph theory.*

**Can you describe in a few sentences – for non-mathematicians – what the article is about?**

*Archaeologists are interested in models and methods that make reasonable predictions about the unknown. Existing models of network formation typically assume that the final network structure is either very regular, say every settlement is connected to its three closest neighbors, or optimizes some measure of efficiency such as construction costs. We confront this with a network growth process where early and possibly short-sighted decisions can shape the network for generations to come. This model considers all possible histories and requires difficult computations to be used. We also evaluate the model on the Roman road network of Sardinia, with promising results.*

**Besides mathematics, what other disciplines participated in the project?**

*The project is joint work with Benjamin Ducke from the German Archaeological Institute, who also has a background in computer science and has worked at the interface between archaeology and mathematical modeling before.*

**What could be (is) the applied aspect of the project? **

*While we were looking for a model that was simple enough to be amenable to a rigorous analyis, good performance on real-world data was a central goal. We also provide open source software to help the model find its way into practice.*

**What was the most fun in your research?**

*It was great to see results improve as we refined our optimization method! I also enjoyed working on the computational hardness results, although they ended up less visible in the article’s supplementary material.*

**Last but not least, what are the next steps concerning your research?**

*I want to further explore how social choice shapes networks! After submission I made an excursion to study a game-theoretic model for the provision of public goods over a network. I might take this economic lense back to the ancient road by studying network formation games.*

**Thank you for your time!**

this paper was written within a MATH+ project EF5-6 that is part of the Emergent Field EF45