Google matrix, dynamical attractors, and Ulam networks

We study the properties of the Google matrix generated by a coarse-grained Perron-Frobenius operator of the Chirikov typical map with dissipation. The finite-size matrix approximant of this operator is constructed by the Ulam method. This method applied to the simple dynamical model generates directed Ulam networks with approximate scale-free scaling and characteristics being in certain features similar to those of the world wide web with approximate scale-free degree distributions as well as two characteristics similar to the web: a power-law decay in PageRank that mirrors the decay of PageRank on the world wide web and a sensitivity to the value $\alpha$ in PageRank. The simple dynamical attractors play here the role of popular websites with a strong concentration of PageRank. A variation in the Google parameter $\alpha$ or other parameters of the dynamical map can drive the PageRank of the Google matrix to a delocalized phase with a strange attractor where the Google search becomes inefficient.

Figure 1

(Color online) PageRank $p_j$ for the Google matrix generated by the Chirikov typical map (2) at $T=10$, $k=0.22$, $\eta =0.99$ (set $T10$, top row), and $T=20$, $k=0.3$, $\eta =0.97$ (set $T20$, bottom row) with $\alpha =1$ (left column), 0.95 (middle column), 0.85 (right column); the value of index $j$ is a function of the cell index in the map phase space $\left(i_x;i_y\right)$ (see text), here $p_j$ is plotted in phase space of the map using the above relation between $j$ and $\left(i_x,i_y\right)$. The phase space region $0\le x<2\pi ;-\pi \le y<\pi$ is divided on $N=3.6\times {10}^5$ cells; $p_j$ is zero for black and maximal for white.

Figure 2

Bifurcation diagram showing values of $y$ vs map parameter $k$ for the set $T10$ of the Chirikov typical map [Eq. (2)]. The values of $y$, obtained from ten trajectories with initial random positions in the phase space region, are shown for integer moments of time $100<t/T\le 110$ (left panel) and ${10}^4<t/T\le {10}^4+100$ (right panel).

Figure 3

Same as in Fig. 2 for the set $T20$.

Figure 4

(Color online) Differential distribution of number of nodes with ingoing $P_{in}\left(\kappa \right)$ (blue/black) and outgoing $P_{out}\left(\kappa \right)$ (red/gray) links $\kappa$ for sets $T10$ (left) and $T20$ (right) (top and bottom curves at ${\text{log}}_{10}\kappa =0.6$ correspond to red/gray and blue/black curves). The straight dashed lines give the algebraic fit $P\left(\kappa \right)\sim {\kappa }^{-\mu }$ with the exponent $\mu =1.86$, 1.11 $\left(T10,T20\right)$ for ingoing and $\mu =1.91$, 1.46 $\left(T10,T20\right)$ outgoing links. Here $N=1.44\times {10}^6$ and $P\left(\kappa \right)$ gives a number of nodes at a given integer number of links $\kappa$ for this matrix size. Isolated blue/black point at $\kappa =0$ shows that in the whole matrix there is a significant number of nodes with zero ingoing links. We note that the WWW is characterized by the exponents $\mu \approx 2.1$, 2.7 for ingoing and outgoing links respectively (see, e.g., [3, 7]).

Figure 5

(Color online) Same as in Fig. 3 for the set $T10$ at $k=0.22$ (left) (same as Fig. 4 left) and $k=0.6$ (right) and $N=3.6\times {10}^5$. The fit gives the exponent $\mu =1.87$, 1.92 for ingoing (blue/black), outgoing (red/gray) links at $k=0.22$ (left) and $\mu =1.70$, 1.83 for ingoing (blue), outgoing (red) links at $k=0.6$ (right) (top and bottom curves at ${\text{log}}_{10}\kappa =0.8$ correspond to red/gray and blue/black curves). Isolated blue/black point at $\kappa =0$ shows that in the whole matrix there is a significant number of nodes with zero ingoing links.

Figure 6

