两类网页重要性排序算法的概率对比  

Comparing Two Page Importance Algorithms in Probabilistic View

作　　者：刘玉婷[1] 

机构地区：[1]北京交通大学数学系,北京100044

出　　处：《应用数学学报》2010年第3期432-442,共11页Acta Mathematicae Applicatae Sinica

基　　金：中央高校基本科研业务费专项资金(2009JBM106)资助项目

摘　　要：PageRank和BrowseRank算法是近年来针对网页重要性排序提出的两类典型算法.本文基于更新过程,通过遍历理论分析对比两类网页重要性排序算法,发现它们都利用随机游走的思想来模拟用户在互联网上浏览网页的行为,不同的是前者是离散时间参数的马尔可夫链而后者是连续时间参数的.而且它们所利用的数据也不同,前者基于网络链接图而后者是从真实用户浏览日志中生成的用户浏览图.此外,我们还证明随机游走的平稳分布是对网页重要性的一个合理且可行的衡量方法,并给出目前一些文献中所获得的实验结果的概率解释和意义.There are two classical algorithms to compute page importance recently：PageRank algorithm and BrowseRank algorithm.In this paper,we compare these two algorithms by the theorem of ergodicity of renewal process.We show that both of them use random walk to model the user browsing behaviors on Web,the difference is that the former builds a discrete-time Markov model,while the latter uses a continuous-time Markov model.Moreover, they built their models on different data bases,that is,PageRank model is on the link graph,while BrowseRank model used the user browsing graph created from real browsing log data.We prove also that the stationary distribution of such random walk is a reasonable and feasible method for page importance calculation.Furthermore,we analyze some experimental results observed in correlative literature in probabilistic view.

关 键 词：连续时间马尔可夫过程 平稳分布 遍历定理 BrowseRank算法 PAGERANK算法 

分 类 号：O211[理学—概率论与数理统计]