PageRank算法应用广泛,但是实际应用场景网络图庞大、复杂,传统算法计算易出现问题
-
第一个问题是基本PageRank算法模型中限制了有向图必须是连通状态的,而在实际问题场景中所建立的大部分网络结构通常并不是强连通,会存在某些未连通的结点没有出链,此时这类结点就被称为悬挂结点,而在算法中随机冲浪者链接到该网页(结点)时,便会产生无法跳出该网页的情况,此时这个网页就如同是一个黑洞,阻碍随机冲浪者访问其他网页的概率机会,最终会导致其他网页的访问概率值全部为0
- 例
-
第二个问题是在实际问题场景中所建立的复杂有向图中会出现闭合的环结构,其不具有向外传播或链接的能力,所以随机冲浪者在网页内的闭环中陷入死循环,使得循环里的网页PageRank概率值不断积累导致过度评价结点的现象产生
- 例
- 实际应用改进
- 问题1(等级泄露):网络中有些结点没有到其他结点的入链链接,在多次迭代后,所有结点的PageRank值都变为0
- 问题2(等级沉没):有向网络中随机冲浪者访问网页链接达成一个闭合环结构时,此时便只有出链而没有入链,进而环内网页的重要性判断概率值出现无限增大
- 所以为了同时解决以上两个问题以适用实际应用场景,Larry Page在原有PageRank基本思想保持不变的基础上,进一步通过添加用户随机访问概率的阻尼系数d,提出了改进后的PageRank随机浏览模型,其中阻尼系数d通常可以经验的取值为0.85(大概率),经改进过后的表达式为: