Complex network view of evolving manifolds

We study complex networks formed by triangulations and higher-dimensional simplicial complexes representing closed evolving manifolds. In particular, for triangulations, the set of possible transformations of these networks is restricted by the condition that at each step, all the faces must be triangles. Stochastic application of these operations leads to random networks with different architectures. We perform extensive numerical simulations and explore the geometries of growing and equilibrium complex networks generated by these transformations and their local structural properties. This characterization includes the Hausdorff and spectral dimensions of the resulting networks, their degree distributions, and various structural correlations. Our results reveal a rich zoo of architectures and geometries of these networks, some of which appear to be small worlds while others are finite dimensional with Hausdorff dimension equal or higher than the original dimensionality of their simplices. The range of spectral dimensions of the evolving triangulations turns out to be from about 1.4 to infinity. Our models include simplicial complexes representing manifolds with evolving topologies, for example, an $h$-holed torus with a progressively growing number of holes. This evolving graph demonstrates features of a small-world network and has a particularly heavy-tailed degree distribution.

Figure 1

Pachner moves. The zero-move increases the number of faces by 2. The two-move reduces their number by 2.

Figure 2

Examples of transformations that can be reduced to a sequence of Pachner moves. (a) In any of two directions, operation $C1$ can be performed as a sequence two Pachner moves; from left to right: first $P1$ and then $P2$; from right to left: first $P2$ and then $P1$. (b) In either of two directions, operation $C2$ can be performed as a sequence of three Pachner moves.

Figure 3

The “elementary” operation $S$: splitting and merging of adjacent edges and their joint vertex. The two adjacent edges and their joint vertex are transformed into two adjacent triangles sharing the new edge between the joint vertex and its counterpart. The move from left to right creates two new faces. The move from right to left eliminates two faces. All other faces in this triangulation stay intact. Any triangular mesh transformation can be reduced to a finite sequence of steps, each of which is this operation.

Figure 4

Pachner move $P2$ can be performed in two steps by applying $S$ twice.

Figure 5

Operation $S^{\prime }$. In contrast to $S$ in Fig. 3, the new edge here interconnects the opposite ends of the adjacent edges. Note the following restriction: the adjacent edges on the left cannot belong to the same triangle.

Figure 6

(a) The degree distribution of model G1: the results of numerical simulations (network of $2^{27}$ vertices, 200 samples) and the theoretical curve, Eq. (8). (b) The corresponding cumulative degree distribution $P_{\text{cum}}\left(k\right)={\sum }_{q\ge k}P\left(q\right)$, simulations, and the expression $12/\left[k\right(k+1\left)\right]$, obtained from Eq. (8).

Figure 7

Degree-degree correlations in model G1. (a) The average degree ${\langle k\rangle }_{\text{nn}}\left(k\right)$ of the nearest neighbors of a vertex of degree $k$. (b) The average degree ${\langle k\rangle }_{\text{on}}\left(k\right)$ of the vertex in a rhombus, opposite to a vertex of degree $k$, that is not its nearest neighbor. The points in the plots are obtained by logarithmic binning the results of numerical simulations for a network of $2^{27}$ vertices. The numerical simulations employ 200 samples.

Figure 8

(a) The degree distribution of model G2: the results of numerical simulations (network of $2^{27}$ vertices, 200 samples) and the theoretical curve, Eq. (11). (b) The corresponding cumulative degree distribution $P_{\text{cum}}\left(k\right)$, simulations, and the expression $120/\left[k\right(k+1\left)\right(k+2\left)\right]$, obtained from Eq. (11).

Figure 9

Degree-degree correlations in model G2. The average degree ${\langle k\rangle }_{\text{nn}}\left(k\right)$ of the nearest neighbors of a vertex of degree $k$. (b) The average degree ${\langle k\rangle }_{\text{on}}\left(k\right)$ of the vertex in a rhombus, opposite to a vertex of degree $k$, that is not its nearest neighbor. The points in the plots are obtained by logarithmic binning the results of numerical simulations for a network of $2^{27}$ vertices. The numerical simulations employ 200 samples.

Figure 10

(a) The average number of vertices $V\left(r\right)$ at a distance $r$ or smaller from a randomly chosen vertex as a function of $r$ for the models G, G2, Ga, Gb, and Gc of growing triangulation networks. (b) The logarithmic derivative $dlnV\left(r\right)/dlnr$. The presence of a plato on a curve for the logarithmic derivative indicates that the corresponding network is finite dimensional. The networks in the numerical simulations are of $2^{28}$ vertices. The sizes of samples in the simulations for models G, Ga, Gb, and Gc are 16, 24, 16, and 16, respectively. For each sample, 100 vertices are chosen uniformly at random, around which the spheres of radius $r$ are made.

Figure 11

(a) Cumulative number of Laplacian spectrum eigenvalues, $N_{<}\left(\lambda \right)={\sum }_{i:0<{\lambda }_i\le \lambda }1$, for the models G1, G2, G, Ga, Gb, Gc, and GW of growing triangulation networks. The spectra are obtained for the networks of $2^{17}$ vertices. The results are accumulated from 639, 256, 64, 32, 64, 32, and 32 samples for models G1, G2, G, Ga, Gb, Gc, and GW respectively. (b) Cumulative number of Laplacian spectrum eigenvalues for the models E1, E2, and E3 of equilibrium triangulation networks. The spectra are obtained for the networks of $2^{15}$ vertices. For each model, the results are accumulated from 32 samples. The dashed lines have the slope 1, corresponding to the Laplacian dimension $d_L=2$.

Figure 12

(a) Degree distribution of the model GW of a growing triangulation network with periodically merging triangles ($h$-holed torus). Different periods $\theta$ for introducing the holes are considered, $\theta =10,20,50,100,200,500,1000,2000,$ and $\infty$. The resulting networks in the numerical simulations are of $2^{20}$ vertices, the averaging is over 10 (for $\theta =10$) or 100 (for $\theta \ge 20$) samples. The infinite period $\theta$ provides model G2. (b) The corresponding cumulative degree distributions.

Figure 13

The time evolution of the average distance between vertices in the model GW of a growing triangulation network with periodically merging triangles. Different curves are obtained for different periods $\theta$ of introducing the holes, $\theta =10,20,50,100,200,500,1000,2000,$ and $\infty$. The curve for $\theta \to \infty$ corresponds to model G2.

Figure 14

Cumulative number of Laplacian spectrum eigenvalues of model GW for a set of values $\theta =10,20,50,100,200,500,1000,2000,$ and $\infty$. The network size is $2^{17}$ vertices.

Figure 15

Cumulative number of Laplacian spectrum eigenvalues of model GW, $\theta =200$, for a set of network sizes. The inset shows the cumulative density of the Laplacian spectrum $N_{<}\left(\lambda \right)/N$ vs $\lambda$ for the same set of network sizes. Notice that all the curves in the inset precisely coincide in the respective regions of $\lambda$.