We study a spatial network model with exponentially distributed link lengths on an underlying grid of points, undergoing a structural crossover from a random, Erdős-Rényi graph, to a d-dimensional lattice at the characteristic interaction range ζ. We find that, whilst far from the percolation threshold the random part of the giant component scales linearly with ζ, close to criticality it extends in space until the universal length scale ζ6/(6-d), for d<6, before crossing over to the spatial one. We demonstrate the universal behavior of the spatiotemporal scales characterizing this critical stretching phenomenon of mean-field regimes in percolation and in dynamical processes on d=2 networks, and we discuss its general implications to real-world phenomena, such as neural activation, traffic flows or epidemic spreading.
Two decades after its inception, network theory has grown to become an exhaustive framework for taming the complexity of a multitude of systems at different scales [1–3]. Despite the many advances made in the study of critical phenomena  on random networks, their analysis in the presence of a geometric embedding has remained an important theoretical challenge, so far grounded on very little analytical results [5–9]. This represents today a fundamental barrier in the understanding of complex systems of great interest, like networks of neurons [10,11], communication  and transportation systems , or power-grids , whose functioning strongly intertwines their spatial constraints.
This Letter aims to explore the effects that a tunable characteristic link length has on the universality of critical phenomena in a realistic model of a spatial network. We consider a variant on a lattice of the so-called Waxman model , where nodes are distributed on an hypercube of linear size with spacing , and edges are drawn with probabilities , for every pair of nodes , placed at the Euclidean distance . Like in Erdős-Rényi (ER) networks, the parameter controls the density of links, with the average connectivity, while is a characteristic link length. Although simplistic, the exponential wiring cost function of this model correctly fits the spatial distribution of link lengths observed in communication systems , like the Internet [17,18] or transport networks [19,20], interactions based on similarity in social networks , and recent experimental results [22–26] support the existence of scale-invariant organizational principles in the connectome of mammals based on it.
This disordered lattice is a natural benchmark for investigating crossover phenomena [27,28] in spatial networks. Depending on the values of , in fact, our model crosses over between two limiting regimes: for , all link lengths are equally probable (i.e., ) and we recover a random, ER-like structure, whilst for (where is the average density of nodes), long links are prohibited, leading instead to a latticelike topology. By performing site percolation [29–31], we disclose an intriguing scenario: while far from criticality the random part of the giant component crosses over to a spatial regime at the characteristic scale , close to the percolation threshold it surprisingly extends in space until the intrinsic scale , for . We call this structural expansion of mean-field regimes the critical stretching, and we explore its universal features by means of scaling arguments, and simulations in . In particular, because the structure affects the collective phenomena occurring on it, the critical stretching should be reflected in processes evolving on this spatial network. We verify this claim on an SIR (susceptible-infective-removed) process , where the mean-field (diffusive) regime of the outbreak front’s velocity undergoes a temporal critical stretching, making the epidemic invade the system at “slow” rates for significantly longer times.
Crossover and critical stretching.—To investigate the structural crossover, we perform site percolation by randomly removing a fraction of the network’s nodes, for given average degree and varying  characteristic link-lengths. For increasing , a rapid monotonic decrease of the percolation threshold from the lattice value to the ER one is observed [Fig. 1(b), and Ref.  ]. To analyze the response the scaling of percolation observables have to this variation, we consider the correlation length , where is the pair connectivity function for a given occupation probability . By definition, measures the mean distance between sites belonging to the same cluster, and it diverges as approaches like . Numerical results [Fig. 1(a)] for networks in , display excellent agreement with the critical exponents expected in the two limiting cases, i.e., for and for , further showing that a crossover from the former to the latter regime occurs closer and closer to for increasing .
This critical crossover can be understood by invoking the Levanyuk-Ginzburg (LG) criterion . Since the spectrum of our spatial network satisfies the classical LG assumptions , we expect fluctuations to be negligible as long as for , where is the displacement of from its critical value. To obtain this condition, we noticed that the scale up to which the mean-field regime extends in the giant cluster is , where is the (dimensionless) correlation length in chemical space, and the factor takes into account the characteristic length of links . The critical crossover should then take place at and, in light of the above, at the intrinsic scale . For such variation to occur, the amplitude modulating the scaling of with must itself become anomalous in as soon as fluctuations set in, so that . The exponent can be found by invoking a smooth variation at , i.e., , yielding . Factoring out , as well as , we obtain the generalized scaling
Geometric stretching at criticality. —From a geometric standpoint, the crossover scaling in Eq. (1) implies a nontrivial structural variation of the large-scale organization of the network close to its percolation threshold. To put this on firmer bases, consider the scaling of the pair connectivity function , where is the anomalous dimension. The correlation length is itself the representative of a crossover in the giant component, separating a self-similar organization where , from a “noncritical” one marked instead by a decreasing exponential . Then again, we know from Eq. (1) that crosses over between the mean-field and the lattice singular behaviors, depending on how close the network is to . Let us then fix the occupation probability to a value , so that geometric fluctuations are free to set in above . In turn, this means that and so the cutoff becomes significant only if . Therefore, reading as a function of for fixed and variable values of , we advance the crossover relation
Equation (2) provides a geometric formulation of the LG criterion at criticality, upon which density fluctuations of the spanning cluster are negligible as far as . This result enables testing the critical stretching of the high-dimensional (mean-field) regime of the networks’ structure by comparing its geometric features at and away from criticality. With this aim, we focus on two exponents: (i) the shortest-path fractal dimension , and (ii) the mass fractal dimension of the incipient cluster . Although the analysis could be carried out in any dimension , we restrict here to the case for simplicity of computation. Let us start from the behavior at . (i) By definition, regulates the scaling of the mean Euclidean distance between sites in the giant cluster separated by the chemical distance , so that for large enough. For future reference, we consider the reciprocal scaling , for large enough. In chemical space, translates  into the quantity (where the brackets denote the floor function) which, consistently with the scaling ansatz in Eq. (2), identifies the intrinsic chemical length at which the geometric crossover occurs. In defining , we must thus consider two regimes: where (i.e., random walk), and where instead . Merging the two behaviors into a single equation, we propose the scaling
To complete the picture, we must verify that far from the percolation threshold, is indeed the characteristic length at which the geometric crossover occurs. Let us start from the mass scaling (ii) at . In this case, the Euclidean dimension is expected to regulate the scaling of for distances , while an infinite-dimensional (small-world) behavior should be observed for . The numerical results in Fig. 2(c) corroborate this intuition, further showing [Fig. 2(c), inset] that below the random structure embeds onto an Euclidean space whose dimension grows unbounded with . (i) The shortest-path’s scaling at supports this large-to small-world crossover: while for any path shall behave like a random walk , i.e., , for (lattice regime) the lengths and must share the same metric, i.e., . We can then advance the scaling where for and constant otherwise. The quantity can be regarded as the chemical length up to which the small-world extends, so since . The data collapse in Fig. 2(d) is consistent with our scaling, and further supports [Fig. 2(d), inset] the approximation . Altogether, these results confirm the prediction that far from criticality the network’s geometry is governed by the characteristic scale , corroborating the surprising effect of the critical stretching.
Stretching effects in spreading dynamics.—Since collective phenomena are strongly affected by the geometry of the underlying interaction structure, the critical stretching will accordingly influence the dynamics of processes acting on the network. As an illustrative example, let us consider an SIR process with infection rate and recovery time , spreading on our network model in . In light of the mapping to percolation , the clusters of nodes removed by the outbreak are geometrically equivalent to those originated from a static deletion, whereas the shortest-path identifies now the number of time steps separating infected nodes in the th shell from an initial spreader. Setting the relative rate to a value , we thus expect the spreading of the disease to undergo a temporal crossover at the intrinsic time scale from a mean-field behavior to a spatial one. In particular, interpreting as the average distance of the infective nodes from an initial spreader, we can deduce from Eq. (3) that the spreading velocity of the outbreak front will accordingly satisfy the temporal scaling
Discussion.—In this Letter, we have investigated the effects that a tunable characteristic link length has on the critical phenomena in spatial networks. We studied the spatiotemporal location where a crossover from random (mean-field) to spatial regimes takes place when considering the network away from () or close to () its percolation threshold. We found that while this crossover occurs at when , it surprisingly extends until close to , signaling that the mean-field (ER) structure expands beyond the input characteristic link length near criticality. We named this phenomenon critical stretching, and we demonstrated its geometric and dynamic features by analyzing the Euclidean correlation length and its chemical counterpart , whose crossover scales are summarized in Table I.
Some relevant comments are in order. (i) The critical stretching length scales and are univocally defined by the critical exponents of percolation and the dimension of the embedding space. As such, they are not influenced by the system’s finite size  and can be regarded as a set of universal spatiotemporal scales for any spatial network featuring a characteristic scale of link lengths and a homogeneous degree distribution. (ii) In light of the expressions in Table I, the stretching effects become stronger at higher embedding dimensions. In networks, e.g., the intrinsic scales at are significantly larger if compared to the crossover scales and away from criticality. This supports the possibility that the stretching effects we found can be experimentally observed in real-world systems. In fact, besides accurately modeling communication [16–18,21] and transport networks [19,20], recent evidences [23–26] support the existence of scale-invariant organization principles in mammal brains based on the exponential wiring cost function examined here. Our results offer then a fundamental keystone for understanding, e.g., the traffic flow  or the neural functioning—e.g., in reference to the observed activity before epileptic seizures —and they raise the perspective of developing criteria (say, measuring the amount of stretching in the propagation of the action potentials for neural networks) for testing how close these systems are to their tipping points.
I. B. and B. G. contributed equally to this work. S. H. acknowledges financial support from the ISF, ONR, DTRA: HDTRA-1-10-1-0014, BSF-NSF: 2015781, ARO, the Israeli Ministry of Science, Technology and Space (MOST) in joint collaboration with the Japan Science Foundation (JSF), and the Italian Ministry of Foreign Affairs and International Cooperation (MAECI), and the Bar-Ilan University Center for Research in Applied Cryptography and Cyber Security. I. B. thanks S. V. Buldyrev, G. Sicuro, and M. C. Strinati for valuable discussions.