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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
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.
Type de document :
Pré-publication, Document de travail
21 pages. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00778088
Contributeur : Canimogy Cogoulane <>
Soumis le : vendredi 18 janvier 2013 - 16:36:26
Dernière modification le : jeudi 10 mai 2018 - 02:04:58

Lien texte intégral

Identifiants

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

Collections

Citation

Olivier Fercoq. Convergence of Tomlin's HOTS algorithm. 21 pages. 2012. 〈hal-00778088〉

Partager

Métriques

Consultations de la notice

245