Spatial strength centrality and the effect of spatial embeddings on network architecture

For many networks, it is useful to think of their nodes as being embedded in a latent space, and such embeddings can affect the probabilities for nodes to be adjacent to each other. In this paper, we extend existing models of synthetic networks to spatial network models by first embedding nodes in Euclidean space and then modifying the models so that progressively longer edges occur with progressively smaller probabilities. We start by extending a geographical fitness model by employing Gaussian-distributed fitnesses, and we then develop spatial versions of preferential attachment and configuration models. We define a notion of “spatial strength centrality” to help characterize how strongly a spatial embedding affects network structure, and we examine spatial strength centrality on a variety of real and synthetic networks.

Figure 1

Example degree distributions of geographical fitness networks with Gaussian-distributed fitnesses and various values of the spatial decay parameter $\beta$. The values of $\beta$ in the plots are (a) 0, (b) 0.5, (c) 1, (d) 1.5, (e) 2, and (f) 2.5.

Figure 2

Characteristics of networks (with $n=500$ nodes) from a geographical fitness model with Gaussian-distributed fitness for different values of the spatial decay parameter $\beta$ and 30 instantiations of the model for each value of $\beta$. We show computations of (a) mean local clustering coefficient, (b) mean geodesic distance, (c) mean edge length, and (d) degree assortativity. In all cases, we first take means with respect to individual networks and then take means over the 30 instantiations. The error bars indicate 95% confidence intervals.

Figure 3

Scatter plot of closeness centralities for nodes in 4 instantiations of our GF model with decay parameter $\beta =0$. All instantiations for $\beta =0$ have similar scatter plots. The depicted instantiations illustrate common patterns. For each network, we highlight the node with the largest (in absolute value) fitness. In most scatter plots, we observe two large branches (on the left and right) and a small horizontal (or predominantly horizontal) curve between these two large branches. We refer to one branch as “lower” than the other if the lowest point of that branch is lower than the lowest point of the other branch. We observe that the left branch is lower when there is an “extremum” (i.e., a node with the largest absolute value) of closeness centrality on the left [see panels (a)–(b)] and that the right branch is lower when there is an extremum of closeness centrality on the right [see panel (c)].

Figure 4

Scatter plot of closeness centralities for nodes in 4 instantiations of our GF model with decay parameter $\beta =0.5$. The depicted instantiations illustrate common patterns. For each network, we highlight the node with the largest (in absolute value) fitness. For this value of $\beta$, we do not always observe noticeable branches [see panels (b)–(d)]. When there are noticeable branches in a scatter plot, they are usually accompanied by a node whose fitness has a large absolute value [see panel (a)].

Figure 5

Scatter plot of closeness centralities for nodes in 2 instantiations of our GF model with decay parameter $\beta =1$. The depicted instantiations illustrate common patterns. For each network, we highlight the node with the largest (in absolute value) fitness. For this value of $\beta$, branches are almost never apparent in the scatter plots [see panel (a)], even when there are nodes with extreme fitness values [see panel (b)], and the node with the most extreme fitness value is not necessarily the one with the largest value of closeness centrality.

Figure 6

Degree distributions for networks that we construct from our spatial preferential-attachment model with $T=10000$ time steps. The values of the spatial decay parameter $\beta$ in the plots are (a) 0, (b) 2, and (c) 4.

Figure 7

Some characteristics of the networks from our SPA model for different values of the spatial decay parameter $\beta$ for networks with $n=10010$ nodes, $m=5$ edges for each new node that we add to a network, and 10 instantiations of our model. We show computations of (a) mean local clustering coefficient, (b) mean geodesic distance, (c) mean edge length, and (d) degree assortativity.

Figure 8

Mean geodesic distances of our SPA networks as a function of the number $n$ of nodes in a network for several values of the spatial decay parameter $\beta$. We show the number of nodes on a logarithmic scale. Each point in the plot represents a mean of the mean geodesic distances over 10 instantiations of our SPA model.

Figure 9

Mean local clustering coefficients of our SPA networks as a function of the number $n$ of nodes in a network for several values of the spatial decay parameter $\beta$. We show the number of nodes on a logarithmic scale. Each point in the plot represents a mean of the mean local clustering coefficients over 10 instantiations of our SPA model.

