Google matrix analysis of directed networks

In the past decade modern societies have developed enormous communication and social networks. Their classification and information retrieval processing has become a formidable task for the society. Because of the rapid growth of the World Wide Web, and social and communication networks, new mathematical methods have been invented to characterize the properties of these networks in a more detailed and precise way. Various search engines extensively use such methods. It is highly important to develop new tools to classify and rank a massive amount of network information in a way that is adapted to internal network structures and characteristics. This review describes the Google matrix analysis of directed complex networks demonstrating its efficiency using various examples including the World Wide Web, Wikipedia, software architectures, world trade, social and citation networks, brain neural networks, DNA sequences, and Ulam networks. The analytical and numerical matrix methods used in this analysis originate from the fields of Markov chains, quantum chaos, and random matrix theory.

Figure 1

Google matrix of the network Wikipedia English articles for August 2009 in the basis of the PageRank index $K$ (and $K^{\prime }$). Matrix $G_{K{K}^{\prime }}$ corresponds to the $x$ (and $y$) axis with (a) $1\le K,K^{\prime }\le 200$, and with (b) $1\le K,K^{\prime }\le N$; all nodes are ordered by the PageRank index $K$ of matrix $G$ and thus we have two matrix indices $K,K^{\prime }$ for matrix elements in this basis. (a) The first $200\times 200$ matrix elements of the $G$ matrix (see Sec. 3). (b) The density of all matrix elements coarse grained on $500\times 500$ cells where its elements $G_{K,K^{\prime }}$ are written in the PageRank basis $K(i)$ with indices $i\to K(i)$ (in the $x$ axis) and $j\to K^{\prime }(j)$ (in a usual matrix representation with $K=K^{\prime }=1$ on the top-left corner). The color shows the density of matrix elements changing from black for the minimum value [$(1-\alpha )/N$] to white for the maximum value via green (gray) and yellow (light gray); here the damping factor is $\alpha =0.85$. This and other color figures are available in open access arXiv preprint ([47]). From [45].

Figure 2

Distribution $w_{\text{in},\text{out}}(k)$ of the number of (a) ingoing and (b) outgoing links $k$ for $N=3282257$ Wikipedia English articles (August 2009) of Fig. 1 with the total number of links $N_{\ell }=71012307$. The straight dashed fit lines show the slopes with (a) ${\mu }_{\text{in}}=2.09\pm 0.04$ and (b) ${\mu }_{\text{out}}=2.76\pm 0.06$. From [154].

Figure 3

(a) Example of a simple network with directed links between five nodes. (b) Distribution of five nodes from (a) on the PageRank-CheiRank plane $(K,K^{*})$, where the size of a node is proportional to the PageRank probability $P(K)$ and the color of a node is proportional to the CheiRank probability $P^{*}(K^{*})$, with the maximum at gray (red) and the minimum at black (blue). The locations of the nodes of (a) on the $(K_i,{K_i}^{*})$ plane are (2,4), (1,3), (3,1), (4,2), and (5,5) for the original nodes $i=1,2,3,4$, and 5, respectively. PageRank and CheiRank vectors are computed from the Google matrices $G$ and $G^{*}$ shown in Fig. 4 at a damping factor $\alpha =0.85$.

Figure 4

(a) Adjacency matrix $A$ of the network of Fig. 3 with indices used there, (b) adjacency matrix $A^{*}$ for the network with inverted links; (c) matrices $S$ and (d) $S^{*}$ corresponding to the matrices $A$ and $A^{*}$; the Google matrices (e) $G$ and (f) $G^{*}$ corresponding to matrices $S$ and $S^{*}$ for $\alpha =0.85$ (only three digits of matrix elements are shown).

Figure 5

Dependence of probabilities of PageRank $P$ [gray (red) curves] and CheiRank $P^{*}$ [black (blue) curves] vectors on the corresponding rank indices $K$ and $K^{*}$ for networks of Wikipedia August 2009 (top curves) and University of Cambridge (bottom curves, moved down by a factor of 100). The straight dashed lines show the power law fits for PageRank and CheiRank with the slopes $\beta =0.92$ and 0.58, respectively, corresponding to $\beta =1/({\mu }_{\text{in},\text{out}}-1)$ for Wikipedia (see Fig. 2), and $\beta =0.75$ and 0.61 for Cambridge. From [154] and [60].

Figure 6

Correlator $\kappa$ as a function of the number of nodes $N$ for different networks: From [45], with additional data from [1], [42], [94], and [59].

Figure 7

