Research On The Hyperlink-based Ranking Algorithms In Web Information Retrieval

With the enormous volume of Web pages in Internet, it comes that Internet users are increasingly using search engines to find specific information. The goal of Web information retrieval is to find all Web pages for a user query in a collection of Web Pages and the task of ranking algorithm is evaluating related Web pages for users. By analysis the structure of hyperlinks, PageRank algorithm which is applied in Google efficiently promote the result of search. Extrapolation Method, composed of Aitken Extrapolation and eigenvalues-based algorithm mainly, can notably reduce iterations commonly .Aitken Extrapolation algorithm use Aitken transform to reduce iterations. Because Aitken transform can not converge in many conditions, this paper presents an improved algorithm FNN-Aitken Extrapolation algorithm by analysis the reason of instability. Instead of calling Aitken transform repeatedly, the improved algorithm call Aitken transform in choosing proper occasion only once. Theoretical analysis and experiment results show that the improved algorithm not only avoid the instability of original algorithm but also reduce iterations compared to Power Method.Compared with Aitken Extrapolation, eigenvalues-based algorithm bypass Aitken transform and perform more effectively than Aitken Extrapolation algorithm theoretically in the process of iterating hyperlink-based Markov matrix. Yet the performance of eigenvalues-based algorithm has a closed relation with d parameter which is chosen with no evident rule. On the other hand, Adaptive method can save running time of iterations by increasing the sparsity of Markov hyperlink matrix. For the purpose of saving running time of iterations, this paper apply Adaptive method to Aitken Extrapolation algorithm and eigenvalues-based algorithm respectively. Experimental results elementarily show that these two new algorithms can speed up the performance of iterations.