Linear response theory for Google matrix

Dima L. Shepelyansky; Klaus M. Frahm

REVIEW 2 major objections 5 minor 18 references

Linear response theory for Google matrix

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new algorithm computes the exact linear response of PageRank, locating the pathway between any two nodes.

desk verdict Sound linear-response math and a scalable algorithm, but the 'effective pathway' claim rests on an unvalidated interpretive step the authors themselves flag. read the letter →

arxiv 1908.08924 v1 pith:F53EBMGD submitted 2019-08-23 cs.SI physics.soc-ph

Klaus M. Frahm , Dima L. Shepelyansky This is my paper · ORCID

classification cs.SIphysics.soc-ph

keywords GooglematrixPageRanklinearresponsetheoryLIRGOMAXREGOMAXdirectednetworksinjectionandabsorptionsensitivityanalysis

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a weak perturbation of a Google matrix, or of the Markov process behind PageRank, produces a first-order correction to the PageRank vector that can be computed exactly, without finite-difference noise, by solving an inhomogeneous equation. It introduces the LIRGOMAX algorithm, which iterates $P_1 = G_0 P_1 + V_0$ to convergence in large directed networks. For the injection/absorption variant, where probability is pumped into one node and removed at another, the entries of $P_1$ with largest absolute value mark the nodes most sensitive to the perturbation, and these form an automatically selected subset of the effective pathway between the two nodes. The paper demonstrates on a five-million-node network that this subset, combined with the REGOMAX reduction, reveals a two-block structure of direct and indirect interactions between the two endpoints. The broader point is that linear response, a standard tool in physics, transfers to PageRank and gives a direct way to probe influence and hidden pathways in directed networks.

What carries the argument

The load-bearing object is the inhomogeneous PageRank equation $P_1 = G_0 P_1 + V_0$ together with the iterative solver and the projection $Q(X)=X-(E^TX)P_0$. The equation converts the linear-response problem into a source-driven version of the PageRank fixed-point problem, so it can be solved by the same convergent iteration as PageRank itself. The projection removes the numerical component along $P_0$ that would otherwise accumulate and slow convergence, and it enforces the normalization condition $E^TP_1=0$. For the injection/absorption model, the special choice of the perturbation matrix makes $V_0$ a difference of two columns of $G_0$, which is what ties the response vector to a directed pathway between two nodes.

What would settle it

Compute $P_1$ with LIRGOMAX on a small directed network where the true pathway is known from an independent flow-based metric, for example maximum flow or random-walk hitting probabilities, and check whether the top-$|P_1|$ subset contains both endpoints and coincides with that pathway. A pair with a low-PageRank absorption node having few incoming links, where the paper itself expects the endpoints to fall outside the top subset, would already falsify the automatic pathway-selection claim.

Watch

Extended reading notes

Core claim

The central discovery is that the linear response of PageRank is governed by a single inhomogeneous fixed-point equation. Expanding $G(\varepsilon)=G_0+\varepsilon G_1$ and $F(\varepsilon,P)=P+\varepsilon F_1(P)$ around $\varepsilon=0$, the $O(\varepsilon)$ correction $P_1$ satisfies $P_1 = G_0 P_1 + V_0$ with $V_0 = G_1P_0 + G_0F_1(P_0)$. Because $E^T V_0 = 0$, the apparent singularity of $(1-G_0)^{-1}$ is harmless: $V_0$ has no component along the PageRank eigenvector, and iteration $P^{(n+1)}_1=G_0P^{(n)}_1+V_0$ converges with the same speed as the PageRank power method. For injection at $i$ and absorption at $j$, the special scaling $D_i=1/P_0(i)$, $D_j=-1/P_0(j)$ makes the source term exactly the difference between the $i$-th and $j$-th columns of $G_0$, so the response is driven by the difference of two columns of the Google matrix. Ordering all nodes by $|P_1|$ and keeping the extremes yields the most sensitive nodes, and applying REGOMAX to that subset gives the reduced Google matrix with its direct and indirect interaction components.

