Google matrix of the citation network of Physical Review

Klaus M. Frahm, Young-Ho Eom, and Dima L. Shepelyansky

Phys. Rev. E 89, 052814 – Published 28 May 2014

Abstract

We study the statistical properties of spectrum and eigenstates of the Google matrix of the citation network of Physical Review for the period 1893–2009. The main fraction of complex eigenvalues with largest modulus is determined numerically by different methods based on high-precision computations with up to $p = 16 384$ binary digits that allow us to resolve hard numerical problems for small eigenvalues. The nearly nilpotent matrix structure allows us to obtain a semianalytical computation of eigenvalues. We find that the spectrum is characterized by the fractal Weyl law with a fractal dimension $d_{f} \approx 1$ . It is found that the majority of eigenvectors are located in a localized phase. The statistical distribution of articles in the PageRank-CheiRank plane is established providing a better understanding of information flows on the network. The concept of ImpactRank is proposed to determine an influence domain of a given article. We also discuss the properties of random matrix models of Perron-Frobenius operators.

10 More

Received 21 October 2013

DOI:https://doi.org/10.1103/PhysRevE.89.052814

Authors & Affiliations

Klaus M. Frahm, Young-Ho Eom, and Dima L. Shepelyansky

Laboratoire de Physique Théorique du CNRS, IRSAMC, Université de Toulouse, UPS, 31062 Toulouse, France

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 89, Iss. 5 — May 2014

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Different order representations of the Google matrix of the CNPR ( $α = 1$ ). The left panels show (a) the density of matrix elements $G_{t t^{'}}$ in the basis of the publication time index $t$ (and $t^{'}$ ); (b) the 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, and Phys. Rev. STPER with time ordering inside each journal; (c) the same as (b) but with PageRank 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 thin line with 2–3 pixels (out of 500) due to a limited number of published papers. The panels (a), (b), (c), and (f) show the coarse-grained density of matrix elements done on $500 \times 500$ square cells for the entire network. In panels (d), (e), and (f) the matrix elements $G_{K K^{'}}$ are shown in the basis of PageRank index $K$ (and $K^{'}$ ) with the range $1 \leq K, K^{'} \leq 200$ (d); $1 \leq K, K^{'} \leq 400$ (e); $1 \leq K, K^{'} \leq N$ (f). Color shows the amplitude (or density) of matrix elements $G$ changing from blue/black for zero value to red/gray at maximum value. The PageRank index $K$ is determined from the PageRank vector at $α = 0.85$ .
Reuse & Permissions
Figure 2
(a) Dependence of the linear density $N_{G} / K$ of nonzero elements of the adjacency matrix among top PageRank nodes on the PageRank index $K$ for the networks of Twitter (top blue/black curve), Wikipedia (second from top red/gray curve), Oxford University 2006 (magenta/gray boxes), and Cambridge University 2006 (green/gray crosses), with data taken from Ref. [12], and Physical Review all journals (cyan/gray circles) and Physical Review without Rep. Mod. Phys. (bottom black curve). (b) Dependence of the quantity $Σ / K$ on the PageRank index $K$ with $Σ = \sum_{K_{1} < K, K_{2} < K} G_{K_{1}, K_{2}}$ being the weight of the Google matrix elements inside the $K \times K$ square of top PageRank indexes. The curves correspond to the same networks as in (a): Physical Review without Rep. Mod. Phys. (top black curve), Physical Review all journals (cyan/gray circles), Oxford University 2006 (magenta/gray boxes), Cambridge University 2006 (green/gray crosses), Wikipedia (second bottom red/gray curve), and Twitter (bottom blue/black curve).
Reuse & Permissions
Figure 3
Spectrum of $S$ for CNPR (reduced CNPR without Rev. Mod. Phys.) shown on left panels (right panels). (a, c) Subspace eigenvalues (blue/black dots) and core space eigenvalues (red/gray dots) in the $λ$ plane (green/gray curve shows unit circle); there are 27 (26) invariant subspaces, with maximal dimension 6 (6), and the sum of all subspace dimensions is $N_{s} = 71$ (75). The core space eigenvalues are obtained from the Arnoldi method applied to the core space subblock $S_{c c}$ of $S$ with Arnoldi dimension $n_{A} = 8000$ as explained in Ref. [10] and using standard double-precision arithmetic. (b, d) Fraction $j / N$ of eigenvalues, shown in a logarithmic scale, with $| λ | > | λ_{j} |$ for the core space eigenvalues (red/gray bottom curve) and all eigenvalues (blue/black top curve) from raw data of top panels. The number of eigenvalues with $| λ_{j} | = 1$ is 45 (43) of which 27 (26) are at $λ_{j} = 1$ ; this number is identical to the number of invariant subspaces which have each one unit eigenvalue.
Reuse & Permissions
Figure 4
Number of occupied nodes $N_{i}$ (i.e., positive elements) in the vector $S_{0}^{i} e$ versus iteration number $i$ (red/gray crosses) for the CNPR (a) and the triangular CNPR (b). In both cases the initial value is the network size $N_{0} = N = 463 348$ . For the CNPR $N_{i}$ saturates at $N_{i} = N_{sat} = 273 490 \approx 0.590 N$ for $i \geq 27$ while for the triangular CNPR $N_{i}$ saturates at $N_{i} = 0$ for $i \geq 352$ confirming the nilpotent structure of $S_{0}$ . In (a) the quantity $N_{i} - N_{sat}$ is shown in order to increase visibility in the logarithmic scale.
Reuse & Permissions
Figure 5
(a) Comparison of the core space eigenvalue spectrum of $S$ for CNPR (blue/black squares) and triangular CNPR (red/gray crosses). Both spectra are calculated by the Arnoldi method with $n_{A} = 4000$ and standard double precision. (b) Comparison of the numerically determined nonvanishing 352 eigenvalues obtained from the representation matrix (A8) (blue/black squares) with the spectrum of triangular CNPR (red/gray crosses) already shown in the left panel. Numerics is done with standard double precision.
Reuse & Permissions
Figure 6
Comparison of the numerically accurate 352 nonvanishing eigenvalues of $S$ matrix of triangular CNPR, determined by the Newton-Maehly method applied to the reduced polynomial (A4) with a high-precision calculation of 256 binary digits (red/gray crosses, all panels), with eigenvalues obtained by the Arnoldi method at different numerical precisions (for the determination of the Arnoldi matrix) for triangular CNPR and Arnoldi dimension $n_{A} = 352$ (blue/black squares, all panels). The first row corresponds to the numerical precision of 52 binary digits for standard double-precision arithmetic. The second (third, fourth) row corresponds to the precision of 256 (512, 1280) binary digits. All high-precision calculations are done with the library GMP [30]. The panels in the left column show the complete spectra and the panels in the right columns show the spectra in a zoomed range: $- 0.4 \leq Re (λ), Im (λ) \leq < 0.4$ for the first row or $- 0.2 \leq Re (λ), Im (λ) \leq 0.2$ for the second, third, and fourth rows.
Reuse & Permissions
Figure 7
Comparison of the core space eigenvalue spectrum of $S$ of CNPR, obtained by the high-precision Arnoldi method using 768 binary digits (blue/black squares, all panels), with lower-precision data of the Arnoldi method (red/gray crosses). In both top panels the red/gray crosses correspond to double precision with 52 binary digits [extended range in (a) and zoomed range in (c)]. In the bottom (b) [or (d))] panel red/gray crosses correspond to the numerical precision of 256 (or 512) binary digits. In these two cases only a zoomed range is shown. The eigenvalues outside the zoomed ranges coincide for both data sets up to graphical precision. In all cases the Arnoldi dimension is $n_{A} = 2000$ . High-precision calculations are done with the library GMP [30].
Reuse & Permissions
Figure 8
Modulus $| λ_{j} |$ of the core space eigenvalues of $S$ of CNPR, obtained by the Arnoldi method, shown versus level number $j$ . (a) Data for standard double precision with 52 binary digits with different Arnoldi dimensions $1000 \leq n_{A} \leq 8000$ . (b) Data for Arnoldi dimension $n_{A} = 2000$ with different numerical precisions between 52 and 768 binary digits.
Reuse & Permissions
Figure 9
(a) Comparison of $n_{R} = 340$ core space eigenvalues of $S$ for CNPR obtained by two variants of the rational interpolation method (see text) with the numerical precision of $p = 1024$ binary digits, 681 support points (first variant, red/gray crosses), or 682 support points (second variant, blue/black squares). (d) Comparison of the core space eigenvalues of CNPR obtained by the high-precision Arnoldi method with $n_{A} = 2000$ and $p = 768$ binary digits (red/gray crosses, same data as blue/black squares in Fig. 7) with the eigenvalues obtained by (both variants of) the rational interpolation method with the numerical precision of $p = 1024$ binary digits and $n_{R} = 300$ eigenvalues (blue/black squares). Here both variants with 601 or 602 support points provide identical spectra (differences below $10^{- 14}$ ). (b, e) Same as panels (a) and (d) with a zoomed range: $- 0.5 \leq Re (λ), Im (λ) \leq 0.5$ . (c) Comparison of the core space spectra obtained by the high-precision Arnoldi method (red/gray crosses, $n_{A} = 2000$ and $p = 768$ ) and by the rational interpolation method with $p = 12 288$ , $n_{R} = 2000$ eigenvalues (blue/black squares). (f) Same as (c) with $p = 16 384$ , $n_{R} = 2500$ for the rational interpolation method. Both panels (c) and (f) are shown in a zoomed range: $- 0.1 \leq Re (λ), Im (λ) \leq 0.1$ . Eigenvalues outside the shown range coincide up to graphical precision, and both variants of the rational interpolation method provide numerically identical spectra.
Reuse & Permissions
Figure 10
The most accurate spectrum of eigenvalues of $S$ for CNPR. (a) Red/gray dots represent the core space eigenvalues obtained by the rational interpolation method with the numerical precision of $p = 16 384$ binary digits, $n_{R} = 2500$ eigenvalues; green (light gray) dots on the $y = 0$ axis 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, see text); blue/black dots show the direct subspace eigenvalues of $S$ (same as blue/black dots in left upper panel in Fig. 3). (c) Red/gray dots represent the core space eigenvalues obtained by the high-precision Arnoldi method with $n_{A} = 2000$ and the numerical precision of $p = 768$ binary digits, and blue dots show the direct subspace eigenvalues of $S$ . Note that the Arnoldi method also determines implicitly the degenerate subspace eigenvalues of $S_{0}$ , which are therefore not shown in another color. b, d) Same as in top panels (a) and (c) with a zoomed range: $- 0.4 \leq Re (λ), Im (λ) \leq 0.4$ .
Reuse & Permissions
Figure 11
Data for the whole CNPR at different moments of time. (a) [or (c)] Number $N_{λ}$ of eigenvalues with $λ_{c} \leq λ \leq 1$ for $λ_{c} = 0.50$ (or $λ_{c} = 0.65$ ) versus the effective network size $N_{t}$ where the nodes with publication times after a cut time $t$ are removed from the network. The green/gray line shows the fractal Weyl law $N_{λ} = a {(N_{t})}^{b}$ with parameters $a = 0.32 \pm 0.08$ ( $a = 0.24 \pm 0.11$ ) and $b = 0.51 \pm 0.02$ ( $b = 0.47 \pm 0.04$ ) obtained from a fit in the range $3 \times 10^{4} \leq N_{t} < 5 \times 10^{5}$ . The number $N_{λ}$ 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$ (red/gray crosses) and $n_{A} = 2000$ (blue/black squares). (b) Exponent $b$ with error bars obtained from the fit $N_{λ} = a {(N_{t})}^{b}$ in the range $3 \times 10^{4} \leq N_{t} < 5 \times 10^{5}$ versus cut value $λ_{c}$ . (d) Effective network size $N_{t}$ versus cut time $t$ (in years). The green/gray line shows the exponential fit $2^{(t - t_{0}) / τ}$ with $t_{0} = 1791 \pm 3$ and $τ = 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.
Reuse & Permissions
Figure 12
Two eigenvectors of the matrix $S$ for the triangular CNPR. Both panels show the modulus of the eigenvector components $| ψ_{j} (N_{t}) |$ versus the time index $N_{t}$ (as used in Fig. 11) with nodes/articles ordered by the publication time (small red/gray dots). The blue/black points represent five particular articles: BCS 1957 ( $+$ ), Anderson 1958 ( $\times$ ), Benettin et al. 1976 ( $*$ ), Thouless 1977 ( $⊡$ ), and Abrahams et al. 1979 ( $⊙$ ). The left (right) panel corresponds to the real (complex) eigenvalue $λ_{0} = 1$ ( $λ_{39} = - 0.3738799 + i 0.2623941$ ).
Reuse & Permissions
Figure 13
Dependence of probability of PageRank $P$ (CheiRank $P^{*}$ ) on corresponding index $K$ ( $K^{*}$ ) for the CNPR at $α = 0.85$ .
Reuse & Permissions
Figure 14
Density distribution $W (K, K^{*}) = d N_{i} / d K d K^{*}$ of Physical Review articles in the PageRank-CheiRank plane $(K, K^{*})$ . Color bars show the natural logarithm of density, changing from minimal nonzero density (dark) to maximal one (white); zero density is shown by black. (a) All articles of CNPR; (b) CNPR without Rev. Mod. Phys.
Reuse & Permissions
Figure 15
Dependence of impact vector $v_{f}$ probability $P$ and $P^{*}$ (a, b) on the corresponding ImpactRank index $K$ and $K^{*}$ for an initial article $v_{0}$ as BCS [34] and Anderson [35] in CNPR, and Napoleon in the English Wikipedia network from Ref. [39]. Here the impact damping factor is $γ = 0.5$ .
Reuse & Permissions
Figure 16
(a) Spectrum (red/gray 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 blue/black circle represents the theoretical spectral border with radius $R = 1 / \sqrt{3 N} \approx 0.02887$ . The unit eigenvalue $λ = 1$ is not shown due to the zoomed presentation range. (c) Spectrum of one realization of triangular RPFM (red/gray crosses) with nonvanishing matrix elements uniformly distributed in the interval $[0, 2 / (j - 1) [$ and a triangular matrix with nonvanishing elements $1 / (j - 1)$ (blue/black squares); here $j = 2, 3, ..., 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) Complex eigenvalue spectrum (red/gray dots) of a sparse RPFM with dimension $N = 400$ and $Q = 20$ nonvanishing elements per column at random positions. Panel (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 blue/black circle represents the theoretical spectral border with radius $R = 2 / \sqrt{3 Q} \approx 0.2582$ ( $R = 1 / \sqrt{Q} \approx 0.2236$ ). In panels (b) and (d) $λ = 1$ is shown by a larger red dot for better visibility. The unit circle is shown by green/gray line [panels (b), (c), and (d)].
Reuse & Permissions
Figure 17
(a) Spectrum (red/gray dots) of one realization of the power law RPFM with dimension $N = 400$ and decay exponent $b = 2.5$ (see text); the unit eigenvalue $λ = 1$ is shown by a large red/gray dot, the unit circle is shown by a green/gray curve; the blue/black circle represents the spectral border with theoretical radius $R = \approx 0.1850$ (see text). (b) Dependence of the spectrum border radius on matrix size $N$ for $50 \leq N \leq 2000$ ; red/gray crosses represent the radius obtained from theory (see text); blue/black squares correspond to the spectrum border radius obtained numerically from a small number of eigenvalues with maximal modulus; the green/gray line shows the fit $R = C N^{- η}$ of red/gray crosses with $C = 0.67 \pm 0.03$ and $η = 0.22 \pm 0.01$ .
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics