Theorem 3.2, p. 11 — under (†) the HITS iterates converge, x* to the principal eigenvector of AᵀA and y* to that of AAᵀ
ProvedKleinbergHITS.Conv.theorem_3_2Let be a directed graph on pages with adjacency matrix ( if page links to page , else ), and let be the authority and hub weight vectors returned by Kleinberg's procedure Iterate: starting from , 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 .
Assume Assumption (†) for and for : for each of these symmetric matrices, the eigenvalue of largest absolute value is simple, nonzero, and strictly larger in absolute value than every other eigenvalue. Then there are vectors such that
and is a principal eigenvector of and is a principal eigenvector of : unit vectors with and .
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 and the bibliographic coupling matrix , so that any eigenvector algorithm computes them.
Formalization Note Theorem 3.2 refers to the limits of Theorem 3.1, so the statement asserts their existence as well. Assumption (†) is the paper's standing assumption; its encoding includes , 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 , is true but not part of the printed theorem and is not asserted.
import Mathlib import Definitions.Def_KleinbergHITS_Conv_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.