Small world of Ulam networks for chaotic Hamiltonian dynamics

We show that the Ulam method applied to dynamical symplectic maps generates Ulam networks which belong to the class of small-world networks appearing for social networks of people, actors, power grids, biological networks, and Facebook. We analyze the small-world properties of Ulam networks on examples of the Chirikov standard map and the Arnold cat map showing that the number of degrees of separation, or the Erdös number, grows logarithmically with the network size for the regime of strong chaos. This growth is related to the Lyapunov instability of chaotic dynamics. The presence of stability islands leads to an algebraic growth of the Erdös number with the network size. We also compare the time scales related with the Erdös number and the relaxation times of the Perron-Frobenius operator showing that they have a different behavior.

Figure 1

Left panels: Probability distribution $w_E$ of Erdös number $N_E$ for the Ulam network of the Chirikov standard map at $K=7$ (a) and $K=7+2\pi$ (c) for three different numbers of nodes (cells) $N_d\approx M^2/2$ using a hub cell at $x=0.1/\left(2\pi \right),p=0$. [(b) and (d)] Probability distribution $w_l$ of number of links $N_l$ per node of the networks of panels (a) and (c), respectively. In all cases the Ulam network was constructed with one trajectory of ${10}^{12}$ iterations using the initial condition $x=0.1/\left(2\pi \right), p=0.1/\left(2\pi \right)$.

Figure 2

Dependence of the average Erdös number $\langle N_E\rangle$ on the number of nodes (cells) $N_d$ for the Ulam network of the Chirikov standard map at $K=5$ (top data points, black dots), $K=7$ (both sets of center data symbols of red pluses and green squares), and $K=7+2\pi \approx 13.28$ (bottom data points, blue stars). The hub cell is either at $x=0.1/\left(2\pi \right), p=0$ (top, center with red plus symbols and bottom) or at $x=0.1/\left(2\pi \right), p=0.1/\left(2\pi \right)$ (center data with green squares).

Figure 3

Properties of the Erdös number $N_E$ for the Ulam network of the Arnold cat map on a torus with $L=3$ with hub cell at position $x=p=0$. (a) Frequency distribution $N_f\left(N_E\right)$ for three different values of $M$. The pink line corresponds to the fit $N_f\left(E\right)=C{e}^{h{N}_E}$ for $M=14699$ using the fit range $2\le N_E\le 18$ with $C=1.777\pm 0.005$ and $h=0.9629\pm 0.0002$. (b) Dependence of average $\langle N_E\rangle$ on the number of nodes (cells) $N_d=L{M}^2$ (red plus symbols). The blue stars correspond to a restricted average over nodes being in the center square box with $\left|x\right|<0.5$ and $\left|p\right|<0.5$ (instead of $\left|x\right|<0.5$ and $\left|p\right|<L/2$ for the full average). The pink line corresponds to the fit (of top data points) $\langle N_E\rangle =d+ln\left(N_d\right)/\tilde{h}$ with $d=-1.25\pm 0.08$ and $\tilde{h}=0.957\pm 0.005$. The two values of $h$ and $\tilde{h}$ compare to the theoretical Lyapunov exponent $h_{\mathrm{th}}=ln[(3+\sqrt{5})/2]\approx 0.9624$. The Ulam network for the Arnold cat map was constructed from exact theoretical transition probabilities as described in Appendix. The number of links per node is constant for all nodes: $N_l=5$ (4 or 6) if $M$ and $LM$ are odd ($M$ and $LM$ even or $M$ odd and $LM$ even, respectively).

Figure 4

Top: Color density plot of the probability distribution in the phase plane $(x,p)$ obtained after $t=4$ (a) or $t=7$ (b) iterations of the UPFO ($M=400$, resolution $400\times 200$ boxes) for the Chirikov standard map at $K=7$ with an initial state being localized in one cell at $x=p=0.1/\left(2\pi \right)$. The colors red, green, and blue correspond to maximum, medium, and minimal values. (c) Density plots of the Erdös number of nodes or cells for the Ulam network (standard map, $K=7$, same hub position as in Fig. 1) in the phase plane $(x,p)$ with red, green, and light blue corresponding to smallest, medium, and largest Erdös numbers. The dark blue cells correspond to nonaccessible islands which do not contribute as nodes for the Ulam network. Left panel corresponds to one full square box of the phase space given by $0\le x<1$ and $-0.5\le p<0.5$ for $M=400$ (resolution $400\times 400$ boxes). Panel (d) shows a zoom of $200\times 200$ cells with bottom left corner at cell position (935,1500) for $M=3200$ and containing the left of the two islands (for $K=7$). In both bottom panels data for cells with $p<0$ are obtained from the symmetry: $p\to -p$ and $x\to 1-x$.

Figure 5

Same as in Fig. 1 but for the golden critical value $K=K_g=0.971635406$ of map (1).

Figure 6

Density plots of Erdös number (similar as in bottom panels of Fig. 4) for the Ulam network of the Chirikov standard map at the golden critical value $K=K_g=0.971635406$ for $M=3200$ [top panel (a), hub cell at position $x=0.1/\left(2\pi \right), p=0$, resolution $3200\times 1600$ boxes] and of the Arnold cat map for $M=59, L=3$ [bottom panel (b), hub cell at position $x=p=0$, resolution $59\times 177$ boxes]. In the latter case the roles of the $x$ and $p$ axes have been exchanged for a better visibility.