Load-bearing premise

The ranking of nodes by the magnitude of the first-order response $|P_1|$ is taken to identify the 'effective pathway' between the injection and absorption nodes; the paper states in Section 2.5 that there is no mathematical argument placing the two endpoints in that top subset, especially for low-PageRank nodes.

Editorial extensions

If this is right

The PageRank sensitivity $D^{(j\to i)}(k)=P_1(k)/P_0(k)$ to a matrix-element perturbation can be computed in the exact $\varepsilon\to 0$ limit, avoiding the numerical loss of precision of finite-difference formulas.
The method provides an automatic, non-heuristic way to select a small subset of nodes relevant to a perturbation, which can then be studied with REGOMAX; this replaces arbitrary choices of subset.
The same linear-response framework applies to any perturbation of the Google matrix or of the Markov process, not only injection/absorption, so it can quantify how small structural changes propagate through a directed network.
On the tested five-million-node network, the top positive and negative entries of $P_1$ form two coherent blocks around the injection and absorption nodes, showing that the response captures meaningful global structure.
Because the iteration has the same cost as the power method, the computation is feasible for any network where the unperturbed PageRank can be computed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

I read the paper's 'pathway' as a claim about linear sensitivity, not about graph-theoretic paths; a natural test is whether top-$|P_1|$ nodes coincide with high-flow or high-commute-time routes on small networks where those quantities can be computed exactly.
The difference-of-columns form $V_0=(G_0)_{:i}-(G_0)_{:j}$ suggests a Green's-function interpretation: $P_1$ is the response of the Markov chain to a unit source-sink pair, so the same machinery could be applied to node influence, betweenness, or random-walk hitting times.
The paper's own caveat that injection nodes with low PageRank and few incoming links may not appear in the top-response subset implies that the automatic selection is endpoint-blind in those cases; a low-PageRank pair would require a separate criterion for including the endpoints themselves.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core of this paper is solid. The derivation in Section 2 is correct: expanding G and F to first order, getting the inhomogeneous equation P1 = G0 P1 + V0, and solving by power iteration with a projection step is standard but cleanly done. The algorithm genuinely scales to the 5.4M-node Wikipedia graph, and the exact ε→0 limit is a real improvement over finite-difference sensitivity. The pump model normalization Di = 1/P0(i), Dj = −1/P0(j) is a nice trick that makes the first-order source vector sparse and interpretable. Credit where due: this is a useful tool for PageRank sensitivity analysis, and the authors are transparent about the machinery and provide code and data links.

The soft spot is the interpretive leap from P1 to 'effective pathway.' They compute the 20 most negative and 20 most positive entries of P1, not the top 40 by |P1|, despite saying otherwise in the text. That is a concrete mismatch: in Table 1, negative entries with KL up to 68 are skipped while positive entries with KL as low as 278 are included. So the sign-balanced subset is an arbitrary choice, and the claimed magnitude criterion is not what is implemented. More importantly, Section 2.5 explicitly concedes there is 'no simple mathematical argument' that the injection and absorption nodes even belong to the top-response set. Without an independent flow-based or ground-truth metric, the pathway interpretation is a conjecture. Large |P1| can reflect global PageRank redistribution rather than a source-to-target route, as the appearance of United States at KL=4 suggests.

That said, these are problems with the application framing, not with the mathematics. The linear response computation is correct, and the REGOMAX analysis of the selected subset is a reasonable, if preliminary, illustration. The paper reads as an honest first demonstration. For a reader wanting to compute PageRank sensitivity on huge directed networks, this is a genuinely useful contribution. For a reader expecting validated path discovery, it falls short.

My recommendation: send it to peer review. A good referee should push the authors to either validate the pathway claim against a flow-based baseline or reframe the paper as sensitivity analysis without the pathway language. The subset-selection discrepancy should also be fixed or explained. This is a worthwhile contribution that needs revision, not rejection.