Figure 10

Degree distributions for networks that we construct from our spatial configuration model with a degree sequence given by a BA network with $n=1010$ nodes and $m=5$ new edges for each node that we add after the seed. The values of the spatial decay parameter $\beta$ in the plots are (a) 0, (b) 2, and (c) 4.

Figure 11

Some characteristics of the networks from our spatial configuration-model networks for various values of the spatial decay parameter $\beta$. For each configuration-model network, we use a degree sequence given by a BA model with $n=1010$ nodes and $m=5$ new edges for each node that we add after the seed. In our computations, we take means over 30 instantiations (for which we have 30 different networks) of our spatial configuration model. We show computations of (a) mean local clustering coefficient, (b) mean geodesic distance, (c) mean edge length, and (d) degree assortativity. The error bars indicate 95% confidence intervals.

Figure 12

Comparison of the characteristics of our spatial configuration-model networks (blue disks) with characteristics of SPA networks (orange crosses) with $n=1010$ nodes and $m=5$ new edges for each node that we add. The spatial configuration-model networks are the same networks (each with a degree sequence from a BA network) from Fig. 11. We take all data points as means over 30 instantiations, and error bars indicate $95\%$ confidence intervals.

Figure 13

Mean spatial strength centralities $\langle S\rangle$ in our GF model, our SPA model, and our spatial configuration model for various values of the spatial decay parameter $\beta$. For a given value of $\beta$, each point represents a mean over 20 instantiations of a model. Our GF-model networks have $n=500$ nodes, and our SPA and spatial configuration-model networks have $n=1010$ nodes.

Figure 14

Mean spatial strength centralities of example networks from individual instantiations of our GF model with $n=150$ nodes, which we place in $[0,1]\times [0,1]$ (with periodic boundary conditions) according to their assigned coordinates. We show examples with (a) $\beta =0.5$ and $\langle S\rangle \approx 0.786$ and (b) $\beta =3$ and $\langle S\rangle \approx 1.007$.

Figure 15

Example networks with the indicated values of mean spatial strength centrality. The depicted networks are (a) a lattice network, with $\langle S\rangle \approx 0.999$; (b) a spatially-embedded Cayley tree, with $\langle S\rangle \approx 0.687$; and (c) a hub-and-spoke example, with $\langle S\rangle \approx 0.300$.

Figure 16

These small hub-and-spoke networks give a toy example that illustrates an idea of potential relevance to a network of flights between airports. For each network, we give the spatial strength centralities of each hub and each spoke. In each of the two examples, all spoke nodes have the same spatial strength centrality. Panel (a) has $\langle S\rangle \approx 0.300$, and panel (b) has $\langle S\rangle \approx 0.430$. In panel (b), the hub–spoke edges are half the length of such edges in panel (a). Notably, the values of $S_{\text{hub}}$ in panel (b) are smaller than they are for corresponding nodes in panel (a).

Figure 17

This example of a two-scale network with two pairs of nodes has a mean spatial strength centrality of $\langle S\rangle \approx 8.009$. By increasing the length of the long edge, one can make $\langle S\rangle$ arbitrarily large.

Figure 18

Example networks and mean spatial strength centralities of empirical networks and an RGG. We show (a) a street network from Tunis, Africa with 1731 nodes and $\langle S\rangle \approx 2.339$; (b) a fungal network of type “Pv_M_I+4R_U_N_21d_4” (see Ref. [15]) with 641 nodes and $\langle S\rangle \approx 2.279$; and (c) an RGG with $n=500$ nodes, a connection radius of $r_c=0.07$, and $\langle S\rangle \approx 1.228$.

Figure 19

Scatter plot of mean spatial strength centrality versus the number of nodes in several synthetic and empirical networks. We use fungal networks from Ref. [15], city street networks from Ref. [16], and RGGs with a connection radius of $r_c=0.07$. The spatial Cayley trees in this plot have between 1 and 6 branches, and their depths range from 1 to 4. The lattice networks have 5, 10, 15, 20, 25, or 30 rows and columns (and any combination of rows and columns of those sizes); in the plot, these networks yield an almost horizontal line at a mean spatial strength centrality of about 1. The city in the top-right corner of the plot is Paris.