知识图谱入门学习之路（三）----图算法PageRank

进入到图算法很多人最先接触的算法就是PageRank，PageRank是谷歌最开始创造并应用的，当初主要是为了用来评估构成网络中的每一个节点的重要性。在正式结束PageRank算法之前，我们先了解下有网络图（The web graph）。网络图的特征就是：有向图，存在强连通区。在网络图中，网页作为图中的节点，超链接作为图中的边。In(V)={w| w can re...

幸运的Alina

6179人浏览 · 2020-03-07 21:37:55

幸运的Alina · 2020-03-07 21:37:55 发布

进入到图算法很多人最先接触的算法就是PageRank，PageRank是谷歌最开始创造并应用的，当初主要是为了用来评估构成网络中的每一个节点的重要性。

在正式介绍PageRank算法之前，我们先了解下网络图（The web graph）。网络图的特征就是：有向图，存在强连通区。在网络图中，网页作为图中的节点，超链接作为图中的边。

In(V)={w| w can reach V}

Out(V)={w| V can reach w}

对于上图来说

In(A)={A,B,C,E,G}

Out(A)={A,B,C,D,F}

在有向图中有2中类型，每一种图都可以通过这2种类型进行表示：

1. 强连接：在有向图中，每个节点可以到达图中的任意一个节点。

In(A)=Out(A)={A,B,C,D,E}

2.有向无环图（DAG：directed acydic graph）：图中不存在环，也就是如果从A可以到达B，那么B不能到达A。

强连通分量（strongly connected component）是节点S的集合，具备下面2个特征：

1.在S中的每一对节点都可以互相连通彼此；

2.在这种特性下，S是最大的集合，没有别的集合能够把S包含进去。

每一个节点都是一个SCC

在上述图中强连通分量：{A,B,C,G},{D},{E},{F}

定理：在每一个有向图中，在强连通分量上是一个有向无环图。

对于上图:

In(A)={A,B,C,D,E}

Out(A)={A,B,D,E,F,G,H}

$SCC(A)=In(A)\bigcap Out(A)=\begin{Bmatrix} A,B,D,E \end{Bmatrix}$

上图就是一个巨大的强连通分量，不会存在第二个SCC。

在进行详细介绍PageRank的时候，先来思考下如下问题：

当一个页面有很多超链接的时候，是进来的链接重要还是出去的链接重要？显而易见，是进来的链接重要，那么问题又来了，进来的每一个链接的重要性都是一样的，还是说有所不同，如果不同怎么去衡量。在这里我们采用从更可信的地方出来的链接会更重要。同时网页的重要打分评估也是一个循环递归问题。

PageRank采用流式模型：

重要页面的投票会具有更高的权重。

如果页面 $i$ 的权重为 $r_{i}$ ,有 $d_{i}$ 条出边，那么每一个链接有拥有 $\frac{r_{i}}{d_{i}}$ 票。

页面 $j^{^{'s}}$ 的重要性 $r_j$ 是该页面所有进链投票总和。对节点j 定义 $r_j$ 如下所示：

$r_j= \sum_{i\rightarrow j} \frac{r_i}{d_i}$ 其中 $d_i$ 代表节点 $i$ 的出度

如上图，我们可知

$r_j=\frac{r_i}{3}+\frac{r_k}{4}$

矩阵表达：

设M为随机邻接矩阵，页面 $j$ 有 $d_j$ 条出边，当 $j\rightarrow i$ 就有 $M_{ij}=\frac{1}{d_j}$ ，其中M的每列和为1

秩向量 $r$ :对于页面 $i$ 的每一个进来的页面 $r_i$ 有： $\sum_{i}r_i=1$ ,也可以写作 $r=M\cdot r$

在PageRank中采用了随机游走。

想象上网过程中的随机游走，

1.在任意时刻t，在页面 $i$ 进行浏览；

2.在 $t+1$ 时刻，从页面 $i$ 均匀随机的往外走；

3.直到到了页面 $j$ 链接到了 $I$ ,也就是遍历完；

4.不断地重复上述过程。

采用P(t)来表示在时间t，页面 $i$ 被访问到的概率，用P(t)来表示每个页面的概率分布情况。那么到了 $t+1$ 时刻怎么去判断浏览到哪了，通过根据链接均匀随机的进行游走， $P(t+1)=M\cdot p(t)$ ，假设当随机游走到达了如下状态 $P(t+1)=M\cdot P(t)=P(t)$ 那么可知在随机游走中P(t)是平稳分布的。我们的秩向量r也满足 $r=M\cdot r$ ，同时r在随机游走中也满足平稳分布。

PageRank算法步骤如下：

1.给每个节点一个初始的PR（Page Rank）值；

2.对每一个节点进行计算：

$r_{j}^{t+1} = \sum_{i\rightarrow j}\frac{r_{i}^{t}}{d_i}$ 式中 $d_i$ 代表节点i的出度

直到 $\sum_{i}||r_{i}^{t+1}-r_{j}^{t}||< \varepsilon$

其中 $\varepsilon$ 一般是能容忍的精度，到最后会逐渐收敛于某个值

3.重复迭代

举例如下：

如上图：

	y	a	m
y	1/2	1/2	0
a	1/2	0	1
m	0	1/2	0

下面计算PageRank过程

首先赋予初始PR值：PR(y)=PR(a)=PR(m)=1/3

第一次迭代：

$PR(y)=\frac{1}{2}*PR(y)^0+\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{1}{3}+\frac{1}{2}*\frac{1}{3}=\frac{1}{3}$

$PR(a)=\frac{1}{2}*PR(y)^0+1*PR(m)^0=\frac{1}{2}*\frac{1}{3}+\frac{1}{3}=\frac{3}{6}$

$PR(m)=\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{1}{3}=\frac{1}{6}$

第二次迭代：

$PR(y)=\frac{1}{2}*PR(y)^0+\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{1}{3}+\frac{1}{2}*\frac{3}{6}=\frac{5}{12}$

$PR(a)=\frac{1}{2}*PR(y)^0+1*PR(m)^0=\frac{1}{2}*\frac{1}{3}+\frac{1}{6}=\frac{1}{3}$

$PR(m)=\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{3}{6}=\frac{3}{12}$

第三次迭代：

$PR(y)=\frac{1}{2}*PR(y)^0+\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{5}{12}+\frac{1}{2}*\frac{1}{3}=\frac{9}{24}$

$PR(a)=\frac{1}{2}*PR(y)^0+1*PR(m)^0=\frac{1}{2}*\frac{5}{12}+\frac{3}{12}=\frac{11}{24}$

$PR(m)=\frac{1}{2}*PR(a)^0=\frac{1}{2}*\frac{1}{3}=\frac{1}{6}$

通过不断迭代直至收敛到

PR(y)=6/15

PR(a)=6/15

PR(m)=3/15

上面介绍完PageRank的计算过程，下面有三个问题需要思考：第一，是否具有覆盖性；第二，覆盖的值是否是我们想要的；第三，结果分值是合理的吗。

通过实践会发现PageRank在实际中存在如下两个问题：

1.有些页面是死胡同，只有进去的链接，它自身没有对外的链接，这样的页面会导致重要性泄露；

2.蛛网陷阱（所有的出链都是在一个group中）最终会吸收所有的重要性。

举例蛛网陷阱：

如上图所示：

$r_{j}^{t+1} = \sum_{i\rightarrow j}\frac{r_{i}^{t}}{d_i}$

iteration	0	1	2	3
$r_a$	1/2	1	1	1
$r_b$	1/2	0	0	0

谷歌对于蛛网陷阱的解决方法就是：在每一个步，随机浏览有2中选择

1.在可能性为 $\beta$ ，随机跟一个链接出去

2.在可能性为 $1-\beta$ ,调到一个随机页面；通常 $\beta$ 的取值在0.8到0.9之间。

关于死胡同解决方法为：teleport

	y	a	m
y	1/2	1/2	0
a	1/2	0	0
m	0	1/2	0

变成

	y	a	m
y	1/2	1/2	1/3
a	1/2	0	1/3
m	0	1/2	1/3

最终的PageRank公式为：

$r_j=\sum_{i\rightarrow j}\beta\frac{r_i}{d_i}+(1-\beta)\frac{1}{n}$

好了，关于PageRank的介绍先说这么多，后续再聊！

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

魔乐社区

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

魔乐社区

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模