Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2, p. 11 — under (†) the HITS iterates converge, x* to the principal eigenvector of AᵀA and y* to that of AAᵀ

Proved
KleinbergHITS.Conv.theorem_3_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

convergencehitsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1power-iterationprincipal-eigenvector

Let GGG be a directed graph on nnn pages with adjacency matrix AAA (Aij=1A_{ij}=1Aij​=1 if page iii links to page jjj, else 000), and let (xk,yk)(x_k,y_k)(xk​,yk​) be the authority and hub weight vectors returned by Kleinberg's procedure Iterate(G,k)(G,k)(G,k): starting from x0=y0=(1,…,1)x_0=y_0=(1,\dots,1)x0​=y0​=(1,…,1), each round replaces the authority weight of a page by the sum of the hub weights of the pages linking to it, then the hub weight of a page by the sum of the new authority weights of the pages it links to, and normalizes both vectors so that their squares sum to 111.

Assume Assumption (†) for A⊤AA^{\top}AA⊤A and for AA⊤AA^{\top}AA⊤: for each of these symmetric matrices, the eigenvalue λ1\lambda_1λ1​ of largest absolute value is simple, nonzero, and strictly larger in absolute value than every other eigenvalue. Then there are vectors x∗,y∗x^*,y^*x∗,y∗ such that

xk→x∗,yk→y∗(k→∞),x_k\to x^*,\qquad y_k\to y^*\qquad(k\to\infty),xk​→x∗,yk​→y∗(k→∞),

and x∗x^*x∗ is a principal eigenvector of A⊤AA^{\top}AA⊤A and y∗y^*y∗ is a principal eigenvector of AA⊤AA^{\top}AA⊤: unit vectors with A⊤Ax∗=λ1(A⊤A) x∗A^{\top}Ax^*=\lambda_1(A^{\top}A)\,x^*A⊤Ax∗=λ1​(A⊤A)x∗ and AA⊤y∗=λ1(AA⊤) y∗AA^{\top}y^*=\lambda_1(AA^{\top})\,y^*AA⊤y∗=λ1​(AA⊤)y∗.

This is the central result of §3: the hub and authority scores computed by the HITS algorithm are the principal eigenvectors of the co-citation matrix A⊤AA^{\top}AA⊤A and the bibliographic coupling matrix AA⊤AA^{\top}AA⊤, so that any eigenvector algorithm computes them.

Formalization Note Theorem 3.2 refers to the limits x∗,y∗x^*,y^*x∗,y∗ of Theorem 3.1, so the statement asserts their existence as well. Assumption (†) is the paper's standing assumption; its encoding includes λ1≠0\lambda_1\ne0λ1​=0, which the paper attributes to (†) on p. 11 and without which the one-page graph with no link would be a counterexample. "The principal eigenvector" is determined only up to sign; the statement says that each limit is a unit vector in the one-dimensional principal eigenspace. Non-negativity of x∗x^*x∗, y∗y^*y∗ is true but not part of the printed theorem and is not asserted.

Preamble
import Mathlib
import Definitions.Def_KleinbergHITS_Conv_Setting
Formal statement
namespace KleinbergHITS.Conv

open Matrix Filter Topology

/-- Kleinberg (1999), §3, Theorems 3.1 and 3.2, pp. 10–11: under Assumption (†) for `AᵀA` and `AAᵀ`,
the `Iterate` sequences converge to limits `x*` and `y*`, and `x*` is the principal eigenvector of
`AᵀA` and `y*` is the principal eigenvector of `AAᵀ`. -/
theorem theorem_3_2 {n : ℕ} (E : Fin n → Fin n → Prop) [DecidableRel E]
    (hAtA : Dagger ((adjMatrix E)ᵀ * adjMatrix E)) (hAAt : Dagger (adjMatrix E * (adjMatrix E)ᵀ)) :
    ∃ xstar ystar : Fin n → ℝ,
      Tendsto (fun k => (hitsIter E k).1) atTop (𝓝 xstar) ∧
      Tendsto (fun k => (hitsIter E k).2) atTop (𝓝 ystar) ∧
      IsPrincipalEigenvector ((adjMatrix E)ᵀ * adjMatrix E) xstar ∧
      IsPrincipalEigenvector (adjMatrix E * (adjMatrix E)ᵀ) ystar := by sorry

end KleinbergHITS.Conv
Source
Kleinberg, Authoritative sources in a hyperlinked environment, J. ACM 46(5) (1999), author's copy, pp. 10–11, Theorems 3.1 and 3.2 (with Assumption (†), p. 10)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me