✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

PageRank（网页排名）最初是在万维网（WWW）的背景下提出的，它利用 WWW 的链接结构来产生全局、客观的网页“重要性”排名供搜索引擎使用。该算法由 Google 联合创始人 Larry Page 和 Sergey Brin 于 1997-1998 年提出：

• L. Page, S Brin, R. Motwani, T. Winograd, The PageRank Citation Ranking: Bringing Order to The Web (1998)

随着技术的发展与大量关联性数据的产生，PageRank 也被许多其他领域采用。

基本概念

链接结构与 PageRank

在 WWW 中，网页中包含的超文本在网页之间创建链接。每个网页（节点）都可以有一些前链（通过出边连接）和后链（通过入边连接）。在下图中，A 和 B 是 C 的后链，D 是 C 的前链。

不同网页在后链数量方面差异很大。在自然状态下，那些重要、权威或高质量的网页会获得更多或更重要的后链。

PageRank 的核心思想是：一个网页的后链的排名总和越高，则该网页的排名就越高。这同时涵盖了两种情况，一是网页有大量的后链，二是网页的后链尽管数量不多但排名很高。

排名传递

所有网页的排名（分值）是以递归的方式计算的，所有网页的初始排名分值可以是任意的，然后进行迭代计算直至收敛。在每次迭代中，每个网页均匀地将其自身的排名分值传递给其所有的前链；同时，每个网页都从其所有后链获得排名分值。因此，网页 u 在一次迭代后的排名分值为：

其中 B_u 是网页 u 的后链集合。

以下是一组网页间的排名传递达到稳定的状态：

阻尼系数

考虑以下几种类型的网页：

• 没有后链的网页。它们获得的排名是 0，但它们仍需被浏览到。
• 没有前链的网页。它们的排名分值会从系统中消失。
• 对于一组网页，它们只指向组内的网页，而不指向任何组外的网页。

为了克服这些问题，我们引入阻尼系数（Damping Factor），其值介于 0 和 1 之间。它为每个网页提供一个保底排名分值，同时削弱从后链传递过来的排名分值。一次迭代后网页 u 的排名变为：

其中 d 是阻尼系数。例如，当 d 为 0.7 时，如果一个网页从后链接收到的排名总和为 8，则该网页在本轮的排名为 0.7*8 + (1-0.7) = 5.9。

阻尼系数也可以理解为浏览者随机跳转到不是当前网页的前链之一的其他网页的概率。

特殊说明

• 孤点的排名将为 (1-d)。
• 自环边被视为一条入边和一条出边，网页会通过自环边会将一部分排名传递给自身。有大量自环边的图通常需要较多次的迭代才能趋于稳定。

语法

• 命令：algo(page_rank)
• 参数：

示例

示例图如下：

文件回写

algo(page_rank).params({
  init_value: 1,
  loop_num: 50,
  damping: 0.8,
  weaken: 1,
  order: 'desc'
}).write({
    file: {filename: 'rank'}
})

结果：文件 rank

E,3.96235
F,1.61052
N,1.48175
G,1.25663
I,1.25663
B,0.844209
L,0.844209
K,0.702651
M,0.48106
J,0.36
H,0.333333
A,0.333333
C,0.333333
D,0.2

属性回写

algo(page_rank).params({
  loop_num: 50,
  weaken: 1
}).write({
  db:{property: 'PR'}
})

结果：每个节点的排名回写至名为 PR 的点属性下

直接返回

algo(page_rank).params({
  init_value: 1,
  loop_num: 50,
  damping: 0.8,
  weaken: 1,
  order: 'desc',
  limit: 5
}) as PR 
return PR

结果：PR

流式返回

algo(page_rank).params({
  loop_num: 50,
  damping: 0.8,
  weaken: 1,
  order: 'desc',
  limit: 5
}).stream() as PR 
find().nodes({_uuid == PR._uuid}) as nodes
return table(nodes._id, PR.rank)

结果：table(nodes._id, PR.rank)