Physical Review Letters

American Physical Society

Critical Stretching of Mean-Field Regimes in Spatial Networks

Volume:
123,
Issue: 8

DOI 10.1103/PhysRevLett.123.088301

Abstract

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 [4] 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 [12] and transportation systems [13], or power-grids [14], whose functioning strongly intertwines their spatial constraints.

This Letter aims to explore the effects that a tunable characteristic link length $\zeta $ 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 [15], where $N={L}^{d}$ nodes are distributed on an hypercube of linear size $L$ with spacing $a\equiv 1$, and edges are drawn with probabilities ${\mathcal{P}}_{ij}\propto \kappa {e}^{-{d}_{ij}/\zeta}$, for every pair of nodes $i$, $j$ placed at the Euclidean distance ${d}_{ij}$. Like in Erdős-Rényi (ER) networks, the parameter $\kappa \equiv \u27e8k\u27e9/(N-1)$ controls the density of links, with $\u27e8k\u27e9$ the average connectivity, while $\zeta \in (0,L]$ 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 [16], like the Internet [17,18] or transport networks [19,20], interactions based on similarity in social networks [21], 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 $\zeta $, in fact, our model crosses over between two limiting regimes: for $\zeta \sim \mathcal{O}(L)$, all link lengths are equally probable (i.e., ${\mathcal{P}}_{ij}\sim \kappa $) and we recover a random, ER-like structure, whilst for $\zeta \sim \mathcal{O}(1/\sqrt{\rho})$ (where $\rho $ 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 $\zeta $, close to the percolation threshold it surprisingly extends in space until the intrinsic scale ${\xi}_{*}(\zeta )={\zeta}^{6/(6-d)}$, for $d<6$. 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 $d=2$. 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 [32], 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 $1-p$ of the network’s nodes, for given average degree $\u27e8k\u27e9=4$ and varying [33] characteristic link-lengths. For increasing $\zeta $, a rapid monotonic decrease of the percolation threshold ${p}_{c}$ from the lattice value to the ER one ${p}_{c}^{\mathrm{MF}}=1/\u27e8k\u27e9$ is observed [Fig. 1(b), and Ref. [20] ]. To analyze the response the scaling of percolation observables have to this variation, we consider the correlation length ${\xi}^{2}(p)\u2254\int {r}^{2}g(r,p)dr/\int g(r,p)dr$, where $g(r,p)$ is the pair connectivity function for a given occupation probability $p$. By definition, $\xi $ measures the mean distance between sites belonging to the same cluster, and it diverges as $p$ approaches ${p}_{c}$ like $\xi \sim |p-{p}_{c}{|}^{-{\nu}_{d}}$. Numerical results [Fig. 1(a)] for networks in $d=2$, display excellent agreement with the critical exponents expected in the two limiting cases, i.e., ${\nu}_{2D}=4/3$ for $\zeta \sim \mathcal{O}(1)$ and ${\nu}_{\mathrm{MF}}=1/2$ for $\zeta \sim \mathcal{O}(L)$, further showing that a crossover from the former to the latter regime occurs closer and closer to ${p}_{c}$ for increasing $\zeta $.

This critical crossover can be understood by invoking the Levanyuk-Ginzburg (LG) criterion [34]. Since the spectrum of our spatial network satisfies the classical LG assumptions [6], we expect fluctuations to be negligible as long as ${u}^{3-d/2}{\zeta}^{d}\gg 1$ for $d<6$, where $u\equiv |p/{p}_{c}-1|$ is the displacement of $p$ 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 ${\xi}_{\mathrm{MF}}\propto \zeta {{\xi}_{\ell}}^{1/2}$, where ${\xi}_{\ell}(u)\sim {u}^{-1}$ is the (dimensionless) correlation length in chemical space, and the factor $\zeta $ takes into account the characteristic length of links [35]. The critical crossover should then take place at ${u}_{*}(\zeta )\equiv {\zeta}^{-2d/(6-d)}$ and, in light of the above, at the intrinsic scale ${\xi}_{*}(\zeta )\equiv {\zeta}^{6/(6-d)}$. For such variation to occur, the amplitude modulating the scaling of $\xi $ with $u$ must itself become anomalous in $\zeta $ as soon as fluctuations set in, so that ${\xi}_{d}\propto {\zeta}^{\mathrm{\Psi}(d)}{u}^{-{\nu}_{d}}$. The exponent $\mathrm{\Psi}(d)$ can be found by invoking a smooth variation at ${u}_{*}$, i.e., ${\xi}_{\mathrm{MF}}{|}_{{u}_{*}}={\xi}_{d}{|}_{{u}_{*}}$, yielding $\mathrm{\Psi}(d)=[(6-2d{\nu}_{d})/(6-d)]$. Factoring out ${\xi}_{*}$, as well as $u/{u}_{*}$, we obtain the generalized scaling

$\frac{\xi (u,\zeta )}{{\xi}_{*}(\zeta )}={\left(\frac{u}{{u}_{*}(\zeta )}\right)}^{-\xbd}\mathcal{F}\left(\frac{u}{{u}_{*}(\zeta )}\right),$

where $\mathcal{F}(\mathcal{x})\propto {\mathcal{x}}^{-{\nu}_{d}+1/2}$ for $\mathcal{x}\ll 1$, and constant otherwise. After specializing these results to the case $d=2$, the data presented in Fig. 1(a) have been accordingly rescaled. The data collapse depicted in Figs. 1(c) and 1(d) supports our scaling arguments, and further highlights an interesting prediction of the LG criterion. Although one would have expected the random-to-spatial crossover to occur at the input characteristic scale $\zeta $—as it does far from criticality—here it stretches until ${\zeta}^{6/(6-d)}$. This scale can be regarded as the network analogue at the crossover of what Binder calls “thermodynamic length” in spin systems [27]. However, in contrast to thermal phase transitions, ${\xi}_{*}$ identifies here a “structural length” at which geometric fluctuations set in. This means that ${\xi}_{*}$ does not only rule the critical scaling of the percolation observables, but also the network’s geometry at the onset of the giant component, stretching nonlinearly with $\zeta $ its mean-field regimes. For this reason, we call this phenomenon *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 $g(r,u,\zeta )\propto {r}^{-d+2-\eta}{e}^{-r/\xi (u,\zeta )}$, where $\eta $ is the anomalous dimension. The correlation length $\xi (u,\zeta )$ is itself the representative of a crossover in the giant component, separating a self-similar organization where $g(r)\sim {r}^{-d+2-\eta}$, from a “noncritical” one marked instead by a decreasing exponential [31]. Then again, we know from Eq. (1) that $\xi (u,\zeta )$ crosses over between the mean-field and the lattice singular behaviors, depending on how close the network is to ${p}_{c}$. Let us then fix the occupation probability to a value $u\ll {u}_{*}$, so that geometric fluctuations are free to set in above ${\xi}_{*}$. In turn, this means that $\xi {|}_{u\ll {u}^{*}}\gg {\xi}_{*}$ and so the cutoff ${e}^{-r/\xi (u,\zeta )}$ becomes significant only if $r\sim \mathcal{O}({\xi}_{*})$. Therefore, reading ${g}_{u}(r,\zeta )$ as a function of $r$ for fixed $u\ll {u}_{*}$ and variable values of $\zeta $, we advance the crossover relation

$\frac{{g}_{u}(r,\zeta )}{{g}_{*}(\zeta )}={\left(\frac{r}{{\xi}_{*}(\zeta )}\right)}^{-4}\mathcal{G}(\frac{r}{{\xi}_{*}(\zeta )},\frac{\xi {|}_{u\ll {u}^{*}}}{{\xi}_{*}(\zeta )}),$

where ${g}_{*}(\zeta )\equiv {\zeta}^{-24/(6-d)}$, and $\mathcal{G}(\mathcal{x},\mathcal{y})\propto {\mathcal{x}}^{\mathrm{\Phi}(d)}{e}^{-\mathcal{x}/\mathcal{y}}$ for $\mathcal{x}\gg 1$ and constant otherwise, with $\mathcal{y}\gg 1$ and $\mathrm{\Phi}(d)=6-d-\eta $. To obtain Eq. (2), we have rescaled the argument of the exponential cutoff to make explicit the ratio $r/{\xi}_{*}$, and factorized out the mean-field regime ${g}_{\mathrm{MF}}\sim {r}^{-4}$.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 $r\ll {\zeta}^{6/(6-d)}$. 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 ${d}_{\mathrm{min}}$, and (ii) the mass fractal dimension ${d}_{f}$ of the incipient cluster [30]. Although the analysis could be carried out in any dimension $d<6$, we restrict here to the case $d=2$ for simplicity of computation. Let us start from the behavior at $p={p}_{c}$. (i) By definition, ${d}_{\mathrm{min}}$ regulates the scaling of the mean Euclidean distance $\u27e8r\u27e9$ between sites in the giant cluster separated by the chemical distance $\ell $, so that $\ell \sim \u27e8r{\u27e9}^{{d}_{\mathrm{min}}}$ for $\u27e8r\u27e9$ large enough. For future reference, we consider the reciprocal scaling $\u27e8r\u27e9\sim {\ell}^{1/{d}_{\mathrm{min}}}$, for $\ell $ large enough. In chemical space, ${\xi}_{*}$ translates [35] into the quantity ${\xi}_{\ell}^{*}\equiv \lfloor {u}_{*}^{-1}\rfloor =\lfloor \zeta \rfloor $ (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 ${d}_{\mathrm{min}}$, we must thus consider two regimes: $\ell \ll {\xi}_{\ell}^{*}$ where ${d}_{\mathrm{min}}^{\mathrm{MF}}=2$ (i.e., random walk), and $\ell \gg {\xi}_{\ell}^{*}$ where instead ${d}_{\mathrm{min}}^{2D}\simeq 1.13077(2)$[36]. Merging the two behaviors into a single equation, we propose the scaling

$\frac{\u27e8r\u27e9(\ell ,\zeta )}{{\xi}_{*}(\zeta )}=\left(\frac{\ell}{{\xi}_{\ell}^{*}(\zeta )}{)}^{\xbd}\mathcal{R}\right(\frac{\ell}{{\xi}_{\ell}^{*}(\zeta )}),$

where $\mathcal{R}(\mathcal{x})\propto {\mathcal{x}}^{1/{d}_{\mathrm{min}}^{2D}-1/2}$ for $\mathcal{x}\gg 1$ and constant otherwise. We tested Eq. (3) by using a breadth-first search algorithm whose results, displayed in Fig. 2(a), support our scaling arguments. (ii) To investigate the mass scaling $M\sim {r}^{{d}_{f}}$ at ${p}_{c}$, we first need to determine the dependence on $\zeta $ of the giant cluster’s amplitude. This quantity is found by calculating the $\zeta $ correction to the size ${S}_{\infty}$ of the giant component in the spatial regime which, according to the LG criterion, scales as ${S}_{\infty}^{2D}\propto \mathcal{B}(\zeta ){u}^{5/36}$ with $\mathcal{B}(\zeta )\equiv {\zeta}^{-31/36}$. In light of this, we obtain the scaling ${M}_{2D}\propto \mathcal{B}(\zeta ){r}^{91/48}$ for $r\gg {\xi}_{*}$ which, combined with what expected in the high-dimensional (mean-field) part, i.e., ${M}_{\mathrm{MF}}\sim {r}^{4}$[30], yields the ansatz $\frac{M(r,\zeta )}{{M}_{*}(\zeta )}=\left(\frac{r}{{\xi}_{*}(\zeta )}{)}^{4}\mathcal{M}\right(\frac{r}{{\xi}_{*}(\zeta )}),$

where $\mathcal{M}(\mathcal{x})\propto {\mathcal{x}}^{-101/48}$ for $\mathcal{x}\gg 1$, constant otherwise, and ${M}_{*}(\zeta )\equiv {\zeta}^{571/288}$ is the incipient cluster’s mass at ${\xi}_{*}$. Equation (4) states in more practical terms the prediction of Eq. (2), namely that the fractal geometry of the critical cluster in our network crosses over from the one of an ER graph [37] (i.e., ${d}_{f}^{\mathrm{MF}}=4$) to that of a $d=2$ lattice (for which ${d}_{f}^{2D}=91/48$), where the former stretches up until the intrinsic length ${\zeta}^{3/2}$. As shown in Fig. 2(b), Eq. (4) exquisitely matches the numerical data.To complete the picture, we must verify that *far* from the percolation threshold, ${\xi}_{\times}\equiv \zeta $ is indeed the characteristic length at which the geometric crossover occurs. Let us start from the mass scaling (ii) at $p=1$. In this case, the Euclidean dimension $d=2$ is expected to regulate the scaling of $M$ for distances $r\sim \mathcal{O}({\xi}_{\times})$, while an infinite-dimensional (small-world) behavior should be observed for $r\sim \mathcal{o}({\xi}_{\times})$. The numerical results in Fig. 2(c) corroborate this intuition, further showing [Fig. 2(c), inset] that below ${\xi}_{\times}$ the random structure embeds onto an Euclidean space whose dimension grows unbounded with $\zeta $. (i) The shortest-path’s scaling at $p=1$ supports this large-to small-world crossover: while for $r\lesssim {\xi}_{\times}$*any* path shall behave like a random walk [30], i.e., $\u27e8r\u27e9\propto \zeta {\ell}^{1/2}$, for $\u27e8r\u27e9\gtrsim {\xi}_{\times}$ (lattice regime) the lengths $\ell $ and $\u27e8r\u27e9$ must share the same metric, i.e., $\u27e8r\u27e9\sim \ell $. We can then advance the scaling $\u27e8r\u27e9=\zeta {\ell}^{1/2}\mathcal{f}(\ell )$ where $\mathcal{f}(\ell )\propto {\ell}^{1/2}$ for $\ell \gtrsim {\xi}_{\ell}^{\times}(\zeta )$ and constant otherwise. The quantity ${\xi}_{\ell}^{\times}$ can be regarded as the chemical length up to which the small-world extends, so ${\xi}_{\ell}^{\times}\propto \mathrm{log}{N}_{\zeta}\sim \mathrm{log}\zeta $ since ${N}_{\zeta}\sim {\zeta}^{2}$. The data collapse in Fig. 2(d) is consistent with our scaling, and further supports [Fig. 2(d), inset] the approximation ${\xi}_{\ell}^{\times}\propto \mathrm{log}\zeta $. Altogether, these results confirm the prediction that far from criticality the network’s geometry is governed by the characteristic scale $\zeta $, 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 $\beta $ and recovery time $\gamma \equiv 1$, spreading on our network model in $d=2$. In light of the mapping to percolation [32], the clusters of nodes removed by the outbreak are geometrically equivalent to those originated from a static deletion, whereas the shortest-path $\ell $ identifies now the number of time steps $t$ separating infected nodes in the $\ell $th shell from an initial spreader. Setting the relative rate ${\beta}^{\prime}\equiv 1-\beta /{\beta}_{c}$ to a value ${\beta}^{\prime}\ll {\zeta}^{-1}$, we thus expect the spreading of the disease to undergo a *temporal crossover* at the intrinsic time scale ${\tau}_{*}\equiv \lfloor \zeta \rfloor $ from a mean-field behavior to a spatial one. In particular, interpreting $\u27e8r\u27e9$ as the average distance of the infective nodes from an initial spreader, we can deduce from Eq. (3) that the spreading velocity $\mathcal{v}\u2254d\u27e8r\u27e9/dt\sim {t}^{1/{d}_{\mathrm{min}}-1}$ of the outbreak front will accordingly satisfy the temporal scaling

$\frac{\mathcal{v}(t,\zeta )}{{\mathcal{v}}_{*}(\zeta )}=\left(\frac{t}{{\tau}_{*}(\zeta )}{)}^{-\xbd}\mathcal{V}\right(\frac{t}{{\tau}_{*}(\zeta )}),$

where $\mathcal{V}(\mathcal{x})\propto {\mathcal{x}}^{1/{d}_{\mathrm{min}}^{2D}-1/2}$ for $\mathcal{x}\gg 1$, constant otherwise, and ${\mathcal{v}}_{*}(\zeta )\equiv {\zeta}^{1/2}$ is the crossover critical velocity. The data collapse in Fig. 3 validates our premises, confirming that, if critical, the epidemic front undergoes a spatiotemporal crossover at the distances $({\xi}_{*},{\tau}_{*})$ from the infective spreader, varying from diffusive to superdiffusive propagations. Since the crossover time scale stretches from a logarithmic—${\tau}_{\times}\propto \mathrm{log}\zeta $ far from criticality—to a linear dependence with $\zeta $, we disclose an intriguing scenario: if critical, an outbreak will invade the system at “slow” (i.e., diffusive) rates for longer times, before turning superdiffusive. Besides of theoretical interest, these results are relevant for the analysis of spreading processes in real-world systems, e.g., in virus propagation on wireless networks [16], in the spreading of diseases through transportation systems [19,20] or of rumors in social networks [21], whose spatial constraints are well captured by the exponential wiring cost function here adopted.*Discussion.*—In this Letter, we have investigated the effects that a tunable characteristic link length $\zeta $ 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 ($p\gg {p}_{c}$) or close to ($p\to {p}_{c}$) its percolation threshold. We found that while this crossover occurs at $\zeta $ when $p=1$, it surprisingly extends until ${\zeta}^{6/(6-d)}$ close to ${p}_{c}$, signaling that the mean-field (ER) structure expands beyond the *input* characteristic link length $\zeta $ near criticality. We named this phenomenon *critical stretching*, and we demonstrated its geometric and dynamic features by analyzing the Euclidean correlation length $\xi (p,\zeta )$ and its chemical counterpart ${\xi}_{\ell}(p,\zeta )$, whose crossover scales are summarized in Table I.

Some relevant comments are in order. (i) The critical stretching length scales ${\xi}_{*}$ and ${\xi}_{\ell}^{*}$ 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 [35] 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 $d=3$ networks, e.g., the intrinsic scales ${\xi}_{*}={\xi}_{\ell}^{*}={\zeta}^{2}$ at ${p}_{c}$ are significantly larger if compared to the crossover scales ${\xi}_{\times}=\zeta $ and ${\xi}_{\ell}^{\times}\propto \mathrm{log}\zeta $ 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 [13] or the neural functioning—e.g., in reference to the observed activity before epileptic seizures [38]—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.

We consider $\zeta \in [1,L/2)$, where ${\zeta}_{\mathrm{max}}=L/2$ reflects the choice of periodic boundary conditions (and avoids links’ re-drawing), while the lower bound ${\zeta}_{\mathrm{min}}=1$ describes the lattice-dominated regime, since $\rho \sim 1/{a}^{d}$ for $L\gg 1$, where $a\equiv 1$ is the lattice spacing.

See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevLett.123.088301 for details on the percolation LG criterion, and for the finite-size analysis of the critical stretching length scales.

Citing articles via

Tweets

https://www.researchpad.co/tools/openurl?pubtype=article&doi=10.1103/PhysRevLett.123.088301&title=Critical Stretching of Mean-Field Regimes in Spatial Networks&author=Ivan Bonamassa,Bnaya Gross,Michael M. Danziger,Shlomo Havlin,&keyword=&subject=Letters,Polymer, Soft Matter, Biological, Climate, and Interdisciplinary Physics,

© 2020 Newgen KnowledgeWorks | Privacy & Cookie Policy | Powered by: Nova