Referee Report

2 major / 5 minor

Summary. The paper develops a linear response formalism for the Google matrix/PageRank problem, deriving the first-order correction P1 to the PageRank vector under a weak perturbation of either the Google matrix or the stochastic process. The central algorithmic contribution is LIRGOMAX, which solves the inhomogeneous PageRank equation P1 = G0 P1 + V0 by iteration with a projection step, avoiding the numerical loss of precision of finite-difference estimates. Two perturbation models are treated: a pump model with probability injection at one node and absorption at another, and a PageRank-sensitivity model for individual matrix-element changes. The method is applied to the 2017 English Wikipedia network (N ≈ 5.4 million) for two injection/absorption pairs (University of Cambridge / Harvard University, and Napoleon / Alexander I of Russia). In each case the authors select 40 nodes from the extremes of P1, apply the REGOMAX reduction to that subset, and present reduced Google matrices and 'friend' networks, which they interpret as revealing the effective pathway between the initial pair of nodes.

Significance. If assessed as a computational method for the exact ε→0 limit of PageRank linear response, the contribution is solid and potentially useful. The derivation in Section 2.4 is internally consistent; the iteration (12) with projection (13) is a standard and efficient way to solve the singular inhomogeneous equation, and the reported scalability to a 5-million-node network is a genuine practical advantage. The paper honestly acknowledges some limitations, notably in Section 2.5 where it concedes that there is no mathematical argument guaranteeing the initial nodes belong to the top-response set. However, the paper's central application claim—that the selected nodes constitute the 'effective pathway' between the injection and absorption nodes—is an interpretive step that is not validated by any independent ground truth, flow-based metric, or comparison with alternative pathway-finding methods. As written, the paper demonstrates a sensitivity-analysis algorithm; the pathway-discovery language overstates what is established.

major comments (2)

[Section 2.5 and Section 3] The identification of the nodes with the largest linear-response values as an 'effective pathway' between injection and absorption nodes is unsupported. Section 2.5 explicitly states that there is 'no simple mathematical argument' that the two initial nodes even belong to the top-response set, and Sections 3.1–3.2 provide no external validation: no comparison with explicit hyperlink paths, random-walk hitting or commute probabilities, betweenness/flow centrality, or any other pathway benchmark. Because the abstract and Discussion present pathway identification as the main application, this is a load-bearing issue. The authors should either provide such validation or explicitly reframe the contribution as a sensitivity-analysis tool rather than a pathway-discovery method.
[Section 2.5, Tables 1 and 2] The implemented node-selection rule is not the top-40 subset by |P1| implied by the surrounding narrative; it is the union of the 20 most negative and 20 most positive entries of P1. Table 1 omits negative entries with KL ranks between 24 and 68 while including positive entries with KL ranks as low as 278, and Table 2 shows the same pattern (e.g., positive entries down to KL=209 while intervening negative entries are skipped). This sign-balanced selection changes the REGOMAX subset and therefore changes all subsequent reduced-matrix results in Figures 2–4 and 6–8. The authors should justify this unstated modeling choice or report results for the literal top-40 magnitude criterion, since the current rule is an additional arbitrary element in the pipeline.

minor comments (5)

[Section 4 and Section 3.2] There are small language errors: 'matricies' in Section 4 should be 'matrices', and Section 3.2 contains the duplicated article in 'In contrast to the the previous example'.
[Section 2.1] The statement that results are insensitive to α in the range 0.5 ≤ α ≤ 0.95 is cited to previous work; since P1 is a new derived quantity, a one-line check that the reported top-response tables are stable under this α variation would make the algorithmic claim more self-contained.
[Figures 4 and 8] The caption explains that friends are chosen by the largest matrix elements in the same column of Grr+Gqr^(nd), but the direction convention of the drawn arrows should be stated explicitly in the captions, because the column-stochastic convention may make the link direction non-obvious to readers.
[References] Reference [10] is cited as an arXiv preprint; if a peer-reviewed version exists, it should be cited instead, and reference [16] is a project URL without a persistent identifier, so the exact data and code snapshot used for the figures should be archived with a DOI.
[Section 2.5] The term 'pathway' is used before it is operationally defined; the manuscript would be clearer if it stated in Section 2.5 that 'pathway' is a heuristic label for the set of nodes with large |P1|, rather than a mathematically defined object.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: LIRGOMAX solves the exact first-order PageRank response equation with no fitted inputs; the 'effective pathway' label is an acknowledged interpretation, not a by-construction prediction.

full rationale

The LIRGOMAX derivation is self-contained. Equations (6)-(10) expand the perturbed stationary condition P = G(ε)F(ε,P) to first order and obtain the inhomogeneous equation P1 = G0 P1 + V0, with V0 = G1P0 + G0F1(P0). For the pump model, Section 2.4.2 reduces V0 to Q(G0DP0), and the choice Di = 1/P0(i), Dj = -1/P0(j) is a normalization that makes e(P0) = 0 and gives W0 entries +1 and -1; no parameter is fitted to the final subset. The iteration (12) is a standard convergent linear solve of that fixed equation, and the projection (13) only removes numerical contamination along the PageRank direction. REGOMAX is invoked from prior work as a downstream analysis tool, but the central LIRGOMAX claim does not depend on an unverified self-citation or an imported uniqueness theorem. The only soft point is Section 2.5, which explicitly concedes 'there is no simple mathematical argument' that the injection and absorption nodes belong to the largest-|P1| subset; this is a caveat about whether the top-response set deserves the label 'effective pathway', not a circular reduction, because P1 is not defined in terms of the selected subset. The sign-balanced 20+20 subset selection and the absence of external pathway ground truth affect external validity and interpretation, not the logical independence of the computation.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central derivation rests on standard Perron-Frobenius theory and the column-stochastic normalization of the Google matrix. The only ad hoc premise is that high |P1| values define the effective pathway, which is the paper's interpretive leap. The two free parameters in the analysis are the arbitrary subset size and the choice of injection/absorption weights, neither of which is fitted to outcome data.

free parameters (2)

Subset size: number of top |P1| nodes per sign = 20 negative and 20 positive entries (Nr = 40)
The paper defines the pathway subset as the 20 nodes with the strongest negative and 20 with the strongest positive P1 values; this cutoff is arbitrary and no sensitivity analysis is provided.
Injection/absorption weights D_i and D_j = D_i = 1/P0(i), D_j = -1/P0(j)
This normalization makes e(P0) = ET D P0 = 0 so the denominator in (2) equals unity; it is a convenient model choice rather than a parameter fitted to reproduce the reported subset.

assumptions (4)

standard math G0 is a primitive stochastic matrix with a unique PageRank eigenvector P0.
Invoked implicitly in Section 2.1 to justify existence and uniqueness of P0 and convergence of power iteration; follows from Perron-Frobenius theory for Google matrices.
standard math The left leading eigenvector of G0 is the uniform vector ET.
Used to derive the orthogonality conditions (8) and the projector Q in (13); follows from the column-stochastic normalization of G0.
domain assumption Terms of order ε² and higher are negligible in the expansion.
The linear response is defined as the first-order coefficient in ε; the paper provides no bound on the remainder terms for the specific pump and sensitivity perturbations. Introduced in Section 2.4.1.
ad hoc to paper Ranking by |P1| identifies the 'effective pathway' between injection and absorption nodes.
The central interpretive claim, asserted in the abstract and Section 2.5, is not derived from the mathematics and is not validated against any ground-truth pathway or flow metric.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear response theory for Google matrix." pith.science (2026). https://pith.science/paper/F53EBMGD

@misc{pith2026190808924,
  author       = {Pith},
  title        = {Pith review of: Linear response theory for Google matrix},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F53EBMGD}},
  note         = {Machine review of arXiv:1908.08924}
}

