Pith. sign in

REVIEW 3 major objections 5 minor 29 references

The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read This paper claims that the directional derivative of Kemeny's constant, expressed through a rank-one-modified graph Laplacian, gives a positive, finite importance score for every edge—including cut-edges—and its unweighted version gives pos

desk verdict Kemeny derivative centrality is a real result with correct core identities; two factor-of-two errors and a thin link-prediction section need fixing before publication. read the letter →

arxiv 2508.21506 v1 pith:VIYFY42Y submitted 2025-08-29 math.NA cs.NA

Dario A. Bini , Beatrice Meini , Federico Poloni This is my paper · ORCID
classification math.NAcs.NA MSC 05C5015B5160J2065F0568R10
keywords KemenyconstantdirectionalderivativeedgecentralitycutedgeslinkpredictiongraphLaplacianrandomwalksensitivitymeasure
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 proposes using the directional derivative of Kemeny's constant—the average time for a random walk to travel between two randomly chosen vertices—as a measure of an edge's importance. It proves that this derivative has a closed form involving the inverse of a modified graph Laplacian, and that it is finite and positive for every edge, including cut-edges, where earlier finite-difference measures either diverge or need special filtering. The same expression, in its unweighted form, assigns a positive score to every non-edge, which the authors use for link prediction. A related theorem ties the new derivative to an earlier edge-centrality measure, explaining why the two largely agree while the new one avoids regularization and numerical cancellation. If correct, the paper supplies one uniform computation for ranking both existing edges and candidate future links.

What carries the argument

The load-bearing object is the quadratic form β(p,q) = w_pq^T S^{-1} D S^{-1} w_pq, with w_pq = e_p - e_q, D = diag(d), and S = L + dd^T/||d||_1, the graph Laplacian plus a rank-one term that makes it invertible. This form is the unweighted directional derivative of Kemeny's constant, and multiplied by the edge weight a_pq it is the weighted derivative. It works through the rank-one update S - t a_pq w_pq w_pq^T: applying the inverse-update formula to the trace expression for Kemeny's constant turns the perturbed Kemeny constant into a rational function of t whose first derivative is β(p,q), with positivity following from positive definiteness. Because S is invertible even when {p,q} is a cu

What would settle it

Take a network whose future links are known, compute β(p,q) for all non-edges, and compare precision at the top of the ranking against Jaccard and Adamic-Adar baselines; if the top-scoring non-edges are not future links at least as often as the baselines, the link-prediction interpretation is not supported.

Watch

Extended reading notes

Core claim

The central discovery is that the derivative of Kemeny's constant along an edge is not just a formal object but a computable, universally positive quantity. Writing w_pq = e_p - e_q, S = L + dd^T/||d||_1, and D = diag(d), the paper proves that the weighted directional derivative is µ(p,q) = a_pq · w_pq^T S^{-1} D S^{-1} w_pq and the unweighted derivative is µ̄(p,q) = w_pq^T S^{-1} D S^{-1} w_pq. Because S is invertible for every connected graph, both quantities are finite; the quadratic form is positive for every pair p ≠ q, including cut-edges and non-edges. The paper further proves that for non-cut-edges the earlier finite-difference measure of [3] equals µ(p,q) divided by 1 - a_pq w_pq^T

Load-bearing premise

The edge-importance reading depends on the perturbation model in which weakening an edge always comes with compensating self-loops at its endpoints, and for non-edges it further assumes the formal unweighted derivative predicts real future links—a link-prediction assumption supported only by a few hand-checked examples.

Editorial extensions

If this is right

  • Because µ(p,q) = a_pq β(p,q) is positive and finite for every edge, one formula and one algorithm replace the earlier three-way case split for ordinary edges, regularized cut-edges, and filtered cut-edges.
  • Because β(p,q) is well defined for all pairs, the same matrix S^{-1} D S^{-1} yields a ranking of all non-edges, so link prediction no longer requires common neighbours to assign a nonzero score.
  • Theorem 2 gives c(p,q) = µ(p,q) / (1 - a_pq w_pq^T S^{-1} w_pq) on non-cut-edges, so the new derivative and the earlier finite-difference measure agree up to an edge-dependent factor there.
  • For one-path graphs, µ(q,q+1) = σ_{q-1}(1 - σ_{q-1}) / (λ_{q-1} π_{q-1}); with unit weights this becomes a parabola peaking near the middle edge, quantifying which edge most hurts circulation if weakened.
  • The normalized average of β(p,q) over all pairs defines a single scalar sensitivity of Kemeny's constant, computable from the trace and total sum of S^{-1} D S^{-1} without enumerating edges.

