Comparing spatial networks: A one-size-fits-all efficiency-driven approach

Spatial networks are a powerful framework for studying a large variety of systems belonging to a broad diversity of contexts: from transportation to biology, from epidemiology to communications, and migrations, to cite a few. Spatial networks can be described in terms of their total cost (i.e., the total amount of resources needed for building or traveling their connections). Here, we address the issue of how to gauge and compare the quality of spatial network designs (i.e., efficiency vs. total cost) by proposing a two-step methodology. First, we assess the network's design by introducing a quality function based on the concept of network's efficiency. Second, we propose an algorithm to estimate computationally the upper bound of our quality function for a given network. Complementarily, we provide a universal expression to obtain an approximated upper bound to any spatial network, regardless of its size. Smaller differences between the upper bound and the empirical value correspond to better designs. Finally, we test the applicability of this analytic tool set on spatial network data-sets of different nature.

Figure 1

(a) Average global efficiency, $\langle E_{\text{glob}}\rangle$ and (b) average local efficiency, $\langle E_{\text{loc}}\rangle$, as a function of the total length of the system, $L_{\text{tot}}$, for different models: greedy triangulation (GT), minimum spanning tree (MST), equitable efficiency model (EEM), and Gastner-Newman (GN) with $\lambda =0.85$ and $\gamma =0.06$. Dots refer to the properties of the final networks, while the solid lines account for the evolution, whenever available,of those properties throughout the growth process. The graphs have been built by averaging uniform random distributions of $N=100$ points considering $N_{\mathrm{real}}=50$ different realizations.

Figure 2

(a) Comparison between the averages local, $\langle E_{\text{loc}}\rangle$, and global, $\langle E_{\text{glob}}\rangle$, efficiencies for the GT, MST, EEM, and GN topologies. The values of the other parameters are the same of those used in Fig. 1. Continuous black lines stand for $E_{\text{int}}$ equilines. (b) Average integrated efficiency, $\langle E_{\text{int}}\rangle$, as a function of the total length of the system, $L_{\text{tot}}$.

Figure 3

(a) Evolution of the local ($E_{\text{loc}}^{\text{opt}}$), global ($E_{\text{glob}}^{\text{opt}}$), and integrated ($E_{\text{int}}^{\text{opt}}$) efficiencies with respect to the total length of the system, $L_{\text{tot}}$, for the networks generated using our optimal model. (b) Evolution of the average local ($\langle E_{\text{loc}}\rangle$), and global ($\langle E_{\text{glob}}\rangle$) efficiencies for the same networks. The green star denotes the values at which 90% of the nodes belong to the giant component. Results are averages over $N_{\mathrm{real}}=100$ different layouts of $N=100$ nodes uniformly distributed on the unit square. Continuous black lines stand for $E_{\text{int}}$ equilines.

Figure 4

(a) Evolution of the average integrated efficiency, $\langle E_{\text{int}}^{\text{opt}}\rangle$, with respect to the total length $L_{\text{tot}}$ for systems with different number of nodes $N$. Solid lines account for the evolving systems, while symbols denote the final networks. (b) Same quantity of (a), but displayed as a function of the rescaled length $L^{\prime }$. The curves corresponding to different network sizes overlap perfectly.

Figure 5

(a) Global efficiency difference, $\mathrm{\Delta }{E}_{\text{glob}}=E_{\text{glob}}^{\text{opt}}-E_{\text{glob}}$, with respect to the same quantity calculated for the local efficiency, $\mathrm{\Delta }{E}_{\text{loc}}$ for all the data set reported in Table 1. The hue of the color is used to order the dataset in a chronological way. (b) Ranking of the empirical systems according to the integrated efficiency difference $\mathrm{\Delta }{E}_{\text{int}}=E_{\text{int}}^{\text{opt}}-E_{\text{int}}$. Points for data SE4 and SE5 are not shown since, as mentioned in Sec. 3b, we were unable to generate the optimal counterparts.

Figure 6

Integrated efficiency, $E_{\text{int}}$ as a function of the rescaled length $L^{\prime }$ for the same data sets. The filled area for $L^{\prime }\le 0.91$ denotes the region for which the system has not fully percolated yet. The hue of the color is used to order the data set in a chronological way. The continuous black line stand for the optimal curve $E_{\text{int}}^{\text{opt}}\left(L^{\prime }\right)$.

Figure 7

Schematic representation of a segment $\overline{AB}$.