Percolation of spatially constrained Erdős-Rényi networks with degree correlations

Motivated by experiments on activity in neuronal cultures [J. Soriano, M. Rodríguez Martínez, T. Tlusty, and E. Moses, Proc. Natl. Acad. Sci. 105, 13758 (2008)], we investigate the percolation transition and critical exponents of spatially embedded Erdős-Rényi networks with degree correlations. In our model networks, nodes are randomly distributed in a two-dimensional spatial domain, and the connection probability depends on Euclidian link length by a power law as well as on the degrees of linked nodes. Generally, spatial constraints lead to higher percolation thresholds in the sense that more links are needed to achieve global connectivity. However, degree correlations favor or do not favor percolation depending on the connectivity rules. We employ two construction methods to introduce degree correlations. In the first one, nodes stay homogeneously distributed and are connected via a distance- and degree-dependent probability. We observe that assortativity in the resulting network leads to a decrease of the percolation threshold. In the second construction methods, nodes are first spatially segregated depending on their degree and afterwards connected with a distance-dependent probability. In this segregated model, we find a threshold increase that accompanies the rising assortativity. Additionally, when the network is constructed in a disassortative way, we observe that this property has little effect on the percolation transition.

Figure 1

Illustrative network with 300 nodes and 600 links. (a) Random network without spatial dependence $\alpha =0$. (b) Spatially constrained network with $\alpha =-10$. Note that for $\alpha =-10$ connectivity is mostly local. Nodes are not shown for clarity.

Figure 2

Distribution of link lengths in spatial networks generated with different distance exponents $\alpha$. Gray (red) straight lines are fits of the form $P\left(l\right)\sim l^{\delta }$, with $\delta =1.0,0.0,-2.0,\text{and}-3.4$, from the largest to the smallest slope, respectively. Note that $\alpha$ is the target exponent of the network, while $\delta$ is the resulting exponent of the actual network. $\delta =\alpha +1$ for $\alpha >-4$, but for smaller values of $\alpha$ it holds that $\delta >\alpha +1$. In all cases the distributions are constructed with ${10}^5$ nodes and network connectivity $q=2$ and after averaging over 100 realizations.

Figure 3

Relation between the exponents of the preset link length distribution $P\left(l\right)\sim l^{\alpha +1}$ and the actual distribution $P\left(l\right)\sim l^{\delta }$ after network construction. The main plot shows that the relation $\delta =\alpha +1$ of Eq. (2) remains valid down to $\alpha \approx -4$. For values below $-4$, the exponent $\delta$ saturates to $\approx -3$. The inset shows the probability distribution of link lengths for $\alpha =-10$. Lines are a guide to the eye to show the scaling of the distribution at the limit of small and large $l$, see Eq. (10).

Figure 4

Pearson degree correlation coefficient $r$ for spatial networks with ${10}^5$ nodes and different exponents ($\alpha ,\rho$). ($◯$) Assortative network, ($\diamond$) uncorrelated network, ($\square$) disassortative network.

Figure 5

Schematic representation of the swapping procedure for two nodes $i$ and $j$. The large gray circle shows the swapping neighborhood range of radius $d$. Gray (red) dots depict nodes, with the size proportional to their target-degree. The positions of the nodes $i$ and $j$ (left) are swapped only if the swapping operation increases the difference between the mean target-degree of the two neighborhoods (right).

Figure 6

Comparison of the topological structure of models 1 and 2, for networks with $N={10}^3$ nodes (red spots) and $\alpha =-10$. Spot size is proportional to the degree of the node. Blue lines are representative links between nodes. (a) Construction using a homogeneous distribution with no swapping (model 1). (b) Segregated construction (model 2) after ${10}^6$ node swaps, illustrating the emergence of highly connected node assemblies.

Figure 7

Pearson degree correlation coefficient for networks of different size with $\alpha =-5$ after $S$ iterations of the swapping algorithm. About ${10}^{3}N$ iterations are needed for the Pearson coefficient to saturate.

Figure 8

Pearson degree correlation coefficient $r$ for model 2 networks with spatial segregation and $N={10}^5$, for different number of node-swaps $S$. Assortativity emerges for large negative distance exponents $\alpha$.

Figure 9

Finite-size scaling of mean cluster size of model 1 networks for different values of $\alpha$ and $\rho$. Data points collapse into a single curve. The set of percolation threshold and exponents $q_c$, $\frac{1}{\nu d}$, and $\frac{\gamma }{\nu d}$ were then obtained by the fitting procedure described in the main text. For each plot, their values are (a) $q_c=0.5$, $\frac{1}{\nu d}=0.33$, $\frac{\gamma }{\nu d}=0.33$; (b) $q_c=0.82$, $\frac{1}{\nu d}=0.35$, $\frac{\gamma }{\nu d}=0.87$; (c) $q_c=0.55$, $\frac{1}{\nu d}=0.33$, $\frac{\gamma }{\nu d}=0.33$; and (d) $q_c=0.96$, $\frac{1}{\nu d}=0.35$, $\frac{\gamma }{\nu d}=0.85$.

Figure 10

Scaling of giant component mass $NG$ at different $q$ for an assortative model 1 network with $\rho =-2$ for (a) $\alpha =0$ and (b) $\alpha =-3$. The gray (red) dashed lines are guides to the eye.

Figure 11

Percolation threshold for different values of $\alpha$ for uncorrelated networks ($•$, $\rho =0$), compared to correlated networks generated with model 1: assortative networks ($▵$, $\rho =-2$) and disassortative networks ($\square$, $\rho =2$). Uncorrelated and disassortative networks show a similar trend, while assortative networks display a significant decrease of the percolation threshold compared to the others.

Figure 12

Fractal dimension at criticality for different values of $\alpha$ for uncorrelated networks ($•$), compared to correlated networks generated with model 1: assortative networks ($▵$) and disassortative networks ($\square$). Only assortative networks show a significant decrease in the fractal dimension, which saturate for all network constructions at $\alpha \le -5$.

Figure 13

Influence of $\alpha$ in the percolation threshold and mean cluster size for model 1 networks with ${10}^5$ nodes. (a,b) Size of the giant component for two extreme values of $\alpha$, corresponding to nonspatial networks ($\alpha =0$) and spatial ones ($\alpha =-10$), respectively. Three network configurations are compared: uncorrelated ($\rho =0$), assortative ($\rho =-2$) and disassortative ($\rho =2$). Assortative networks always decrease the percolation threshold, i.e., less links are required to observe the emergence of a giant component. (c,d) Dependence of the mean cluster size on $\alpha$ for the same three networks.

Figure 14

Dependence of the percolation threshold $q_c$ for model 1 networks on the Pearson coefficient $r$ and the distance exponent $\alpha$. Open symbols show the actual data points for the construction of the plot.

Figure 15

Topological features of model 2 networks $(S={10}^8)$, characterized by a spatial segregation of node degrees. (a) Percolation threshold as function of the distance exponent $\alpha$. (b) Fractal dimension at criticality as a function of $\alpha$.

Figure 16

Dependence of the percolation threshold $q_c$ for model 2 networks on the Pearson coefficient $r$ and the distance exponent $\alpha$. Open symbols show the actual data points for the construction of the plot. Extrapolation to values that cannot be analyzed directly is omitted (gray area).