Spectral properties of the Google matrix of the World Wide Web and other directed networks

We study numerically the spectrum and eigenstate properties of the Google matrix of various examples of directed networks such as vocabulary networks of dictionaries and university World Wide Web networks. The spectra have gapless structure in the vicinity of the maximal eigenvalue for Google damping parameter $\alpha$ equal to unity. The vocabulary networks have relatively homogeneous spectral density, while university networks have pronounced spectral structures which change from one university to another, reflecting specific properties of the networks. We also determine specific properties of eigenstates of the Google matrix, including the PageRank. The fidelity of the PageRank is proposed as a characterization of its stability.

Figure 1

Distribution of eigenvalues ${\lambda }_i$ of Google matrices in the complex plane at $\alpha =1$ for dictionary networks: Roget $\left(A,N=1022\right)$, ODLIS $\left(B,N=2909\right)$, and FOLDOC $\left(C,N=13356\right)$; university WWW networks: University of Wales (Cardiff) $\left(D,N=2778\right)$, Birmingham City University $\left(E,N=10631\right)$, Keele University (Staffordshire) $\left(F,N=11437\right)$, Nottingham Trent University $\left(G,N=12660\right)$, Liverpool John Moores University $\left(H,N=13578\right)$(data for universities are for 2002).

Figure 2

(Color online) Top: Roget dictionary, $\alpha =1$. Top panel: normalized density of states $W$ (red/gray) obtained as a derivative of a smoothed version of the integrated density (smoothed over a small interval $\Delta \gamma$ varying with matrix size), integrated density is shown in black. Bottom panel: PAR of eigenvectors as a function of $\gamma$; degeneracy of $\lambda =1$ is 18 (note that the value $W\left(0\right)$ corresponds to eigenvalues with $\left|\lambda \right|=1$). Bottom: ODLIS dictionary, same as top; degeneracy of $\lambda =1$ is 4.

Figure 3

(Color online) Top: FOLDOC dictionary, same as Fig. 2; degeneracy of $\lambda =1$ is 1; Bottom: University of Wales (Cardiff), same as top; degeneracy of $\lambda =1$ is 69.

Figure 4

(Color online) Top: Birmingham City University, same as Fig. 2; degeneracy of $\lambda =1$ is 71; Bottom: Keele University (Staffordshire), same as top; degeneracy of $\lambda =1$ is 205.

Figure 5

(Color online) Top: Nottingham Trent University, same as Fig. 2; degeneracy of $\lambda =1$ is 229. Bottom: Liverpool John Moores University, same as top; degeneracy of $\lambda =1$ is 109; other degeneracy peaks correspond to $\lambda =1/2$ (16), $\lambda =1/3$ (8); $\lambda =1/4$ (947), $\lambda =1/5$ (97), being located at $\gamma =-2\text{ln}\lambda$; other degeneracies are also present, e.g., $\lambda =1/\sqrt{2}$ (41).

Figure 6

(Color online) Cloud of eigenvalues for Liverpool John Moores University, $\alpha =1$. Circles: full matrix $N=13578$. Stars: truncated matrix of size 8192 (left) and 4096 (right).

Figure 7

(Color online) PAR $\xi$ of PageRank as a function of $\alpha$ for University of Wales (Cardiff) (black/dashed), Notre-Dame (blue, dotted), Liverpool John Moores University (red/long dashed), and Oxford (green/solid) Universities (curves from top to bottom at $\alpha =0.6$). Network sizes vary from $N=2778$ to $N=325729$. Inset is a zoom for data from Oxford University close to $\alpha =1$.

Figure 8

(Color online) Some PageRank vectors $p_j$ for Notre-Dame University (top panel) and Oxford (bottom panel). From top to bottom at ${\text{log}}_{10}\left(i\right)=5$: $\alpha =0.49$ (black), 0.59 (red), 0.69 (green), 0.79 (blue), 0.89 (violet), and 0.99 (orange). Dashed line indicates the slope $-1$.

Figure 9

(Color online) PageRank fidelity $f\left(\alpha ,{\alpha }^{\prime }\right)$ for Notre-Dame University $\left(N=325729\right)$; top panel: $f\left(\alpha ,{\alpha }^{\prime }=0.85\right)={\left|⟨\psi \left(\alpha \right)|\psi \left(0.85\right)⟩\right|}^2$ [see Eq. (2)]; bottom panel: color density plot of $f\left(\alpha ,{\alpha }^{\prime }\right)$.

Figure 10

Spectrum of eigenvalues $\lambda$ in the complex plane for the Avrachenkov-Lebedev model [6], with $N=2^{11}$ (network size), $\alpha =0.85$, $m=5$ outgoing links per node. Multiplicity of links is taken into account in the construction of $\mathbf{G}$.

Figure 11

Spectrum of eigenvalues $\lambda$ in the complex plane for the color model, $N=2^{13}$, $p=0.2$, $q=0.1$, and $\alpha =0.85$. Nodes are divided into $n$ color sets labeled from $i=0$ to $n-1$; nodes and links are created according to AB model; only authorized links are links within a color set $i$. This rule is broken with probability $ϵ={10}^{-3}$. We start with three color sets; with probability $\eta$ a new color is introduced (we take $\eta ={10}^{-2}$). In the example displayed, when the number of nodes reaches $N$, $n=83$ colors.

Figure 12

(Color online) Cumulative distribution of ingoing links $P_c^{in}\left(k\right)$ (top panel) and of outgoing links $P_c^{out}\left(k\right)$ (bottom panel) for the AB model with vector size $N=2^{14}$, for $q=0.1$ (black/solid) and $q=0.7$ (red/dashed), data are averaged over 80 realizations of AB model, and for the network of Liverpool John Moores University with $N=13578$, (panel H in Fig. 1) (blue/dotted). Average number of ingoing or outgoing links is $⟨k⟩=6.43$ for $q=0.1$, $⟨k⟩=14.98$ for $q=0.7$, $⟨k⟩=8.2227$ for LJMU. Dashed straight line indicates the slope $-1$. Logarithms are decimal.