Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Convergence of Tomlin's HOTS algorithm

Olivier Fercoq 1, 2
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : The HOTS algorithm uses the hyperlink structure of the web to compute a vector of scores with which one can rank web pages. The HOTS vector is the vector of the exponentials of the dual variables of an optimal flow problem (the "temperature" of each page). The flow represents an optimal distribution of web surfers on the web graph in the sense of entropy maximization. In this paper, we prove the convergence of Tomlin's HOTS algorithm. We first study a simplified version of the algorithm, which is a fixed point scaling algorithm designed to solve the matrix balancing problem for nonnegative irreducible matrices. The proof of convergence is general (nonlinear Perron-Frobenius theory) and applies to a family of deformations of HOTS. Then, we address the effective HOTS algorithm, designed by Tomlin for the ranking of web pages. The model is a network entropy maximization problem generalizing matrix balancing. We show that, under mild assumptions, the HOTS algorithm converges with a linear convergence rate. The proof relies on a uniqueness property of the fixed point and on the existence of a Lyapunov function. We also show that the coordinate descent algorithm can be used to find the ideal and effective HOTS vectors and we compare HOTS and coordinate descent on fragments of the web graph. Our numerical experiments suggest that the convergence rate of the HOTS algorithm may deteriorate when the size of the input increases. We thus give a normalized version of HOTS with an experimentally better convergence rate.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-00778088
Contributor : Canimogy Cogoulane <>
Submitted on : Friday, January 18, 2013 - 4:36:26 PM
Last modification on : Thursday, March 5, 2020 - 6:27:48 PM

Links full text

Identifiers

  • HAL Id : hal-00778088, version 1
  • ARXIV : 1205.6727

Collections

Citation

Olivier Fercoq. Convergence of Tomlin's HOTS algorithm. 2012. ⟨hal-00778088⟩

Share

Metrics

Record views

298