Density distribution of network nodes $W(K,K^{*})=d{N}_i/dKd{K}^{*}$ shown on the plane of PageRank and CheiRank indices in log scale $({\log }_{N}K,{\log }_N{K}^{*})$ for all $1\le K,K^{*}\le N$, density is computed over equidistant grid in plane $({\log }_{N}K,{\log }_N{K}^{*})$ with $100\times 100$ cells; color shows the average value of $W$ in each cell, the normalization condition is $\sum _{K,K^{*}}W(K,K^{*})=1$. Density $W(K,K^{*})$ is shown by color with dark gray (blue) for the minimum in (a) and (b) and (a) white and (b) white (yellow) for the maximum (black for zero). (a) Data for Wikipedia August 2009, $N=3282257$ light gray/dark gray (green/red), points show the top 100 persons from PageRank and CheiRank white (yellow) pluses show the top 100 persons from [85]. From [154]. (b) Density distribution $W(K,K^{*})=d{N}_i/dKd{K}^{*}$ for the Linux Kernel V2.4 network with $N=85757$. From [45].

Figure 8

Illustration of the operation of the Ulam method: the phase space $(x,y)$ is divided in $N=N_x\times N_y$ cells, $N_c$ trajectories start from cell $j$ and the number of trajectories $N_{ij}$ arrived to a cell $i$ from a cell $j$ is collected after a map iteration. Then the matrix of Markov transitions is defined as $S_{ij}=N_{ij}/N_c$, by construction $\sum _{i=1}^N{S}_{ij}=1$.

Figure 9

Complex spectrum of eigenvalues ${\lambda }_j$, shown by gray (red) dots, for the UPFO of two variants of the Chirikov standard map (6); the unit circle $|\lambda |=1$ is shown by a light gray (green) curve, the unit eigenvalue at $\lambda =1$ is shown as a gray (larger red) dot. (a) The Chirikov standard map at dissipation $\eta =0.3$ and $K_s=7$; the phase space is covered by $110\times 110$ cells and the UPFO is constructed by many trajectories with random initial conditions generating transitions from one cell into another. From [49]. (b) The Chirikov standard map without dissipation at $K_s=0.971635406$ with an UPFO constructed from a single trajectory of length ${10}^{12}$ in the chaotic domain and $280\times 280/2$ cells to cover the phase space. From [62].

Figure 10

Density plots of absolute values of the eigenvectors of the UPFO obtained by the generalized Ulam method with a single trajectory of ${10}^{12}$ iterations of the Chirikov standard map at $K_s=0.971635406$. The phase space is shown in the area $0\le x\le 1$, $0\le y\le 1/2$; the UPFO is obtained from $M\times M/2$ cells placed in this area. (a) Eigenvector ${\psi }_0$ with eigenvalue ${\lambda }_0=1$; (b) eigenvector ${\psi }_2$ with real eigenvalue ${\lambda }_2=0.99878108$; (c) eigenvector ${\psi }_6$ with complex eigenvalue ${\lambda }_6=-0.49699831+i0.86089756\approx |{\lambda }_6|e^{i2\pi /3}$; (d) eigenvector ${\psi }_{13}$ with complex eigenvalue ${\lambda }_{13}=0.30580631+i0.94120900\approx |{\lambda }_{13}|e^{i2\pi /5}$. (a) Corresponding to $M=25$ while (b)–(d) have $M=800$. Color is proportional to the amplitude with black (blue) for zero and gray (red) for the maximal value. From [62].

Figure 11

Phase space representation of eigenstates of the UFPO $S$ for $N=110\times 110$ cells (color is proportional to absolute value $|{\psi }_i|$ with gray (red) for maximum and black (blue) for zero). (a) An eigenstate with maximum eigenvalue ${\lambda }_1=0.756$ of the UFPO of map (6) with absorption at $K_s=7$, $a=2$, $\eta =1$, the space region is ($-a{K}_s/4\pi \le y\le a{K}_s/4\pi$, $0\le x\le 1$), the fractal dimension of the strange repeller set nonescaping in the future is $d_e=1+d/2=1.769$. (b) An eigenstate at $\lambda =1$ of the UFPO of map (6) without absorption at $K_s=7$, $\eta =0.3$, the shown space region is ($-1/\pi \le y\le 1/\pi$, $0\le x\le 1$), and the fractal dimension of the strange attractor is $d=1.532$. From [49].

Figure 12

(a) The dependence of the integrated number of states $N_{\gamma }$ with decay rates $0\le \gamma \le {\gamma }_b=16$ on the size $N$ of the UFPO matrix $S$ for the map (6) at $K_s=7$. The fits of numerical data, shown by dashed straight lines, give $\nu =0.590,d_e=1+d/2=1.643$ (at $a=1$); $\nu =0.772,d_e=1+d/2=1.769$ (at $a=2$); $\nu =0.716,d=1.532$ (at $\eta =0.3$); $\nu =0.827,d=1.723$ (at $\eta =0.6$). (b) The fractal Weyl exponent $\nu$ as a function of fractal dimension $d$ of the invariant fractal set for the map (6) with a strange attractor $(\eta <1)$ at $K_s=15$ [gray (green) crosses], $K_s=12$ [gray (red) squares], $K_s=10$ [gray (orange) stars], and $K_s=7$ [black (blue) triangles]; for a strange repeller $(\eta =1)$ at $K_s=7$ (black points) and for a strange attractor for the Hénon map at standard parameters $a=1.2;1.4$, $b=0.3$ (green diamonds). The straight dashed line shows the fractal Weyl law dependence $\nu =d/2$. From [49].

