对pagerank算法的整理
发布网友
发布时间：2022-11-08 23:11
共1个回答
热心网友
时间：2023-11-14 03:33
2、介绍完了pagerank是一个什么东西后，我们就来介绍一下pagerank如何计算的。
2.1、用个例子来说明下PageRank算法
在网页A中有B、C、D三个链接，在网页B中有A、C两个个链接，在网页C中有D链接，网页D中有A、B两个链接。（可以看出这个图是强链接的，任何一个节点都可以到达另一个节点）。
我们假设每一个链接访问的概率是相同的，为了计算方便我们将每一个网页的PageRank设置为1。
先给出计算公式
PR(pj) 表示网页 pj 的 PageRank 得分，L(pj) 表示网页 pj 的出链接数量，1/L(pj) 就表示从网页 pj 跳转到 pi 的概率。
所以我们来计算第一次迭代后的PR值：
PR(A)=PR(B)/2+PR(D)/2
PR(B)=PR(A)/3+PR(D)/2
PR(C)=PR(A)/3+PR(B)/2
PR(D)=PR(A)/3+PR(C)/1
PR(A)+PR(B)+PR(C)+PR(D)=1
PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294
通过上面的公式在不断的进行迭代，可以得到一个收敛值，大概是在（0.265，0.235，2.206，0.294）附近。
2.2看完公式之后，我们来考虑俩种特殊的情况
2.2.1终止问题
上面过程要满足收敛性，需要具备一个条件：图是强连通的，即从任意网页可以到达其他任意网页。
互联网中存在网页不满足强连通的特性，因为有一些网页不指向任何网页，按照上面公式迭代计算下去，导致前面累计得到的转移概率被清零，最终得到的概率分布向量所有元素几乎都为0。
假设把上面图中C到D的链接丢掉，C变成了一个终止点，得到下面这个图：
转移矩阵M为：
不断迭代，最终得到所有元素都为0。
2.2.2 、陷阱问题
陷阱问题：是指有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：
这种情况下，PageRank算法不断迭代会导致概率分布值全部转移到c网页上，这使得其他网页的概率分布值为0，从而整个网页排名就失去了意义。如果按照上面图则对应的转移矩阵M为：
不断迭代，最终得倒如下结果：
为了解决终止点问题和陷阱问题 ，下面需要对算法进行改进。假设选取下一个跳转页面时，既不选 当前页面 ，也不选 当前网页上的其他链接 ，而是以一定概率跳转到其他不相关网页，那么上面两个问题就能得到很好的解决，这就是 完整 PageRank 算法思想 。
N表示的时网页链接的个数，α表示不进行随机跳转的概率。
利用上面公式继续迭代下去，直到收敛，得到最终rank值。
PageRank 的计算是采样迭代法实现的：一开始所有网页结点的初始 PageRank 值都可以设置为某个相同的数，例如 1，然后我们通过上面这个公式，得到每个结点新的 PageRank 值。每当一张网页的 PageRank 发生了改变，它也会影响它的出链接所指向的网页，因此我们可以再次使用这个公式，循环地修正每个网页结点的值。由于这是一个马尔科夫过程，所以我们能从理论上证明，所有网页的 PageRank 最终会达到一个稳定的数值。整个证明过程很复杂，这里我们只需要知道这个迭代计算的过程就行了。
3、基于本文主题叫做数学建模之美，也是一篇读后感，所以我们还是写一下感受吧。
这个算法的优美之处，就在于巧妙地将网页内容的好坏，根据链接数的形式，用PR值进行了排名，它不仅激发网页越做越好，也促进了各个网页之间的联系。
同时在结构方面，他将一个复杂的问题，进行了简单的类比，用图结构的形式代替链接的形式，用户访问的顺序，也就是节点的走向。所以数学之美就在于他是非常的简单，用简单的原理，向我们展示了一个复杂的问题。