read the original abstract

We develop the linear response theory for the Google matrix PageRank algorithm with respect to a general weak perturbation and a numerical efficient and accurate algorithm, called LIRGOMAX algorithm, to compute the linear response of the PageRank with respect to this perturbation. We illustrate its efficiency on the example of the English Wikipedia network with more than 5 millions of articles (nodes). For a group of initial nodes (or simply a pair of nodes) this algorithm allows to identify the effective pathway between initial nodes thus selecting a particular subset of nodes which are most sensitive to the weak perturbation applied to them (injection or pumping at one node and absorption of probability at another node). The further application of the reduced Google matrix algorithm (REGOMAX) allows to determine the effective interactions between the nodes of this subset. General linear response theory already found numerous applications in various areas of science including statistical and mesoscopic physics. Based on these grounds we argue that the developed LIRGOMAX algorithm will find broad applications in the analysis of complex directed networks.

Figures

Figures reproduced from arXiv: 1908.08924 by the authors.

**Figure 2.** Reduced Google matrix components GR, Gpr, Grr and Gqr for the English Wikipedia 2017 network and the subgroup of nodes given in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 1.** Linear response vector P1 of PageRank for the English Wikipedia 2017 with injection (or pumping) at University of Cambridge and absorption at Harvard University. Here KL is the ranking index obtained by ordering |P1| from maximal value at KL = 1 down to its minimal value. Top panel shows |P1| versus KL in a double logarithmic representation for all N nodes. Bottom panel shows a zoom of P1 versus KL for KL ≤ 103 i… view at source ↗

**Figure 3.** Same as in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 7.** Figure 7: Same as in [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]

