Balancing building and maintenance costs in growing transport networks

Arianna Bottinelli, Rémi Louf, and Marco Gherardi

Phys. Rev. E 96, 032316 – Published 27 September 2017

Abstract

The costs associated to the length of links impose unavoidable constraints to the growth of natural and artificial transport networks. When future network developments cannot be predicted, the costs of building and maintaining connections cannot be minimized simultaneously, requiring competing optimization mechanisms. Here, we study a one-parameter nonequilibrium model driven by an optimization functional, defined as the convex combination of building cost and maintenance cost. By varying the coefficient of the combination, the model interpolates between global and local length minimization, i.e., between minimum spanning trees and a local version known as dynamical minimum spanning trees. We show that cost balance within this ensemble of dynamical networks is a sufficient ingredient for the emergence of tradeoffs between the network's total length and transport efficiency, and of optimal strategies of construction. At the transition between two qualitatively different regimes, the dynamics builds up power-law distributed waiting times between global rearrangements, indicating a point of nonoptimality. Finally, we use our model as a framework to analyze empirical ant trail networks, showing its relevance as a null model for cost-constrained network formation.

Received 30 September 2016
Revised 14 September 2017

DOI:https://doi.org/10.1103/PhysRevE.96.032316

Physics Subject Headings (PhySH)

Evolving networks Network formation & growth Network optimization Network phase transitions

Real world networks Transportation networks

Data analysis Evolving network models

Statistical Physics & ThermodynamicsNetworks

Authors & Affiliations

Arianna Bottinelli¹, Rémi Louf², and Marco Gherardi^3,4

¹Mathematics Department, Uppsala University, Lägerhyddsvägen 1, Uppsala 75106, Sweden
²Centre for Advanced Spatial Analysis, University College London, 90 Tottenham Court Road W1T4TJ London, United Kingdom
³Sorbonne Universités, UPMC Univ Paris 06, UMR 7238, Computational and Quantitative Biology, 15 rue de l'École de Médecine Paris, France
⁴Dipartimento di Fisica, Università degli Studi di Milano, via Celoria 16, 20133 Milano, Italy

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 96, Iss. 3 — September 2017

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
At each time step, the model grows a network by adding a new node (NN) at a random position. Depending on what move minimizes the convex combination of total built length $L_{B}$ and total length variation $Δ L$ , NN is either connected to the closest node in the network (dMST move) or the network is rewired to minimize the total length (MST move). In both cases only one link is added.
Reuse & Permissions
Figure 2
Structural properties and evolution of networks grown with different strategies $β$ . The normalized (a) Hamming distance, (b) total length, and (c) efficiency reveal three classes of strategies: MST-like, crossover, and dMST-like, separated by two transition points $β_{1}$ and $β_{2}$ . (d) Probability distribution of the waiting time to the first MST move and between two consecutive MST moves $P (τ)$ for different windows of network size. In $β_{2}, P (τ)$ is a power law of exponent $\approx - 1.5$ (highlighted box). (e) Realizations of the model (black thin line) for values of $β$ in the three classes of strategies and for $β = β_{2}$ on the same 50-nodes sequence (black dots), superposed to the corresponding MST (light bold line).
Reuse & Permissions
Figure 3
The integrated (up to $N_{f} = 1000$ ) total cost landscapes (solid lines) for (a) building ( $L_{B}$ ) and maintaining ( $L_{M}$ ), at different values of the ratio $h$ between their unit costs, (b) the same quantity with selected landscapes are plotted on same-scale axes to show the robustness of optimal strategies in the crossover regime; (c) building, maintaining, and destroying ( $L_{D}$ ) for $h = 1$ . $k \in [- 1, 1]$ is the unit cost of destroying material (if $k < 0$ ) or the advantage of recycling (if $k > 0$ ). The minimum of each cost landscape (dots) is the optimal strategy $β_{opt}$ for the given value of $h$ and $k$ , often belonging to the crossover regime. (d) The total number of links that are destroyed and rebuilt ( $N_{D}$ ) during the growth of the network is maximum in $β_{2}$ , revealing high nonextensive costs. Strategies above the horizontal dashed line destroy more links than the pure strategy $β = 1$ .
Reuse & Permissions
Figure 4
(a) Examples of ant networks: (i), (ii) Argentine ants in laboratory conditions connect their nests through the shortest path. Courtesy of Tanya Latty. (iii) A Meat ant's nest with departing trails. Courtesy of Nathan Brown. (iv) Part of a meat ant's trail network from Google Earth. (b, c, d) Analysis of empirical networks through comparison with our model. Meat ants [39] are squares, other species [37, 40, 41, 42, 43, 44, 45] are diamonds, circles represent the model. (b) A value of $β$ is assigned to each ant network by comparing its rescaled Hamming distance with the prediction of our model. See Tables 1 and 2. (c, d) For each ant network, the empirical values of the normalized efficiency (c) and normalized total length (d) are matched with the value of $β$ assigned as in panel (b), and plotted above the trend predicted by our model for $N = 30$ . Notice that networks with the same rescaled Hamming distance (and thus $β$ ) in (b) may have different values of efficiency and total length and thus correspond to distinct shapes in (c) and (d).
Reuse & Permissions
Figure 5
Randomized network analysis. (a) The Hamming distance of randomized networks from the corresponding MST is larger than 0.5 with large probability, thus it is not possible to assign them a value of $β$ . In this plot and the following ones they are plotted at arbitrary values (full shapes) and together with original ant data (empty shapes) and our model (circles) for comparison. Also, (b) efficiency and (c) total length of randomized networks assume values not compatible with ant data and with the model's predictions.
Reuse & Permissions
Figure 6
Structural properties of the transport networks built by our model as a function of network size $N$ and of the strategy $β$ (colors online). Full lines represent our model at different values of $β$ . Arrows indicate increasing values of $β$ . Dashed lines corresponds to the MST built on the same set of nodes. (a) Top: The Hamming distance as a function of $N$ at different values of $β \in [0, 1]$ . Bottom: the rescaled Hamming distance as a function of N (left) and $β$ (right) for $N = 1000$ . (b) Top: total network length as a function of $N$ for different values of $β$ , and rescaled by the length of the MST built on the same set of nodes (inset). Bottom: The rescaled total length as a function of $β$ at $N = 1000$ . (c) Top: Efficiency as a function of $N$ at different values of $β$ . Smaller plots: Efficiency normalized by the corresponding MST value during three growth stages of the network at $N = 200, N = 350$ , and $N = 1000$ (counterclockwise).
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics