份子，两者有很大差别。
03
马氏链的应用
PageRank基本思想
1. 对于前者，似乎可用对方的重要性传播过来来刻画。
2. 对于后者，对方的重要性的影响跟对方发出的链接数目(出度)有关，
出度越大, 能分到的越少，因此可以采用（1/出度）进行加权。
03
马氏链的应用
随机冲浪模型
根据上面的思想，对于网页 u, 如果它被多个网页 v 所链接，如果 用pr(u)表示网页 u 的重要性，那么该网页的重要性可以由下面的公式确
03
马氏链的应用
参考文献
1. 钱敏平, 龚光鲁. 应用随机过程教程及在算法和智能计算中的随机模型. 北京： 清华大学出版社, 2004. 2. David W. Mount. Bioinformatics, Sequence and Genome Analysis. Cold Spring Harbor Laboratory Press, 2002. 3. Amy N. Langville，Carl D. Meyer. Deeper Inside PageRank. Internet Mathematics, 2004, 1(3): 335-380.
03
马氏链的应用
句子的平均长度
1. 序例如列为
TGCAATCGGATAACCAAACA
2. 限制性内切酶将序列切成如下片断
TGCAATCGGATAACCAAACA
03
马氏链的应用
句子的平均长度——马氏链
1. 状态集合{A, B, AA} 。 2. xn={原始链上第 n 个位置示从网页 v 发出的网页数目，L(u) 表示所有指向网页 u 的
03
马氏链的应用
随机冲浪模型的迭代计算
上面的公式可以迭代计算
其中
表示从网页 v 发出的网页数目，L(u)表示所有指向网页 u 的
网页。
03
马氏链的应用
随机冲浪模型的迭代计算
1/3 pr=0.35 1/3 1 1/3
pr(u)
3. 例子： TATCAAT
03
马氏链的应用
句子的平均长度——马氏链
转移概率矩阵为
其中
03
马氏链的应用
句子的平均长度——马氏链
1. 不变分布
2. 那么句子的平均长度就是
。
03
马氏链的应用
句子的平均长度——马氏链
1. 由上述方程得
2. 那么句子的平均长度就是
。
03
马氏链的应用
PageRank算法
随机冲浪模型对应的马氏链
03
马氏链的应用
随机冲浪模型对应的马氏链
1. 如果迭代收敛，即有 Pr=Pr· W。 2. Pr就是以 W 为转移矩阵的马氏链的不变分布。
3. 或者说，Pr是矩阵 W 的特征值 1 所对应的特征向量。
03
马氏链的应用
阻尼因子（Damping Factor）
1. 人们在浏览网页时，往往会厌倦了顺着网页所给的链接浏览，而重新 随机打开一个网页。
2. 将这种可能性用一个恒定的概率引入。如果这个概率是0.15, 那么阻
尼因子就是0.85。
03
马氏链的应用
阻尼因子（Damping Factor）
考虑到阻尼因子，新的迭代公式为
DF
1
2
3
…
N 1
N
03
马氏链的应用
说明
1. 阻尼因子引入可以给那些没有被链接的网页一个基准值。 2. 另一方面，阻尼因子也降低了PageRank算法中前期的估计量对当
pr=0.1
1
1/2
1/2
pr=0.25 pr=0.15
03
马氏链的应用
随机冲浪模型对应的马氏链
1. 记行向量 Pr=(pr(1), pr(2), … , pr(D))。 2. 令矩阵
其中网页 v 对应的行中，只有 v 所指向的网页所在的列元素取1/dout(v)，
其他列中元素都为 0。
03
马氏链的应用
1. PageRank基本思想 2. PageRank计算方法
3. PageRank和马氏链
03
马氏链的应用
PageRank基本思想
1. 问题：如何评价网页的重要性。 2. 看该网页被引用(链接)的情况：
•
•
如果该网页被网络大V所链接，那么该网页也比较重要；
如果网页被网络大V所唯一链接，相比于网络大V众多链接中的一
03
马氏链的应用
03
马氏链的应用
句子的平均长度
设DNA序列(由四个字母{A, C, G, T}构成)每个字母的出现是独立同分布 的(记为i.i.d)，每个字母出现的概率分别是PA, PC, PG, PT. 现在有一个特
殊的机器(生物上称之为限制性内切酶)，遇到AA就将序列切断。
问题：这些片断的平均长度是多少？
前估计的影响。
3. 从马氏链的角度来看，加入阻尼因子使得所有的网络节点是互通的，
从而保证了遍历性，以至于不变分布存在。
03
马氏链的应用
总结
1. 食堂人气排行榜可以通过调查得到转移概率，求对应的马氏链的不变分布得到。 2. 马氏链是一类重要的随机过程，完全由初始概率和转移概率矩阵唯一确定；转 移概率矩阵决定了其重要特性（互通性，常返性）；在互通常返下有遍历性定 理，保证了不变分布的存在。 3. 马氏链的平均返回时间来求句子的平均长度；用网页链接确定马氏链，用马氏 链的不变分布为网页排序。