Figure 13

PageRank probability $P_j$ for the Google matrix generated by the Chirikov typical map at $T=10$, $k_s=0.22$, and $\eta =0.99$ with (a) $\alpha =1$, (b) $\alpha =0.95$, and (c) $\alpha =0.85$. The probability $P_j$ is shown in the phase space region $0\le x<2\pi ;-\pi \le y<\pi$ which is divided in $N=3.6\times {10}^5$ cells; $P_j$ is zero for black (blue) and maximal for gray (red). From [134].

Figure 14

Dependence of PageRank probability $P_j$ on PageRank index $j$ for number of cells in the UFPO being $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) and (c)]. (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); for the online version we note that the above order of $N$ values corresponds to red, magenta, green, and blue curves, respectively. The dashed line in (a) shows an exponential Boltzmann decay (see text, the line is shifted in $j$ for clarity). The dashed straight line in (b) shows the fit $P_j\sim 1/j^{\beta }$ with $\beta =0.48$. Other parameters, including the values of $\alpha$, and panel order are as in Fig. 13. From [134].

Figure 15

The diagram in the center represents the PCN of a toy kernel with two procedures written in the C-programming language. The data in (a) and (b) show outdegree and indegree probability distributions $P_{\text{out}}(\overline{k})$ and $P_{\text{in}}(k)$, respectively. The colors correspond to different Kernel releases. The most recent version 2.6.32, with $N=285509$ and an average of 3.18 calls per procedure, is represented in gray (red). Older versions (2.4.37.6, 2.2.26, 2.0.40, 1.2.12, and 1.0) with $N$ respectively equal to (85 756, 38 766, 14 079, 4358, and 2751) follow the same behavior. The dashed curve in (a) shows the outdegree probability distribution if only calls to distinct destination procedures are kept. From [28].

Figure 16

(a) Distribution of eigenvalues $\lambda$ in the complex plane for the Google matrix $G$ of the Linux Kernel version 2.6.32 with $N=285509$ and $\alpha =0.85$; the solid curves represent the unit circle and the lowest limit of computed eigenvalues. (b) The dependence of the integrated number of eigenvalues $N_{\lambda }$ with $|\lambda |>0.25$ [gray (red) squares] and $|\lambda |>0.1$ (black circles) as a function of the total number of processes $N$ for versions of Linux Kernels. The values of $N$ correspond (in increasing order) to Linux Kernel versions 1.0, 1.1, 1.2, 1.3, 2.0, 2.1, 2.2, 2.3, 2.4, and 2.6. The power law $N_{\lambda }\propto N^{\nu }$ has fitted values ${\nu }_{|\lambda |>0.25}=0.622\pm 0.010$ and ${\nu }_{|\lambda |>0.1}=0.630\pm 0.015$. The inset shows data for the Google matrix $G^{*}$ with inverse link directions; the corresponding exponents are ${\nu }_{|\lambda |>0.25}^{*}=0.696\pm 0.010$ and ${\nu }_{|\lambda |>0.1}^{*}=0.652\pm 0.007$. From [44].

Figure 17

(a), (b) The complex eigenvalue spectrum $\lambda$ of matrix $S$ for the University of Cambridge 2006 and Oxford 2006, respectively. (c), (d) The spectrum $\lambda$ of matrix $S^{*}$ for Cambridge 2006 and Oxford 2006. Eigenvalues $\lambda$ of the core space are shown by gray (red) points, eigenvalues of isolated subspaces are shown by black (blue) points, and the gray (green) curve (when shown) is the unit circle. (e), (f) The fraction $j/N$ of eigenvalues with $|\lambda |>|{\lambda }_j|$ for the core space eigenvalues [gray (red) bottom curve] and all eigenvalues [black (blue) top curve] from top row data for Cambridge 2006 and Oxford 2006. From [60].

Figure 18

Spectra $\lambda$ of 800 random orthostochastic matrices of size (a) $N=3$ and (b) $N=4$ ($\mathrm{Re}\lambda =x,\mathrm{Im}\lambda =y$). Thin lines denote 3- and 4-hypocycloids, while the thick lines represent the 3-4 interpolation arc. From [160].

Figure 19

(a) PageRank $P(K)$ of Cambridge 2006 for $1-\alpha =0.1$, ${10}^{-3}$, ${10}^{-5}$, and ${10}^{-7}$. (b) First core space eigenvector ${\psi }_1^{(\text{core})}$ vs its rank index $K^{(\text{core})}$ for the UK university networks with a small core space gap $1-{\lambda }_1^{(\text{core})}<{10}^{-8}$. From [60].

Figure 20

(a) Fraction of invariant subspaces $F$ with dimensions larger than $d$ as a function of the rescaled variable $x=d/⟨d⟩$. Upper curves correspond to Cambridge (gray/green) and Oxford (black/blue) for years 2002 to 2006 and middle curves (shifted down by a factor of 10) correspond to the university networks of Glasgow, Cambridge, Oxford, Edinburgh, UCL, Manchester, Leeds, Bristol, and Birkbeck for year 2006 with $⟨d⟩$ between 14 and 31. Lower curve (shifted down by a factor of 100) corresponds to the matrix $S^{*}$ of Wikipedia with $⟨d⟩=4$. The thick black line is $F(x)=(1+2x{)}^{-1.5}$. (b) Rescaled PageRank $P{N}_s$ vs rescaled rank index $K/N_s$ for $1-\alpha ={10}^{-8}$ and $3974\le N_s\le 48239$ for the same university networks as in (a) (upper and middle curves, the latter shifted down and left by a factor of 10). The lower curve (shifted down and left by a factor of 100) shows the rescaled CheiRank of Wikipedia $P^{*}{N}_s$ vs $K^{*}/N_s$ with $N_s=21198$. The thick black line corresponds to a power law with exponent $-2/3$. From [60].

Figure 21

Density distribution $W(K,K^{*})=d{N}_i/dKd{K}^{*}$ for networks of universities in the plane of PageRank $K$ and CheiRank $K^{*}$ indices on a log scale $({\log }_{N}K,{\log }_N{K}^{*})$. The density is shown for a $100\times 100$ equidistant grid in ${\log }_{N}K,{\log }_N{K}^{*}\in [0,1]$, the density is averaged over all nodes inside each cell of the grid, and the normalization condition is $\sum _{K,K^{*}}W(K,K^{*})=1$. Color varies from black for zero to gray (yellow) for maximum density value $W_M$ with a saturation value of $W_s^{1/4}=0.5W_M^{1/4}$ so that the same color is fixed for $0.5W_M^{1/4}\le W^{1/4}\le W_M^{1/4}$ to show in a better way low densities. Networks of the University of Cambridge 2006 with (a) $N=212710$ and ENS Paris 2011 for crawling level 7 with (b) $N=1820015$. From [45].

Figure 22

Complex eigenvalue spectra $\lambda$ of (a) $S$ and (b) $S^{*}$ for the English Wikipedia of August 2009 with $N=3282257$ articles and $N_{\ell }=71012307$ links. The gray (red) dots are the core space eigenvalues, the black (blue) dots are the subspace eigenvalues, and the solid gray (green) curves show the unit circles. The core space eigenvalues are computed by the projected Arnoldi method with Arnoldi dimension $n_A=6000$. From [41].

Figure 23

Complex eigenvalue spectrum of the matrices $S$ for the English Wikipedia August 2009. Highlighted eigenvalues represent different communities of Wikipedia and are labeled by the most repeated and important words following word counting of the first 1000 nodes. (a) A complex plane for positive imaginary part of eigenvalues, while (b) and (c) zoom in on the negative and positive real parts. From [46].

Figure 24

Density of the Wikipedia articles in the PageRank-CheiRank plane $(K,K^{*})$ for four different language Wikipedia editions. The gray (red) points are top PageRank articles of persons, the light gray (green) squares are top 2DRank articles of persons, and the dark gray (cyan) triangles are top CheiRank articles of persons. Wikipedia language editions are (a) English EN, (b) French FR, (c) German DE, and (d) Russian RU. Color bars show a natural logarithm of density, changing from minimal nonzero density (dark) to maximal one (white), and zero density is shown by black. From [42].

Figure 25

Distribution of the top 30 persons over activity fields for (a) PageRank and (b) 2DRank for each of nine Wikipedia editions. The color bars show the values in percent. From [42].

Figure 26

The number of appearances of historical figures of a given country, obtained from 24 lists of the top 100 persons of (a) PageRank and (b) 2DRank, shown on the world map. Color changes from zero (white) to maximum (black), corresponding to the average number of person appearances per country. From [40].

Figure 27

Birth date distributions over 35 centuries of the top historical figures from each Wikipedia edition marked by the two letter standard notation of Wikipedia. (a) Column normalized birth date distributions of PageRank historical figures; (b) the same as (a) for 2DRank historical figures. From [40].

Figure 28

Network of cultures, obtained from 24 Wikipedia languages and the remaining world (WR), considering (a) the top 100 PageRank historical figures and (b) the top 100 2DRank historical figures. The link width and darkness are proportional to a number of foreign historical figures quoted in the top 100 of a given culture, the link direction goes from a given culture to cultures of quoted foreign historical figures, and quotations inside cultures are not considered. The size of nodes is proportional to their PageRank. From [40].

Figure 29

A Google matrix of the network of cultures shown in Fig. 28 and 28, respectively. The matrix elements $G_{ij}$ are shown by color with the damping factor $\alpha =0.85$. From [40].

Figure 30

PageRank-CheiRank plane of cultures with corresponding indices $K$ and $K^{*}$ obtained from the network of cultures based on (a) the top 100 PageRank historical figures, and (b) the top 100 2DRank historical figures. From [40].

Figure 31

(a) Google matrix of Twitter; matrix elements of $G$ are shown in the basis of PageRank index $K$ of matrix $G_{K{K}^{\prime }}$. Here the $x$ (and $y$) axis show $K$ (and $K^{\prime }$) with the range $1\le K,K^{\prime }\le 200$. (b) The density of nodes $W(K,K^{*})$ of Twitter on the PageRank-CheiRank plane $(K,K^{*})$, averaged over $100\times 100$ logarithmically equidistant grids for $0\le \ln K,\ln K^{*}\le \ln N$ with the normalization condition $\sum _{K,K^{*}}W(K,K^{*})=1$. The $x$ axis corresponds to $\ln K$ and the $y$ axis to $\ln K^{*}$. In both panels the color varies from black (blue) at the minimal value to gray (red) at the maximal value; here $\alpha =0.85$. From [63].

Figure 32