Reading between the lines

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

  • Since β(p,q) = ||D^{1/2} S^{-1}(e_p - e_q)||^2, the non-edge scores form a squared Euclidean distance between vertices in the metric induced by S^{-1} D S^{-1}; this suggests triangle-inequality-based shortcuts and a direct connection to resistance-like measures.
  • The identity µ(p,q) = a_pq β(p,q) means edge importance scales linearly with weight while β itself is weight-free; a natural testable extension is to use β alone as a scale-free ranking that does not over-prioritize heavy edges.
  • The global sensitivity measure could be used as a design objective: among candidate edge additions, choose the one that most reduces the sensitivity of Kemeny's constant, a computation that can be done from a single inverse matrix; the paper does not run this optimization.
  • A held-out-edge benchmark with AUC and precision-at-k against common-neighbour indices would establish how broadly the non-edge scores transfer, beyond the anecdotal checks reported.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper introduces two directional derivatives of Kemeny's constant for edges and non-edges of an undirected weighted graph: a weighted derivative μ(p,q) and an unweighted derivative μ̄(p,q). The central algebraic results are: μ(p,q)=a_pq β(p,q), where β(p,q)=w_pq^T S^{-1} D S^{-1} w_pq with S = L + dd^T/‖d‖_1; the positivity of β, including for cut-edges and for non-edges; the relation c(p,q)=μ(p,q)/(1−a_pq w_pq^T S^{-1} w_pq) to the Altafini et al. centrality; an algorithm based on Cholesky factorization; explicit formulas for one-path graphs; and applications to road-network centrality, link prediction, and a global sensitivity measure ζ(G). The main identities (Corollary 1 and Theorem 2) are self-contained and appear correct. However, several secondary but stated results contain factor-of-two errors, and the link-prediction application is supported only by anecdotal evidence.

Significance. If the central identities are correct, the paper makes a useful contribution: μ(p,q) is a universally defined, always-positive edge centrality that avoids the cut-edge singularities and numerical cancellation of the measure in [3], and the closed form via S^{-1}DS^{-1} is parameter-free and directly computable. The connection to the existing centrality of [3] is elegant, and the proposed algorithm appears to yield substantial speedups on large road networks. The unweighted measure μ̄(p,q) gives a positive score to every pair of vertices, which is a potentially valuable algebraic heuristic for link prediction. That said, the advertised link-prediction application is not yet established: the derivative for non-edges is a formal extrapolation along a non-stochastic direction, and the empirical validation is minimal. The factor-of-two errors in Theorem 3 and Eq. (3.7) are real and must be corrected before the paper can be accepted.

major comments (3)
  1. [§3.2, Eq. (3.7)] The formula for ζ(G) is off by a factor of 2. Since μ̄(p,q) = (e_p−e_q)^T M (e_p−e_q) with M = S^{-1}DS^{-1}, summing over all ordered pairs gives Σ_{p,q} μ̄(p,q) = 2n tr(M) − 2 1^T M 1, not n tr(M) − 1^T M 1. Thus ζ(G) should be [2n tr(M) − 2 1^T M 1]/n^2. This error propagates to Figure 6, where the reported values and the comparison across graph families are affected.
  2. [§3, Theorem 3 and Corollary 3] Theorem 3 and Corollary 3 each contain a factor-of-two error. On the two-node graph with a single edge of weight 1, direct computation gives the filtered centrality c_F = 1/2, while Theorem 3 gives c_F = 1. The coefficient in Theorem 3 should be 1 rather than 2, and the bounds in Corollary 3 should have 1/a_pq rather than 2/a_pq. This also affects the comparison with [3] in Section 6 and any use of c_F.
  3. [§3 (definition of μ̄) and §6 (link prediction)] The unweighted derivative for a non-edge, a_pq = 0, is taken along D^{-1}w_pq w_pq^T, which has negative off-diagonal entries; P + tD^{-1}w_pq w_pq^T is not a stochastic matrix of any graph. Hence μ̄(p,q) is an algebraic derivative of an extended Kemeny function, not the derivative under an edge-insertion process. The paper does not state this distinction. The link-prediction claim in the abstract and conclusions ('low μ̄ means probable future collaboration') is then validated only by hand-checking 3 of the top 10 predicted pairs in one collaboration network, with no temporal split, no AUC/Precision@k evaluation, and no comparison against the common-neighbour baselines mentioned in the same section. This is insufficient support for a central advertised application. The authors should either supply a quantitative evaluation or substantially soften the link-prediction interpretation.
minor comments (5)
  1. [§4, Algorithm 1] The notation in (4.6), "w_pq = (w_pq)_{i=1,\dots,n-1}", is confusing because the same symbol is used for the full vector and its first n−1 components. Suggest using a different symbol, e.g., ̂w_pq.
  2. [§6, Figure 4] The matrices of centrality values are printed with many digits and are hard to read. A heatmap with a color scale, or a smaller number of displayed digits, would improve readability.
  3. [§6, Table 1 and Figure 5] The text states that correlations are 'as expected' because the Kemeny derivative is sorted oppositely, but the reported correlations are only pairwise; no statistical significance or ranking metrics are given. This is acceptable as exploratory, but it should be labeled as such.
  4. [§5, Theorem 4] The formula for μ(q,q+1) is stated for q=1,\dots,n−1, but the notation σ_{q−1} and λ_{q−1} requires q≥1; this is implicit but could be made explicit.
  5. [§1] The phrase 'it is numerically stable since its computation avoids cancellation' is plausible but not demonstrated with a rounding-error analysis; a brief justification or reference would help.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivative identities are derived by direct Sherman-Morrison computation; self-citations are background only.

full rationale

The paper's central results, Corollary 1 and Theorem 2, are obtained by differentiating κ(Ppq(t)) = trace(D^{1/2} S_{pq}(t)^{-1} D^{1/2}) - 1 and applying the Sherman-Woodbury-Morrison formula to S_{pq}(t) = S - t a_{pq} w_{pq} w_{pq}^T. This is a self-contained algebraic derivation: no fitted constants, learned parameters, or data-driven calibrations enter the definition of μ(p,q) or ¯μ(p,q). The relation to the edge centrality of [3] in Theorem 2 uses a previously published formula (2.6) from the authors' own work, but that formula is an explicit, independently checkable mathematical result and is not an input that encodes the new derivative measure; the new measure stands without that comparison. Similarly, the one-path expression imports [8, Thm 5.1] for Kemeny's constant from overlapping-author work, but as a benchmark formula, not as a hidden premise that forces the conclusion. The non-edge score is an extrapolation: for a_{pq}=0, P + t D^{-1} w_{pq} w_{pq}^T is not a stochastic matrix, so ¯μ(p,q) is a formal derivative of an extended Kemeny function, and the link-prediction interpretation is heuristic. That is a validation weakness, not circularity, because no prediction was used to define the measure and no target quantity was fitted. The manual check of three of the top ten predicted links is thin evidence, but the derivation itself is not equivalent to its inputs. Score 1 reflects the presence of overlapping-author citations and the heuristic non-edge interpretation, neither of which makes the derivation circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted: the measures are closed-form functions of the graph Laplacian, its rank-one modification S, and the degree vector. No new entities are postulated; the paper defines mathematical measures on existing graph data. The axioms are standard linear-algebra and Markov-chain results plus the stated connectedness assumption.

assumptions (6)
  • standard math Sherman-Woodbury-Morrison identity for rank-one perturbations of nonsingular matrices
    Used in the proofs of Theorem 1 (expansion of S_pq(t)^{-1}), Theorem 2, and Theorem 3; standard linear algebra.
  • standard math Perron-Frobenius theorem for irreducible nonnegative matrices
    Section 2, eigenvalue ordering (2.1); guarantees a simple eigenvalue 1 and lambda_i < 1 for a connected graph.
  • standard math Brauer theorem on eigenvalues of rank-one perturbations of stochastic matrices
    Section 2; used to show the eigenvalues of I - P + 1v^T are 1 and 1 - lambda_i, giving kappa = sum 1/(1-lambda_i).
  • standard math Kemeny's constant formula kappa = trace(I - P + 1v^T)^{-1} - 1
    Eq. (2.2), cited to [22,27]; this is the baseline identity that the whole paper differentiates.
  • standard math Theorem 5.1 of [8] giving Kemeny's constant for one-path birth-death processes (formula (5.2))
    Section 5; used to derive the explicit one-path formula in Theorem 4. It is a published result with overlapping authors but is used as a prior benchmark, not as an input encoding the target result.
  • domain assumption The graph G is connected and edge weights are positive
    Section 2; ensures irreducibility, lambda_i < 1, and invertibility of S = L + dd^T/||d||_1, which is required for every formula in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs." pith.science (2026). https://pith.science/paper/VIYFY42Y

@misc{pith2026250821506,
  author       = {Pith},
  title        = {Pith review of: The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VIYFY42Y}},
  note         = {Machine review of arXiv:2508.21506}
}
read the original abstract

Kemeny's constant quantifies a graph's connectivity by measuring the average time for a random walker to reach any other vertex. We introduce two concepts of the directional derivative of Kemeny's constant with respect to an edge and use them to define centrality measures for edges and non-edges in the graph. Additionally, we present a sensitivity measure of Kemeny's constant. An explicit expression for these quantities involving the inverse of the modified graph Laplacian is provided, which is valid even for cut-edges. These measures are connected to the one introduced in [Altafini et al., SIMAX 2023], and algorithms for their computation are included. The benefits of these measures are discussed, along with applications to road networks and link prediction analysis. For one-path graphs, an explicit expression for these measures is given in terms of the edge weights.

Figures

Figures reproduced from arXiv: 2508.21506 by the authors.

Figure 1
Figure 1. One-path graph formed by n = 6 vertices. In Section 5, we will provide explicit expressions of µ(p, q) for one-path graphs as performed in [9] for c(e), and show the good behaviour of the new measure. 5 One-path graphs Consider the case of a one-path graph formed by n vertices connected as in [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Centralities of the roads in the Pisa road map. On the left, the values are computed by the measure of [3]; on the right, the values are computed using the derivative. The thicker the line, the higher the centrality of the road. maximum values taken by the measure. Regarding the association of the color with the numerical value of the measure, we have considered the square root of the measure to better highlight the… view at source ↗
Figure 3
Figure 3. Log-scale histograms of the centralities in the road map of Pisa, divided into 50 bins. On the left, the values are computed by the measure of [3]; on the right, the values are computed using the derivative. trality value, which is slightly higher than twice the value of the existing edges. For the one-path graph, the most important non-edge is the one that connects the first node to the last one, and the importance… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Edges centralities in star, one-path, circulant, and tree graphs. On the left, the tested graph, on the right, the centralities, in log scale, of edges and non-edges. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]
Figure 5
Figure 5. Figure 5: 50 top new edges (in red) most likely to be added to the blue graph, as predicted by the five tested measures. on common neighbours, but with a further additive term that is inversely pro￾portional to the distance between the two nodes; hence, this centrality measure g…
Figure 6
Figure 6. Figure 6: Global sensitivity ζ(G), as a function of the number of vertices n, for the star, one-path and circulant graph. J A R C K Jaccard 1 0.83 0.76 0.56 -0.15 Adamic–Adar 0.83 1 0.96 0.64 -0.17 Resource allocation 0.76 0.96 1 0.56 -0.15 Common neighbour 0.56 0.64 0.56 1 -0.5…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [3]

    Altafini, D

    D. Altafini, D. A. Bini, V. Cutini, B. Meini, and F. Poloni. An edge centrality measure based on the Kemeny constant. SIAM J. Matrix Anal. Appl., 44(2):648–669, 2023

    work page 2023

  2. [1]

    Ahmad, M

    I. Ahmad, M. U. Akhtar, S. Noor, and A. Shahnaz. Missing link predic- tion using common neighbor and centrality based parameterized algorithm. Scientific Reports, 10(364), 2020

    work page 2020

  3. [2]

    On the Edge Derivative of the Normalized Laplacian with Applications to Kemeny's Constant

    C. Albright, K. P. Hadaway, A. H. Pomerance, J. Jeffries, K. J. Lorenzen, and A. K. Nix. On the edge derivative of the normalized laplacian with applications to Kemeny’s constant. arXiv:2211.01495, 2023

    work page Pith review arXiv 2023

  4. [4]

    Benzi and P

    M. Benzi and P. Boito. Matrix functions in network analysis. GAMM- Mitteilungen, 43(3):e202000012, 2020

    work page 2020

  5. [5]

    Changing the ranking in eigenvector centrality of a weighted graph by small perturbations

    M. Benzi and N. Guglielmi. Changing the ranking in eigenvector centrality of a weighted graph by small perturbations. arXiv:2501.10745, to appear in Math. Comp. , 2025

    work page Pith review arXiv 2025

  6. [6]

    Benzi and C

    M. Benzi and C. Klymko. Total communicability as a centrality measure. Journal of Complex Networks , 1(2):124–149, 05 2013

    work page 2013

  7. [7]

    Berkhout and B

    J. Berkhout and B. F. Heidergott. Analysis of Markov influence graphs. Operations Research, 67(3):892 – 904, 2019

    work page 2019

  8. [8]

    D. Bini, J. J. Hunter, G. Latouche, B. Meini, and P. Taylor. Why is Kemeny’s constant a constant? Journal of Applied Probability, 55(4):1025– 1036, 2018

    work page 2018

