Pareto Optimality in Multilayer Network Growth

We model the formation of multilayer transportation networks as a multiobjective optimization process, where service providers compete for passengers, and the creation of routes is determined by a multiobjective cost function encoding a trade-off between efficiency and competition. The resulting model reproduces well real-world systems as diverse as airplane, train, and bus networks, thus suggesting that such systems are indeed compatible with the proposed local optimization mechanisms. In the specific case of airline transportation systems, we show that the networks of routes operated by each company are placed very close to the theoretical Pareto front in the efficiency-competition plane, and that most of the largest carriers of a continent belong to the corresponding Pareto front. Our results shed light on the fundamental role played by multiobjective optimization principles in shaping the structure of large-scale multilayer transportation systems, and provide novel insights to service providers on the strategies for the smart selection of novel routes.

Figure 1

Illustration of the airline growth model. (a) At time $\tau =2$ a new layer arrives with $K^{[2]}$ links to be placed, and the first edge is placed uniformly at random among all possible pairs of nodes. (b) The remaining $K^{[2]}-1$ links are placed according to the probability $p_{ij}^{[2]}$ in Eq. (1). (c) The same procedure is repeated for each layer $\tau$ until a multiplex with $M$ layers is obtained.

Figure 2

Distributions of layer activity $N^{[\alpha ]}$ (left column), node total degree $o_i$ (middle column), and edge overlap $o_{ij}$ (right column). The multiplex networks (red diamonds) of North America airlines (top row), UK train services (middle row), and UK coach services are compared to the corresponding multiplex networks generated by the MMOO model (solid blue lines) and to multiplex networks whose layers are Erdös-Rényi graphs [67] (dashed lines). The results shown are averaged over $10^3$ realizations (standard deviations are indistinguishable from the symbols).

Figure 3

Observed (solid green line) and theoretical (dashed blue line) Pareto fronts for the continental airline networks of (a) North America and (b) Africa. The top ten airlines by number of passengers in 2013 are highlighted. For each system, the theoretical Pareto front was obtained as the nondominated points of $10^5$ realizations of the MMOO model (the range of variability of the simulations is indicated by the shaded grey region).

Figure 4

Reshaping the routes of two North American airlines in the $F\text{−}G$ plane. United Airlines, a Pareto-optimal company (blue diamonds), cannot be improved any further by our model, while Great Lakes Airlines (brown squares) can potentially get much closer to the Pareto front.