概述
PageRank(网页排名)算法是在有向图中,将点的分值沿有向边的方向进行传递,直至得到全图收敛的分值分布的一种迭代算法,其核心思想是“后链越多或越重要的网页也就越重要”。该算法是由 Google 创始人 Larry Page 和 Sergey Brin 于 1997~1998 年提出的,用于计算网页的受欢迎程度和重要性,从而为搜索结果的排名提供依据。随着技术的发展与大量关联性数据的产生,PageRank 的使用也衍生到了众多领域。
ArticleRank(文章排名)是 PageRank 的一个引申应用。Ultipa 的 PageRank 算法可通过修改参数配置项,指定计算 PageRank 或 ArticleRank。
算法的相关资料如下:
- L Page, S Brin, R. Motwani, T. Winograd, The PageRank Citation Ranking: Bringing Order to The Web (1998)
- J. Li, P. Willett, ArticleRank: a PageRank-based Alternative to Numbers of Citations for Analysing Citation Networks (2009)
基本概念
前、后链
某点的一步邻居如果与该点的出边相连,则称为该点的前链;相反地,如果与该点的入边相连,则称为该点的后链。当节点代表网页时,节点的前链即为该网页所引用的网页,后链则代表那些引用了该网页的网页。
PageRank
在 PageRank 算法中,所有节点都被分配一个初始分值;每个节点的分值会被节点的所有出边平分,并传递给节点的各个前链节点;同时,该节点会接收从各个后链传来的分值,这些收到的分值总和即为该节点在本轮传递中的得分:
上式中,节点 j
为节点 i
的任意一个后链,D(j)
为 j
的出度。
ArticleRank
出版物间的引用和一般网页间的引用非常类似,但也不乏差异性,比如一份出版物不可能引用自身、两份出版物不可能相互引用以及已出版刊物中的引用情况不会改变等。一张出版物引用图具有如下特点:节点不会有自环边,一个节点不会同时作为某点的前链和后链,节点的前链(出度)不变等。
与 PageRank 相比,Ultipa 的 ArticleRank 在将节点的分值进行平分时,使用的不是该节点的出度(出边的条数),而是“该节点的出度与全图节点出度平均值的和”(与 ArticleRank 原文亦有差别)。直观地看,这一改动将大大削弱出度远低于全图出度均值的节点的分值传递能力:
上式中,D(avg)
为全图节点出度的平均值。
一张理想的出版物引用图中,不会有环路存在,因此全图的总分值会随着传递轮数的增加而减少,如果不引入阻尼系数的话,ArticleRank 的分值传递不会达到稳定。
阻尼系数
在 PageRank 算法中,考虑那些没有被任何站点引用的网页(入度为 0、无后链的节点),比如那些孤点网页,它们接收到的分值永远是 0,但在真实网络中,它们仍然需要被浏览到。再考虑那些没有引用任何其它网站的网页(出度为 0、无前链的节点),整个图的分值传递不应该因为这些节点的分值流失而变得毫无意义。
为修复上述两种情况以及处理 ArticleRank 的无法收敛的问题,引入阻尼系数,即一个 0 到 1 之间的数值,让每个点先获得一个基础分,再削弱它们从后链得到的分值(如有)。以 PageRank 为例,当阻尼系数为 0.7
时,每个点都会得到 1 - 0.7 = 0.3
的基础分,而每个点从其后链接收到的总分值,以某点将要接收的 8
为例,将被削弱至 8 * 0.7 = 5.6
,两部分相加即为该点本轮的得分:0.3 + 5.6 = 5.9
。
如果用 c
表示阻尼系数,则每轮传递后节点 i
的分值为:
Ultipa 同时支持 PageRank 和 ArticleRank 两种分值计算方法,可通过算法参数进行配置。
在算法开始时,根据算法参数设置所有点的初始分值;在每轮迭代中,为每个节点计算其将要获得的分值并进行更新。按此规则循环迭代直至全图节点的分值不再改变,或迭代轮数达到限制。
特殊处理
孤点、不连通图
由于阻尼系数 c
的引入,孤点始终将获得 1-c
的分值(初始状态除外)。
不连通图的各个连通分量之间没有分值传递,各个连通分量分别在各自内部达到分值传递的稳定状态。
自环边
本算法中,每条自环边都是一个有效的出度和一个有效的入度,即自环边会将一部分分值传递给该点自身,有自环边的图在执行本算法时通常需要较多的迭代次数才能趋于稳定。
有向边
本算法中的节点的分值是基根据有向边的方向进行分割及传递的。
结果和统计值
以下面的出版物引用关系图为例,运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.8,采用 ArticleRank 分值计算方法,迭代 5 次:
算法结果:为每个点计算分值,根据算法执行方式,返回 _id
、rank
两列或 _uuid
、rank
两列
_uuid | _id | rank |
---|---|---|
7 | book7 | 0.20000000 |
2 | book2 | 0.20000000 |
1 | book1 | 0.20000000 |
3 | book3 | 0.20000000 |
4 | book4 | 0.42830801 |
6 | book6 | 0.31992599 |
5 | book5 | 0.37592599 |
算法统计值:无
命令和参数配置
- 命令:
algo(page_rank)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
init_value | float | 0.2 | > 0 | 初始分值 |
loop_num | int | 5 | >= 1 | 算法迭代的轮数 |
damping | float | 0.8 | 0~1 | 阻尼系数,即用户继续停留在当前页面进行浏览的概率 |
weaken | int | 1 | 1 或 2 | 1 或忽略代表计算 PageRank,2 代表计算 ArticleRank |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC 或 DESC,大小写不敏感 | 对返回结果进行排序;忽略表示不排序 |
示例:运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.8,采用 ArticleRank 分值计算方法,迭代 5 次 ,返回分值最高的 3 个结果
algo(page_rank).params({
init_value: 1,
loop_num: 5,
damping: 0.8,
weaken: 2,
limit: 3,
order: "desc"
}) as rank return rank
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,rank |
示例:运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.5,采用 PageRank 分值计算方法,迭代 5 次,将算法结果回写至名为 ranking 的 CSV 文件
algo(page_rank).params({
init_value: 1,
loop_num: 5
}).write({
file:{
filename: "ranking.csv"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | rank |
点属性 | / |
示例:运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.5,采用 PageRank 分值计算方法,迭代 5 次,将算法结果回写至名为 score 的点属性
algo(page_rank).params({
init_value: 1,
loop_num: 5
}).write({
db:{
property: "score"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其分值 | _uuid , rank |
示例:运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.8,采用 ArticleRank 分值计算方法,迭代 5 次,将算法结果定义为别名 rank 并返回
algo(page_rank).params({
init_value: 1,
loop_num: 5,
damping: 0.8,
weaken: 2
}) as rank return rank
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其分值 | _uuid , rank |
示例:运行 PageRank 算法,所有节点初始分值为 1,阻尼系数为 0.8,采用 PageRank 分值计算方法,迭代 5 次,返回分值最高的 10 个节点的 ID 及其分值
algo(page_rank).params({
init_value: 1,
loop_num: 5,
limit: 10,
order: "desc"
}).stream() as rank
find().nodes({_uuid == rank._uuid}) as nodes
return table(nodes._id, rank.rank)
实时统计
算法无统计值。