Show all 29 references
  1. [9]

    D. A. Bini, S. Kirkland, G. Latouche, and B. Meini. Cut-edge centralities in an undirected graph. Numerical Algorithms, 2025

    2025

  2. [10]

    A. Brauer. Limits for the characteristic roots of a matrix. IV: Applications to stochastic matrices. Duke Math. J. , 19(1):75 – 91, 1952

    1952

  3. [11]

    Breen and S

    J. Breen and S. Kirkland. A structured condition number for Kemeny’s constant. SIAM Journal on Matrix Analysis and Applications , 40(4):1555– 1578, 2019

    2019

  4. [12]

    Cipolla, F

    S. Cipolla, F. Durastante, and B. Meini. Enforcing Katz and PageRank centrality measures in complex networks. SIAM J. Math. Data Science , 2025

    2025

  5. [13]

    Crisostomi, S

    E. Crisostomi, S. Kirkland, and R. Shorten. A Google-like model of road network dynamics and its application to regulation and control. Interna- tional Journal of Control , 84(3):633–651, 2011. 22

    2011

  6. [14]

    Cuthill and J

    E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th National Conference , ACM ’69, page 157–172, New York, NY, USA, 1969. Association for Computing Ma- chinery

    1969

  7. [15]

    W. K. Grassmann, M. I. Taksar, and D. P. Heyman. Regenerative analysis and steady state distributions for Markov chains. Operations Research, 33(5):1107–1116, 1985

    1985

  8. [16]

    A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. In G. Varoquaux, T. Vaught, and J. Millman, editors, Proceedings of the 7th Python in Science Conference (SciPy2008), pages 11–15, Pasadena, CA, USA, August 2008

    2008

  9. [17]

    M. A. Hasan and M. J. Zaki. A Survey of Link Prediction in Social Net- works, pages 243–275. Springer US, Boston, MA, 2011

    2011

  10. [18]

    N. J. Higham. Accuracy and Stability of Numerical Algorithms . Society for Industrial and Applied Mathematics, second edition, 2002

    2002

  11. [19]

    N. J. Higham. Functions of matrices . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation

    2008

  12. [20]

    J. J. Hunter. The role of Kemeny’s constant in properties of Markov chains. Comm. Statist. Theory Methods , 43(7):1309–1321, 2014

    2014

  13. [21]

    Kemeny and J

    J. Kemeny and J. Snell. Finite Markov Chains . Van Nostrand, 1960

    1960

  14. [22]

    J. G. Kemeny. Generalization of a fundamental matrix. Linear Algebra Appl., 38:193–206, 1981

    1981

  15. [23]

    Kirkland, Y

    S. Kirkland, Y. Li, J. McAlister, and X. Zhang. Edge addition and the change in Kemeny’s constant. arXiv preprint arXiv:2306.04005 , 2023

    2023 arXiv

  16. [24]

    Liben-Nowell and J

    D. Liben-Nowell and J. M. Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019–1031, 2007

    2007

  17. [25]

    M. E. J. Newman. Finding community structure in networks us- ing the eigenvectors of matrices. Physical Review E , 74:036104, 2006. arXiv:physics/0605087

    2006 arXiv

  18. [26]

    Patel, P

    R. Patel, P. Agharkar, and F. Bullo. Robotic surveillance and Markov chains with minimal weighted Kemeny constant. IEEE Transactions on Automatic Control, 60(12):3156–3167, 2015

    2015

  19. [27]

    X. Wang, J. L. Dubbeldam, and P. Van Mieghem. Kemeny’s constant and the effective graph resistance. Linear Algebra Appl., 535:231–244, 2017

    2017

  20. [28]

    T. Zhou. Progresses and challenges in link prediction. iScience, 24(11):103217, 2021. 23

    2021

  21. [29]

    T. Zhou, L. Lu, and Y.-C. Zhang. Predicting missing links via local infor- mation. The European Physical Journal B , 71(4):623–630, 2009. 24

    2009

Pith tools

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