Figure 7

Dependence of the average Erdös number $\langle N_E\rangle$ on the number of nodes (cells) $N_d$ for the Ulam network of the Chirikov standard map at $K=K_g$ (red plus symbols) with hub cell at $x=0.1/\left(2\pi \right), p=0$ in a double logarithmic representation. The blue line corresponds to the fit $\langle N_E\rangle =C{N}_d^b$ with $C=1.15\pm 0.04$ and $b=0.297\pm 0.004$.

Figure 8

Double logarithmic representation of fraction $P\left(w_l\right)$ of links with weight below $w_l$ of the Ulam network for the Chirikov standard map with various values of $K$ and $M$. The lower curves are successively shifted down by a factor of 10 for a better visibility. The top straight blue line corresponds to the simplified power law behavior $\sim w_l^{0.5}$. The power law fits $P_w\left(w_l\right)=C{w}_l^b$ for the range $5\times {10}^{-5}<w_l<2.5\times {10}^{-2}$ for $K\ge 5$ (${10}^{-4}<w_l<5\times {10}^{-1}$ for $K=K_g$) provide the fit values (top to bottom curves): $C=2.63\pm 0.03,1.64\pm 0.01,1.68\pm 0.02,1.31\pm 0.01,1.39\pm 0.02$ and $b=0.584\pm 0.002,0.521\pm 0.001,0.525\pm 0.002,0.542\pm 0.001,0.571\pm 0.003$. The vertical lines of data at the left side correspond to the smallest possible weight values $N_d/{10}^{12}$ being the typical inverse number of trajectory crossings per cell with $N_d\approx M^2/2$ for $K\ge 5$ or $N_d\approx M^2/4$ for $K=K_g$.

Figure 9

Dependence of the decay rate ${\gamma }_1=-2ln\left|{\lambda }_1\right|$ on network size where ${\lambda }_1$ is the second eigenvalue of the UPFO for the Chirikov standard map. Top panels correspond to the values $K=5,7,7+2\pi$ [(a) and (b)] and bottom panels [(c) and (d)] to $K=K_g$. Left panels show the dependence of ${\gamma }_1^{-1}$ on network size $N_d$ with a logarithmic representation for $N_d$ (and also for ${\gamma }_1^{-1}$ for bottom panel with $K=K_g$). Right panels [(b) and (d)] show the dependence of ${\gamma }_1$ on $M^{-1}$ where $N_d\approx M^2/2$ ($M^2/4$) for the cases with $K\ge 5$ ($K=K_g$). The blue line in bottom left panel corresponds to the power law fit: ${\gamma }_1^{-1}=C{\left(N_d\right)}^b$ with $C=1.3\pm 0.2$ and $b=0.64\pm 0.01$ for the fit range $N_d>{10}^4$.

Figure 10

(a) Dependence of the inverse decay rate ${\gamma }_1^{-1}=(-2ln|{\lambda }_1{\left|\right)}^{-1}$ on $M$ where ${\lambda }_1$ is the second eigenvalue of the UPFO for the Arnold cat map for the cases $L=2,3,4,5$ and certain prime numbers $29\le M\le 983$. The horizontal lines correspond to the theoretical values ${\left[{\gamma }_1^{\left(\mathrm{diff}\right)}\right]}^{-1}={[D{\left(2\pi \right)}^2/L^2]}^{-1}=3L^2/{\pi }^2$ based on diffusive dynamics in the $p$ direction with diffusion constant $D=1/12$, finite system size $L$, and periodic boundary conditions. (b) Complex spectrum of top $\sim 4000$ reliable eigenvalues ${\lambda }_j$ of the UPFO for the Arnold cat map at $L=3, M=983$ obtained by the Arnoldi method with Arnoldi dimension 5000 and using a symmetrized version of the map in $p$ direction for $0\le p<L/2$ [symmetrized matrix size $N_d^{\left(\mathrm{sym}\right)}\approx L{M}^2/2\approx 1.5\times {10}^6]$. The green curve corresponds to the unit circle. The first two eigenvalues ${\lambda }_0=1$ and ${\lambda }_1\approx 0.834183$, corresponding to ${\gamma }_1\approx 0.362604$, are shown as red dots of increased size.

Figure 11

Parallelogram image of one initial square Ulam cell shown in the grid of possible target cells. The panels correspond to the Arnold cat map with both $M$ and $LM$ even (a), $M$ odd and $LM$ even (b), both $M$ and $LM$ odd (c), and the Chirikov standard map with parameters ${\xi }_0=0.8$ and $A=1.5$ (d). The thick black dots correspond to the map image of a reference point on the grid $(x_i\mathrm{\Delta }s,p_i\mathrm{\Delta }s)$ with integer $x_i, p_i$ and linear cell size $\mathrm{\Delta }s=1/M$. The relative intersection areas of the parallelogram with possible target cells provide exactly (approximately) the transition probability of the UPFO for the cat (standard) map. For the Arnold cat map we have four target cells with probability $1/4$ (both $M$ and $LM$ even), two target cells with probability $3/8$ and four target cells with probability $1/16$ ($M$ odd and $LM$ even) or one target cell with probability $1/2$ and four target cells with probability $1/8$ (both $M$ and $LM$ odd).