Scaling Laws in Spatial Network Formation

Geometric constraints impact the formation of a broad range of spatial networks, from amino acid chains folding to proteins structures to rearranging particle aggregates. How the network of interactions dynamically self-organizes in such systems is far from fully understood. Here, we analyze a class of spatial network formation processes by introducing a mapping from geometric to graph-theoretic constraints. Combining stochastic and mean field analyses yields an algebraic scaling law for the extent (graph diameter) of the resulting networks with system size, in contrast to logarithmic scaling known for networks without constraints. Intriguingly, the exponent falls between that of self-avoiding random walks and that of space filling arrangements, consistent with experimentally observed scaling of the radius of gyration of protein tertiary structures with their chain length.

Figure 1

Mapping spatial structure formation onto network formation. Units coming into spatial contact (green dashed lines) induce additional links on the network level. The network becomes more and more compact as links add, in two dimensions, yielding a subgraph of the triangular grid. For illustration, panels show networks of $N=11$ units for time steps $t\in \{1,2,\dots ,8\}$.

Figure 2

Mapping constraints from spatial geometry to network topology. Links in the contact graph form when two randomly chosen units come into spatial contact, subject to geometric constraints (a)–(d) specified in the text. Process 1: adding a link (green dashed line) is allowed because all conditions (a)–(d) are satisfied. Process 2: adding a link (red dashed line) is forbidden due to condition (a) to avoid overlapping units. Process 3: adding a link on the outer face is forbidden due to condition (b) to avoid the possibility that units (here the one shaded yellow) may with later links (red dotted line) be enclosed by less than six other units during a subsequent step (e.g., red dotted line)

Figure 3

Algebraic scaling laws in spatial network formation. (a) Scaling of chain lengths of experimentally analyzed proteins vs their radii of gyration [Eq. (1)] (37 162 data points from [19] logarithmically binned into 100 equally spaced intervals on log($N$) scale, with error bars indicating standard deviations). Best fits suggest algebraic (red) rather than logarithmic (gray) scaling. [Logarithmic fitting by $R_g=a\ln (bN+c)-a\ln (c)$ ensuring that $\underset{N\to 0}{\lim }{R}_g(N)=0$.] (b) Algebraic scaling of graph diameter $D_{\mathsf{\text{final}}}(N)$ as derived in this Letter (orange line), plotted vs the chain lengths $N$. Black dots indicate 450 stochastic realizations of network formation processes [uniformly sampled on a logarithmic chain length scale, binned and evaluated as in (a)] indicating the diameter of the original graph with best algebraic fit (red line). The algebraic scaling law with the (inverse) scaling dimension $\nu$ lying between that of self-avoiding random walk ${\nu }_{\mathsf{RW}}$ (green dashed lines) and that of space filling aggregates (blue dotted lines) is consistent with biological data but inconsistent with logarithmic scaling as expected from network formation processes without geometric constraints.

Figure 4

Diameter path, diameter graph, and end cycles. A diameter path is a sequence of cycles of maximum length (here $D_t=7$, indicated by the dashed red line. For large graphs with defined average cycle length, $D_t$ is proportional to the diameter of the original graph (black dots, black solid lines, pink solid lines indicate diameter). The diameter graph is the union of all such diameter paths (all shaded regions). $V_t$ denotes the number of cycles on the diameter graph (here $V_t=12$) and $E_t$ the number of end cycles (with only one neighbor) on any diameter path (here $E_t=5$, shaded light rose).

Figure 5

Diameter-increasing vs diameter-conserving link addition. Example illustrating three cycles of length $\ell$, ${\ell }^{\prime }$, and $\ell ″$ along the diameter graph with the dashed lines signifying the rest of the network. Adding a link (red) parallel to the diameter path leaves the diameter constant and creates a branch. Adding a link (blue) transverse to the path (and thus parallel to the edges indicated by wiggled lines) increases the diameter by one. Out of the $\ell (\ell -3)/2$ potential links to add, $h_1{h}_2-2$ may add transversely.