(Color online) PageRank distribution $p_j$ for $N={10}^4$, $9\times {10}^4$, $3.6\times {10}^5$, and $1.44\times {10}^6$ (larger $N$ have more dark and more long curves in (b), (c), (e), and (f); in (a) this order of $N$ is for curves from bottom to top (curves for $N=3.6\times {10}^5$ and $1.44\times {10}^6$ practically coincide in this panel) and in (d) this order of $N$ is for curves from top to bottom at $j\approx 500$ (curves for $N=9\times {10}^4$, $3.6\times {10}^5$, and $1.44\times {10}^6$ practically coincide in this panel); for online version we note that the above order of $N$ values corresponds to red, magenta, green, and blue curves, respectively). The dashed straight lines show fits $p_j\sim 1/j^{\beta }$ with $\beta$: (b) 0.48, (e) 0.88, and (f) 0.60. Dashed lines in panels (a) and (d) show an exponential Boltzmann decay (see text, lines are shifted in $j$ for clarity). Other parameters, including the values of $\alpha$, and panel order are as in Fig. 1. In panels (a) and (d) the curves at large $N$ become superimposed. Here and below logarithms are decimal.

Figure 7

(Color online) (a) Dependence of gap $1-\left|\lambda \right|$ on Google matrix size $N$ for few eigenstates with $\left|\lambda \right|$ most close to 1, set $T10$, $\alpha =1$; (b) dependence of PAR $\xi$ on $\gamma =-2\text{ln}\left|\lambda \right|$ for $N=2500$, 5625, 8100, ${10}^4$, $14400$ for set $T10$, $\alpha =1$ (curves from top to bottom at $\gamma =4$, in online version this order of curves corresponds to colors red, magenta, green, blue, black); (c) complex plane of eigenvalues $\lambda$ for set $T10$ with their PAR $\xi$ values shown by grayness (black/blue for minimal $\xi \approx 4$, gray/light magenta for maximal $\xi \approx 300$; here $\alpha =1$, $N=1.44\times {10}^4$); (d) same as (c) but for set $T20$.

Figure 8

Probability distribution $dW\left(\gamma \right)/d\gamma$ for set $T10$, $\alpha =1$ at $N=2.5\times {10}^3(\times )$, ${10}^4(+)$, $1.44\times {10}^4$ (dots); $W\left(\gamma \right)$ is normalized by the number of states $N_{\gamma }=0.55N^{0.85}$ with $\gamma <6$. Inset: dependence of number of states $N_{\gamma }$ with $\gamma <{\gamma }_b$ on $N$ for sets $T10$ (circles, ${\gamma }_b=6$) and $T20$ (triangles, ${\gamma }_b=3$); dashed lines show the fit $N_{\gamma }=A{N}^{\nu }$ with $A=0.55,\nu =0.85$ and $A=0.97,\nu =0.61$ respectively.

Figure 9

(Color online) Dependence of PageRank $\xi$ on $\alpha$ for set $T10$ at $N=5625$ (dotted magenta/gray), $1.44\times {10}^4$ (dotted red/gray, $9\times {10}^4$ (dashed red/gray, $6.4\times {10}^5$ (full red/gray), (these four curves follow from bottom to top at $\alpha =0.9$ for small to large values of $N$ respectively); and for set $T20$ at $N=1.44\times {10}^4$ (dotted blue/black), $9\times {10}^4$ (dashed blue/black), $6.4\times {10}^5$ (full blue/black), (these three blue/black curves follow from bottom to top at $\alpha =0.6$). Inset shows dependence of $\xi$ on $k$ for set $T10$ at $\alpha =0.99$ with $N=1.44\times {10}^4$ (dotted red/gray), $9\times {10}^4$ (dashed red/gray), $3.6\times {10}^5$ (full red/gray) (this corresponds to the order of curves from top to bottom at $k=0.45$).

Figure 10

(Color online) Same as Fig. 1 for the set $T10$ at $\alpha =0.99$, $N=3.6\times {10}^5$ at $k=0.22$ (left) and $k=0.6$ (right); PAR $\xi$ are the same as in the inset of Fig. 9.

Figure 11

(Color online) Dependence of the network contraction factor $\Gamma$ on the level $q$ of probability distribution over the network nodes (see text). Left panel shows data for the set $T10$ at $k=0.22$, right panel shows data for the set $T20$ at $k=0.3$ for the Ulam network of map [Eq. (2)]. The size of the network is $N={10}^4,4\times {10}^4,16\times {10}^4$ (curves from top to bottom at $q=0.01$). The dashed line (in left/right panels) shows the contraction ${\Gamma }_c={\eta }^T$ of the continuous map [Eq. (2)] corresponding to the network with $N=\infty$ and to values $\eta$ and $T$ for the sets $T10$ and $T20$, respectively.