Mathematics – Optimization and Control
Scientific paper
2011-11-09
Mathematics
Optimization and Control
28 pages, 5 figures
Scientific paper
In the last years, Google's PageRank optimization problems have been extensively studied. In that case, the ranking is given by the invariant measure of a stochastic matrix. In this paper, we consider the more general situation in which the ranking is determined by the Perron eigenvector of a nonnegative, but not necessarily stochastic, matrix, in order to cover Kleinberg's HITS algorithm. We also give some results for Tomlin's HOTS algorithm. The problem consists then in finding an optimal outlink strategy subject to design constraints and for a given search engine. We study the relaxed versions of these problems, which means that we should accept weighted hyperlinks. We provide an efficient algorithm for the computation of the matrix of partial derivatives of the criterion, that uses the low rank property of this matrix. We give a scalable algorithm that couples gradient and power iterations and gives a local minimum of the Perron vector optimization problem. We prove convergence by considering it as an approximate gradient method. We then show that optimal linkage stategies of HITS and HOTS optimization problems verify a threshold property. We report numerical results on fragments of the real web graph for these search engine optimization problems.
No associations
LandOfFree
Perron vector optimization applied to search engines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Perron vector optimization applied to search engines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perron vector optimization applied to search engines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-42899