Delocalization transition for the Google matrix

We study the localization properties of eigenvectors of the Google matrix, generated both from the world wide web and from the Albert-Barabási model of networks. We establish the emergence of a delocalization phase for the PageRank vector when network parameters are changed. For networks with localized PageRank, eigenvalues of the matrix in the complex plane with a modulus above a certain threshold correspond to localized eigenfunctions while eigenvalues below this threshold are associated with delocalized relaxation modes. We argue that, for networks with delocalized PageRank, the efficiency of information retrieval by Google-type search is strongly affected since the PageRank values have no clear hierarchical structure in this case.

Figure 1

(Color) Distribution of eigenvalues ${\lambda }_i$ of Google matrices in the complex plane. Color is proportional to the PAR $\xi$ of the associated eigenvector ${\psi }_i$. Top panel: AB model with $q=0.1$ for $N=2^{14}$ for $N_r=5$ random realizations (see text), $\xi$ varies from $\xi =32$ (blue) to $\xi =1656$ (red); middle panel: same with $q=0.7$, $\xi$ varies from $\xi =1169$ (red) to $\xi =3584$ (purple); bottom panel: data for a university network LJMU with $N=13578$; here in order to get statistically significant data the WWW network was randomized and data correspond to $N_r=5$ random realizations (see text), $\xi$ varies from $\xi =7$ (blue) to $\xi =1177$ (red).

Figure 2

(Color online) Normalized density of states $W$ (top panel) and PAR (bottom panel) as a function of $\gamma$. Data for AB model with $q=0.1$ are shown by full curves from bottom to top at $\gamma =4$ with corresponding $N=2^{10}$ ($N_r=100$ random realizations) (black), $2^{11}$ $\left(N_r=50\right)$ (red), $2^{12}$ $\left(N_r=20\right)$ (green), $2^{13}$ $\left(N_r=10\right)$ (blue), and $2^{14}$ $\left(N_r=5\right)$ (violet). Symbols give the PageRank value of $\xi$ in the same order: circle, square, diamond, triangle down, and triangle up. All curves coincide on the top panel. Dashed curves show the data from the WWW (LJMU network, parameters of Fig. 1). Here and in other figures the quantities shown are dimensionless.

Figure 3

(Color online) Same as in Fig. 2 for AB model at $q=0.7$.

Figure 4

(Color online) Dependence of $\xi$ on matrix size $N$ for AB model at $q=0.1$ (triangles), $q=0.7$ (circles), and for WWW data without randomization (squares). Full symbols are for PageRank $\xi$ values, empty symbols are for eigenvectors with $3<\gamma <4$ (AB model) or for the ten eigenvectors with highest $\xi$ and $\gamma <10$ (WWW data). For AB model the number of random realizations $N_r$ is as in Fig. 2 and $N_r=5$ for $N>2^{14}$ (statistical error bars are smaller than symbol size). Dotted blue lines give linear fits of WWW data, with slopes, respectively, of 0.01 and 0.53. Upper dashed line indicates the slope of 1. Logarithms are decimal.

Figure 5

(Color online) Dependence of eigenvectors ${\psi }_i\left(j\right)$ of AB model on index $j$ ordered in decreasing PageRank values $p_j$ [with normalization ${\sum }_j{\left|{\psi }_i\left(j\right)\right|}^2=1$ and ${\sum }_j{p}_j=1$]. Full smooth curves are PageRank vectors for $N=2^{14}$, dashed smooth curves for $N=2^{19}$. Nonsmooth curves are eigenvectors $\left(N=2^{14}\right)$ within $3<\gamma <4$ with ${\left|{\Psi }_i\left(j\right)\right|}^2$ averaged in this interval. States are averaged over $N_r=5$ random networks. Black is for $q=0.1$, red/gray for $q=0.7$. Inset: cumulative distribution $P_c\left(p_j\right)$ normalized by $P_c\left(0\right)=N$ for AB model ($N=2^{18}$ and $N_r=5$) at $q=0.1$ (full black) and $q=0.7$ (dashed red/gray), and for LJMU nonrandomized data (full red/gray). Dashed straight line indicates slope $1-\nu =-1$. Logarithms are decimal.