数据分析之图算法: 基于Spark和Neo4j

86

｜

第

5

章

d

定义了下一次通过该链接单击的概率。可以将其视为

Web

冲浪者感到无聊并随机切换到另

一个页面的概率。

PageRank

评分反映了通过输入链接访问而非随机访问一个页面的可能性。

没有输出关系的节点（也称

悬挂节点

）或节点分组可以通过拒绝共享而独占

PageRank

得

分，这就是所谓的

等级沉没

。可以把这想象成一个

Web

冲浪者被困在某个页面或者页面子

集中没有出路。另一个难题是由分组中的各节点仅相互指向对方而造成的。当

Web

冲浪者

在节点之间来回跳转时，循环引用会导致其等级升高。这些情况如图

5-12

所示。

等级沉没独占评级得分

A是一个没有输出关系的悬挂节点，隐形传态用于

解决端点问题

C、D和E形成循环引用，没有走出群组的路径。可

借助阻尼系数引入随机节点访问

图 5-12：等级沉没是因为一个节点或节点分组没有输出关系

有两种策略可以避免等级沉没。首先，当到达一个没有输出关系的节点时，

PageRank

算法

假设它到所有节点都有输出关系。穿越这些看不见的关联关系有时也被称为

隐形传态

。其

次，阻尼系数提供了另一种避免等级沉没的方法，相对于直接链接，引入了随机节点访问

的概率。当把

d

设为

0.85

时，完全访问随机节点的概率为

15%

。

虽然原始公式建议阻尼系数取

0.85

，但这起初适用于万维网上链接的幂律分布（大多数页

面的链接很少，少数页面有很多链接）。降低阻尼系数会降低在随机跳转之前沿着长关系

路径前进的可能性，反之将增加节点的前一个节点对其得分和评级的贡献。

如果通过

PageRank

算法得到了意外的结果，那么有必要对该图进行探索性分析，以判断 ...