Comparison of Three Web Search Algorithms

Abstract In this paper we discuss three important kinds of Markov chains used in Web search algorithms-the maximal irreducible Markov chain, the minimal irreducible Markov chain and the middle irreducible Markov chain. We discuss the stationary distributions, the convergence rates and the Maclaurin series of the stationary distributions of the three kinds of Markov chains. Among other things, our results show that the maximal and minimal Markov chains have the same stationary distribution and that the stationary distribution of the middle Markov chain reflects the real Web structure more objectively. Our results also prove that the maximal and middle Markov chains have the same convergence rate and that the maximal Markov chain converges faster than the minimal Markov chain when the damping factor . Supported by the National Natural Science Foundation of China (No.10371034).