(a) Dependence of the area density $g_K=N_G/K^2$ of nonzero elements of the adjacency matrix among top PageRank nodes on the PageRank index $K$ for Twitter [black (blue curve] and Wikipedia [gray (red) curve] networks; data are shown in linear scale. (b) Linear density $N_G/K$ of the same matrix elements shown for the whole range of $K$ in log-log scale for Twitter (blue curve), Wikipedia (red curve), Oxford University 2006 (magenta curve), and Cambridge University 2006 (green curve) (curves from top to bottom at $K=100$). From [63].

Figure 33

Spectrum of the Twitter matrix (a), (c) $S$, and (b), (d) $S^{*}$. (a), (b) Subspace eigenvalues [black (blue) dots] and core space eigenvalues [gray (red) dots] in the $\lambda$ plane [the gray (green) curve shows the unit circle); there are 17 504 (66 316) invariant subspaces, with maximal dimension 44 (2959) and the sum of all subspace dimensions is $N_s=40307$ (180 414). The core space eigenvalues are obtained from the Arnoldi method applied to the core space sub-block $S_{cc}$ of $S$ with Arnoldi dimension $n_A=640$. (c), (d) The fraction $j/N$ of eigenvalues with $|\lambda |>|{\lambda }_j|$ for the core space eigenvalues [gray (red) bottom curve] and all eigenvalues [black (blue) top curve] from raw data [(a), (b), respectively]. The number of eigenvalues with $|{\lambda }_j|=1$ is 34 135 (129 185) of which 17 505 (66 357) are at ${\lambda }_j=1$; this number is (slightly) larger than the number of invariant subspaces which have each at least one unit eigenvalue. Note that in (c) and (d) the number of eigenvalues with $|{\lambda }_j|=1$ is artificially reduced to 200 in order to have a better scale on the vertical axis. The correct numbers of those eigenvalues correspond to (c) $j/N=8.195\times {10}^{-4}$ and (d) $3.102\times {10}^{-3}$ which are strongly outside the vertical panel scale. From [63].

Figure 34

(a) The dependence of certain top PageRank levels $E_i=-\ln (P_i)$ on the damping factor $\alpha$ for the Twitter network. Data points on curves with one color correspond to the same node $i$; about 150 levels are shown close to the minimal energy $E\approx 7.5$. (b) The histogram of unfolded level-spacing statistics for Twitter at $10<K\le {10}^4$. The Poisson distribution $p_{\text{Pois}}(s)=\exp (-s)$ and the Wigner surmise $p_{\text{Wig}}(s)=(\pi /2)s\exp [-(\pi /4)s^2]$ are also shown for comparison. From [66].

Figure 35

Country positions in the PageRank-CheiRank plane $(K,K^{*})$ for world trade in various commodities in 2008. Each country is shown by a circle with its own flag [for better visibility the circle center is slightly displaced from its integer position $(K,K^{*})$ along the direction angle $\pi /4$]. The panels show the ranking for trade in the following commodities: (a), (b) all commodities, and (c), (d) crude petroleum. (a), (c) A global scale with all 227 countries, while (b) and (d) give a zoom in the region of the $40\times 40$ top ranks. From [50].

Figure 36

Spindle distribution for the WTN of all commodities for all countries in the period 1962–2009 shown in the plane of $\mathbf{(}(K^{*}-K)/N,(K^{*}+K)/N\mathbf{)}$ (coarse graining inside each of the $76\times 152$ cells); data from the UN COMTRADE database. From [50].

Figure 37

Time evolution of CheiRank and PageRank indices $K$, $K^{*}$ for some selected countries for all commodities. The countries shown are (a), (b) Japan (jp, black), France (fr, red), Federal Republic of Germany and Germany (de, both blue), Great Britain (gb, green), USA (us, orange) [curves from top to bottom in 1962 in (a)]. The countries shown are (c), (d) Argentina (ar, violet), India (in, dark green), China (cn, cyan), USSR and Russian Federation (ru, both gray) [curves from top to bottom in 1975 in (c)]. From [50].

Figure 38

Nestedness matrices for the plant-animal mutualistic networks in the top panels, and for the WTN of countries and products in the middle and bottom panels. (a), (b)  Data of ARR1 and WES networks. From [125]. The WTN matrices are computed with the threshold $\mu ={10}^{-3}$ and corresponding $\phi \approx 0.2$ for years (c), (d) 2008 and (e), (f) 1968 and 2008 for (c), (e) import and (d), (f) export. Gray (red) and black (blue) represent unit and zero elements, respectively; only lines and columns with nonzero elements are shown. The order of plants and animals, countries and products is given by the nestedness algorithm ([126]); the perfect nestedness is shown by gray (green) curves for the corresponding values of $\phi$. From [52].

Figure 39

Top 20 EcoloRank countries as a function of the years for the WTN (a) import and (b) export panels. The ranking is given by the nestedness algorithm for the trade threshold $\mu ={10}^{-3}$; each country is represented by its corresponding flag. As an example, dashed lines show a time evolution of the following countries: USA, UK, Japan, China, and Spain. From [52].

Figure 40

The top 20 countries as a function of years ranked by the total monetary trade volume of the WTN in (a) import and (b) export, respectively; each country is represented by its corresponding flag. Dashed lines show time evolution of the same countries as in Fig. 39. From [52].

Figure 41

The top 10 ranks of trade products as a function of years for the WTN. (a) Ranking of products by monetary trade volume. (b), (c) Ranking is given by the nestedness algorithm for (b) import and (c) export with the trade threshold $\mu ={10}^{-3}$. Each product is shown by its own symbol with a short name written at years 1968 and 2008; the symbol color marks the first SITC digit. The SITC codes of products and their names are given in the [147] and Table 2 of [52]. From [52].

Figure 42

(a) The Google matrix of integers. The amplitudes of matrix elements $S_{mn}$ are shown by color black (blue) for minimal zero elements and gray (red) maximal unity elements, with $1\le n\le 31$ corresponding to the $x$ axis (with $n=1$ corresponding to the left column) and $1\le m\le 31$ for the $y$ axis (with $m=1$ corresponding to the upper row). (b) The full lines correspond to the dependence of the PageRank probability $P(K)$ on index $K$ for the matrix sizes $N={10}^7$, ${10}^8$, and ${10}^9$ with the PageRank evaluated by the exact expression $P\propto \sum _{j=0}^{l-1}{v}^{(j)}$. The gray (green) crosses correspond to the PageRank obtained by the power method for $N={10}^7$; the dashed straight line shows the Zipf law dependence $P\sim 1/K$. From [58].

Figure 43

(a) Comparison of the first three PageRank approximations $P^{(i)}\propto \sum _{j=0}^{i-1}{v}^{(j)}$ for $i=1,2,3$ and the exact PageRank dependence $P(K)$. (b) Comparison of the dependence of the rescaled probabilities $nP$ and $n{P}^{(3)}$ on $n$. Both panels correspond to the case $N={10}^7$. From [58].

Figure 44

Different representations of the Google matrix structure for the Physical Review network until 2009. (a) Density of matrix elements $G_{t{t}^{\prime }}$ in the basis of the publication time index $t$ (and $t^{\prime }$). (b) Density of matrix elements in the basis of journal ordering according to Phys. Rev. Series I, Phys. Rev., Phys. Rev. Lett., Rev. Mod. Phys., Phys. Rev. A, B, C, D, E, Phys. Rev. STAB, Phys. Rev. STPER, and with time index ordering inside each journal. Note that the journals Phys. Rev. Series I, Phys. Rev. STAB, and Phys. Rev. STPER are not clearly visible due to a small number of published papers. Also Rev. Mod. Phys. appears only as a thick line with 2–3 pixels (out of 500) due to a limited number of published papers. The different blocks with triangular structure correspond to clearly visible seven journals with considerable numbers of published papers. Both panels show the coarse-grained density of matrix elements on $500\times 500$ square cells for the entire network. Color shows the density of matrix elements (of $G$ at $\alpha =1$) changing from black (blue) for minimum zero value to gray (red) maximum value. From [59].

Figure 45

(a) Most accurate spectrum of eigenvalues for the full Physical Review network; the gray (red) dots represent the core space eigenvalues obtained by the rational interpolation method with the numerical precision of $p=16384$ binary digits, $n_R=2500$ eigenvalues; light gray (green) dots show the degenerate subspace eigenvalues of the matrix $S_0$ which are also eigenvalues of $S$ with a degeneracy reduced by one (eigenvalues of the first group); black (blue) dots show the direct subspace eigenvalues of $S$. (b) Spectrum of numerically accurate 352 nonvanishing eigenvalues of the Google matrix for the triangular reduced Physical Review network determined by the Newton-Maehly method applied to the reduced polynomial (11) with a high-precision calculation of 256 binary digits; note the absence of subspace eigenvalues for this case. In both panels the gray (green) curves represent the unit circles. From [59].

Figure 46

Data for the whole citation network of Physical Review at different moments of time. (a) [or (c)] The number $N_{\lambda }$ of eigenvalues with ${\lambda }_c\le \lambda \le 1$ for ${\lambda }_c=0.50$ (or ${\lambda }_c=0.65$) vs the effective network size $N_t$, where the nodes with publication times after a cut time $t$ are removed from the network. The gray (green) line shows the fractal Weyl law $N_{\lambda }=a(N_t{)}^{\nu }$ with parameters $a=0.32\pm 0.08$ ($a=0.24\pm 0.11$) and $\nu =0.51\pm 0.02$ ($b=0.47\pm 0.04$) obtained from a fit in the range $3\times {10}^4\le N_t<5\times {10}^5$. The number $N_{\lambda }$ includes both exactly determined invariant subspace eigenvalues and core space eigenvalues obtained from the Arnoldi method with double precision (52 binary digits) for $n_A=4000$ [gray (red) crosses] and $n_A=2000$ [black (blue) squares]. (b) Exponent $b$ with error bars obtained from the fit $N_{\lambda }=a(N_t{)}^{\nu }$ in the range $3\times {10}^4\le N_t<5\times {10}^5$ vs the cut value ${\lambda }_c$. (d) The effective network size $N_t$ vs cut time $t$ (in years). The gray (green) line shows the exponential fit $2^{(t-t_0)/\tau }$ with $t_0=1791\pm 3$ and $\tau =11.4\pm 0.2$ representing the number of years after which the size of the network (number of papers published in all Physical Review journals) is effectively doubled. From [59].

Figure 47

(a) The spectrum [gray (red) dots] of one realization of a full uniform RPFM with dimension $N=400$ and matrix elements uniformly distributed in the interval $[0,2/N]$; the black (blue) outer circle represents the theoretical spectral border with radius $R=1/\sqrt{3N}\approx 0.02887$. The unit eigenvalue $\lambda =1$ is not shown due to the zoomed presentation range. (c) The spectrum of one realization of triangular RPFM [gray (red) crosses] with nonvanishing matrix elements uniformly distributed in the interval $[0,2/(j-1)]$ and a triangular matrix with nonvanishing elements $1/(j-1)$ [black (blue) squares]; here $j=2,3,\dots ,N$ is the index number of nonempty columns and the first column with $j=1$ corresponds to a dangling node with elements $1/N$ for both triangular cases. (b), (d) The complex eigenvalue spectrum [gray (red) dots] of a sparse RPFM with dimension $N=400$ and $Q=20$ nonvanishing elements per column at random positions. (b) [or (d)] corresponds to the case of uniformly distributed nonvanishing elements in the interval $[0,2/Q]$ (constant nonvanishing elements being $1/Q$); the black (blue) small circle represents the theoretical spectral border with radius $R=2/\sqrt{3Q}\approx 0.2582$ ($R=1/\sqrt{Q}\approx 0.2236$). (b), (d) $\lambda =1$ is shown by a larger red dot for better visibility. The unit circle is shown by the gray (green) curve [(b)–(d)]. From [59].

Figure 48

(a) The gray (red) and black (blue) curves represent the Poisson and Wigner surmise distributions. Diamonds, triangles, open circles, and black solid circles represent, respectively, the level-spacing statistics $p(s)$ at $W/V=4,3,2,1$; $p_{\ell }=0.02$, $L=32000$; averaging is done over 60 network realizations. (b) Stars give dependence of $p_{\ell }$ on a disorder strength $W/V$ at the critical point when ${\eta }_{\ell }(W,p_{\ell })=0.8$, and $p_{\ell }=0.005,0.01,0.02,0.04$ at fixed $L=8000$; the straight line corresponds to $p_{\ell }=p_c=1/4{\ell }_1\approx (W/V{)}^2/400$; the dashed curve is to guide the eye. From [29].

Figure 49

(a) Spectrum of eigenvalues $\lambda$ for the Google matrices $G$ and $G^{*}$ at $\alpha =0.85$ for the neural network of C. elegans [black and gray (red) symbols]. (b) Values of IPR ${\xi }_i$ of eigenvectors ${\psi }_i$ are shown as a function of corresponding $\mathrm{Re}\lambda$ (the same colors). From [94].

Figure 50

The PageRank-CheiRank plane $(K,K^{*})$ showing distribution of neurons according to their ranking. (a) Soma region coloration—head (gray/red), middle (light gray/green), and tail (dark gray/blue). (b) Neuron-type coloration—sensory (gray/red), motor (light gray/green), interneuron (dark gray/blue), polymodal (light-dark gray/purple), and unknown (black). The classifications and colors are given according to he WormAtlas ([6]). From [94].

Figure 51

DNA Google matrix of Homo sapiens (HS) constructed for words of six-letters length. Matrix elements $G_{K{K}^{\prime }}$ are shown in the basis of the PageRank index $K$ (and $K^{\prime }$). Here $x$ and $y$ axes show $K$ and $K^{\prime }$ within the ranges (a) $1\le K,K^{\prime }\le 200$ and (b) $1\le K,K^{\prime }\le 1000$. The element $G_{11}$ at $K=K^{\prime }=1$ is placed at the top-left corner. Color marks the amplitude of matrix elements changing from black (blue) for the minimum zero value to gray (red) at the maximum value. From [93].

Figure 52

Integrated fraction $N_g/N^2$ of Google matrix elements with $G_{ij}>g$ as a function of $g$. (a) Various species with six-letters word length: elephant LA (green), zebrafish DR (black), dog CF (red), bull BT (magenta), and Homo sapiens HS (blue) (from left to right at $y=-5.5$). (b) Data for HS sequence with words of length $m=5$ (brown), 6 (blue), 7 (red) (from right to left at $y=-2$); for comparison black dashed and dotted curves show the same distribution for the WWW networks of Universities of Cambridge and Oxford in 2006, respectively. From [93].

Figure 53

Integrated fraction $N_s/N$ of the sum of ingoing matrix elements with $\sum _{j=1}^N{G}_{i,j}\ge g_s$. (a), (b) The same cases as in Fig. 52 in the same colors. The dashed and dotted curves are shifted on the $x$ axis by one unit left to fit the figure scale. From [93].

Figure 54

Dependence of the PageRank probability $P(K)$ on the PageRank index $K$. (a) Data for different species for word length of six letters: zebrafish DR (black), dog CF (red), Homo sapiens HS (blue), elephant LA (green), and bull BT (magenta) (from top to bottom at $x=1$). (b) Data for HS (full curve) and LA (dashed curve) for word length $m=5$ (brown), 6 (blue/green), and 7 (red) (from top to bottom at $x=1$). From [93].

Figure 55

PageRank proximity $K-K$ plane diagrams for different species in comparison with Homo sapiens: (a) the $x$ axis shows PageRank index $K_{hs}(i)$ of a word $i$ and the $y$ axis shows the PageRank index of the same word $i$ with $K_{bt}(i)$ of bull, (b) $K_{cf}(i)$ of dog, (c) $K_{la}(i)$ of elephant, and (d) $K_{dr}(i)$ of zebrafish; here the word length is $m=6$. The colors of the symbols mark the purine content in a word $i$ (fractions of letters $A$ or $G$ in any order); the color varies from gray (red) at maximal content, via brown, yellow, green, and light blue, to black (blue) at minimal zero content. From [93].

Figure 56

Distribution of nodes in the PageRank-CheiRank plane $(K,K^{*})$ for (a) Escherichia Coli v1.1 and (b) yeast gene transcription networks [network data are taken from [112], [130], and 5]. The nodes with the top five probability values of PageRank, CheiRank, and 2DRank are labeled by their corresponding operon (node) names; they correspond to the five lowest values of indices $K,K_2,K^{*}$. From [45].

Figure 57

Density plot of probability $W_f$ to find a final red fraction $f_f$, shown on the $y$ axis, in dependence on an initial red fraction $f_i$, shown on the $x$ axis; data are shown inside the unit square $0\le f_i,f_f\le 1$. The values of $W_f$ are defined as a relative number of realizations found inside each of $20\times 20$ cells which cover the whole unit square. Here $N_r={10}^4$ realizations of randomly distributed colors are used to obtained $W_f$ values; for each realization the time evolution is followed up the convergence time with up to $t=20$ iterations.; (a) Cambridge network and (b) Oxford network at $a=0.1$. The probability $W_f$ is proportional to color changing from zero (black/blue) to unity (gray/red). From [92].

Figure 58

The PROF-Sznajd model, option 1: density plot of probability $W_f$ to find a final red fraction $f_f$, shown on the $y$ axis, in dependence on an initial red fraction $f_i$, shown on the $x$ axis; data are shown inside the unit square $0\le f_i,f_f\le 1$. The values of $W_f$ are defined as a relative number of realizations found inside each of $100\times 100$ cells which cover the whole unit square. Here $N_r={10}^4$ realizations of randomly distributed colors are used to obtain $W_f$ values; for each realization the time evolution follows the convergence time with up to $\tau ={10}^7$ steps. (a) Cambridge network, (b) Oxford network; here $N_g=8$. The probability $W_f$ is proportional to color changing from zero (black/blue) to unity (gray/red). From [92].