**Figure 5.** Figure 5: Same as in [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 6.** Figure 6: As [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

**Figure 8.** Figure 8: Same as in [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages

[1]

Kubo, Statistical-mechanical theory of irreversible pro- cesses

R. Kubo, Statistical-mechanical theory of irreversible pro- cesses. I. General theory and simple applications to mag- netic and conduction problems, J. Phys. Soc. Japan12(6), 570 (1957)

work page 1957
[2]

Hanggi and H

P. Hanggi and H. Thomas,Stochastic processes: time evo- lution, symmetries and linear response, Phys. Rep.88, 207 (1982)

work page 1982
[3]

Baranger and A.D

H.U. Baranger and A.D. Stone,Electrical linear-response theory in an arbitrary magnetic ﬁeld: a new Fermi-surface formation, Phys. Rev. B40, 8159 (1989)

work page 1989
[4]

Vignale and W

G. Vignale and W. Kohn, Current-dependent exchange- correlation potential for dynamical linear response theory, Phys. Rev. Lett.77, 2037 (1996)

work page 1996
[5]

Ruelle, A review of linear response theory for gen- eral diﬀerentiable dynamical systems, Nonlinearity22, 855 (2009)

D. Ruelle, A review of linear response theory for gen- eral diﬀerentiable dynamical systems, Nonlinearity22, 855 (2009)

work page 2009
[6]

S.Brin and L.Page, The anatomy of a large-scale hyper- textual Web search engine, Computer Networks and ISDN Systems 30, 107 (1998)

work page 1998
[7]

Langville and C.D

A.M. Langville and C.D. Meyer,Google’s PageRank and beyond: the science of search engine rankings, Princeton University Press, Princeton (2006)

work page 2006
[8]

Frahm and D.L

L.Ermann, K.M. Frahm and D.L. Shepelyansky Google matrix analysis of directed networks, Rev. Mod. Phys.87, 1261 (2015) K.M. Frahm and D.L. Shepelyansky: Linear response theory for Google matrix 11

work page 2015

Show all 18 references

[9]

Frahm and D.L

K.M. Frahm and D.L. Shepelyansky, Wikipedia net- works of 24 editions of 2017 , Available: http: //www.quantware.ups-tlse.fr/QWLIB/24wiki2017/. Accessed August (2019)

2019
[10]

Frahm and D.L

K.M. Frahm and D.L. Shepelyansky,Reduced Google ma- trix, arXiv:1602.02394[physics.soc] (2016)

2016 arXiv
[11]

Frahm, K

K.M. Frahm, K. Jaﬀres-Runser and D.L. Shepelyansky, Wikipedia mining of hidden links between political leaders, Eur. Phys. J. B89, 269 (2016)

2016
[12]

Coquide, J

C. Coquide, J. Lages and D.L. Shepelyansky,World inﬂu- ence and interactions of universities from Wikipedia net- works, Eur. Phys. J. B92, 3 (2019)

2019
[13]

Lages, D.L

J. Lages, D.L. Shepelyansky and A. Zinovyev,Inferring hidden causal relations between pathway members using re- duced Google matrix of directed biological networks, PLoS ONE 13(1), e0190812 (2018)

2018
[14]

Cao, Lasing in random media, Waves Random Media 13, R1 (2003)

H. Cao, Lasing in random media, Waves Random Media 13, R1 (2003)

2003
[15]

Coquide, L

C. Coquide, L. Ermann, J. Lages and D.L. Shepelyansky, Inﬂuence of petroleum and gas trade on EU economies from the reduced Google matrix analysis of UN COM- TRADE data, Eur. Phys. J. B92, 171 (2019)

2019
[16]

Frahm and D.L

K.M. Frahm and D.L. Shepelyansky, LIRGOMAX al- gorithm, Available:http://www.quantware.ups-tlse.fr/ QWLIB/lirgomax. Accessed August (2019)

2019
[17]

Chepelianskii A.D.,Towards physical laws for software ar- chitecture, arXiv:1003.5455 [cs.SE] (2010)

2010 arXiv
[18]

T. Guhr, A. Müller-Groeling, H.A. Weidenmüller, Random-matrix theories in quantum physics: common con- cepts, Phys. Rep.299, 189 (1998)

1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Kubo, Statistical-mechanical theory of irreversible pro- cesses

R. Kubo, Statistical-mechanical theory of irreversible pro- cesses. I. General theory and simple applications to mag- netic and conduction problems, J. Phys. Soc. Japan12(6), 570 (1957)

work page 1957

[2] [2]

Hanggi and H

P. Hanggi and H. Thomas,Stochastic processes: time evo- lution, symmetries and linear response, Phys. Rep.88, 207 (1982)

work page 1982

[3] [3]

Baranger and A.D

H.U. Baranger and A.D. Stone,Electrical linear-response theory in an arbitrary magnetic ﬁeld: a new Fermi-surface formation, Phys. Rev. B40, 8159 (1989)

work page 1989

[4] [4]

Vignale and W

G. Vignale and W. Kohn, Current-dependent exchange- correlation potential for dynamical linear response theory, Phys. Rev. Lett.77, 2037 (1996)

work page 1996

[5] [5]

Ruelle, A review of linear response theory for gen- eral diﬀerentiable dynamical systems, Nonlinearity22, 855 (2009)

D. Ruelle, A review of linear response theory for gen- eral diﬀerentiable dynamical systems, Nonlinearity22, 855 (2009)

work page 2009

[6] [6]

S.Brin and L.Page, The anatomy of a large-scale hyper- textual Web search engine, Computer Networks and ISDN Systems 30, 107 (1998)

work page 1998

[7] [7]

Langville and C.D

A.M. Langville and C.D. Meyer,Google’s PageRank and beyond: the science of search engine rankings, Princeton University Press, Princeton (2006)

work page 2006

[8] [8]

Frahm and D.L

L.Ermann, K.M. Frahm and D.L. Shepelyansky Google matrix analysis of directed networks, Rev. Mod. Phys.87, 1261 (2015) K.M. Frahm and D.L. Shepelyansky: Linear response theory for Google matrix 11

work page 2015