两种万维网搜索算法的比较

COMPARISON OF TWO WEB SEARCH ALGORITHMS

Google 创始人sergey Brin 和Lawrence Page 把万维网搜索算法PageRank 定义成某个非周期不可约马氏链的唯一平稳分布.本文讨论了万维网搜索算法中使用的两个重要的马氏链-maximal 不可约马氏链和minimal 不可约马氏链-收敛到平稳分布的收敛速度.结果表明,在阻尼因子α>1/2^(1/2)时,maximal 马氏链比minimal 马氏链的收敛速度快.本文也给出了minimal 马氏链k 步转移矩阵的表达式,及其平稳分布关于参数α的各阶导数和Maclaurin 级数展开.

PageRank was defined as the stationary distribution of some aperiodic irreducible Markov chain by Google＇s founders Sergey Brin and Lawrence Page. In this paper, we discuss the convergence rates of two important Markov chains - maximal irreducible Markov chain and minimal irreducible Markov chain - used in web search algorithms. The 1 result show that if the damping factor a 〉 ~, the maximal Markov chain has a faster convergence rate than the minimal Markov chain. We give also the expression of the kth step transition matrix of the minimal Markov chain, and the every order derivative about α of its stationary distribution, as well as the Maclaurin series of this distribution.