第四章、图上的节点排序（pagerank）

您所在的位置：网站首页 › pagerank排名泄露 › 第四章、图上的节点排序（pagerank）

第四章、图上的节点排序（pagerank）

2023-12-28 17:26| 来源: 网络整理| 查看: 265

图的示例：将Web当作是一个图，其中Web中的网页作为图的节点，Web中的超链接作为图的边。

为什么排序：从直观上看所有的节点并不是同等重要的，我们需要给各个节点的重要性打个分。例如thispersondoesnotexist.com vs. Stanford University 一个是斯坦福大学的网站，一个是个空白网页显然这两个网页不是同等重要的。

如何对节点重要性排序，这肯定要使用图的结构。下面开始我们的节点排序吧！

我们要讲如何使用以下连接分析的方法来计算图中节点的重要性。

网页排序个性化的网页排序重新开始的随机游走边投票（Link As Votes）

边投票：如果一个节点拥有越多的边，那么它就越重要。

我们需要更多的in-coming links还是更多的out-going links？

考虑一个实际情况：

http://www.stanford.edu 拥有23400条in-links，而thispersondoesnotexist.com仅拥有1条。如果按照指入边数量计算，很明显Stanford University 更加重要，这也符合我们原来的设想。

此外，我们还有一个问题，如果只计算in-links那就意味着我们将所有的边都视为都等重要，实际情况不是如此。

重要的节点拥有的out-links更加重要。而重要的in-links指向的节点也更加重要，这就变成了一个递归问题。 PageRank：The ‘flow‘ Model

节点投票的性质：

每个链接的投票与其来源页面的重要性成正比。如果网页 $i$ 的重要性为 $r_i$ 拥有 $d_i$ 个out-links，每一out-links边得到的投票权重为 $r_i/d_i$ 网页 $j$ 的重要性 $r_j$ 是它所有in-links 的和，即 $r_j=\sum_{i\rightarrow j}{\frac{r_i}{d_i}}$

上面的线性方程组，我们最直接的想法是使用高斯消元法来计算，但是此方法的算法时间复杂度为 $O\left( N^2 \right)$ . 我们一般采用迭代的方式进行求解[1]。

PageRank的矩阵形式

随机邻接矩阵（Stochastic adjacency matrix） $M$

我们假设 $j$ 有 $d_j$ 个out-links如果 $j\rightarrow i$ 存在边，那么权重邻接矩阵 $M_{ij}=\frac{1}{d_j}$ 即 $M$ 的列之和为1.Rank Vector $r$ ：An entry per page $r_i$ 是网页 $i$ 的重要性分数 $\sum_i{\boldsymbol{r}_i}=\mathbf{1}$ 我们可以得到下面的等式（r是矩阵M的特征向量

$\boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}, r_j=\sum_{i\rightarrow j}{\frac{r_i}{d_i}}$

下面是一个示例：

将随机游走应用到其中

首先想象一个随机的网络冲浪：

在t时刻，冲浪者在网页 $i$ 处在 $t+1$ 时刻，冲浪者按照网页 $i$ 的out-link随机访问其中一个网页；最终在与网页 $i$ 有关的一些网页 $j$ 处结束；多次重复上述过程

让

$p\left( t \right)$ 是一个概率向量，其中向量元素 $t^{th}$ 表示冲浪者在 $t$ 时刻处在网页 $i$ 的概率。所以说 $p\left( t \right)$ 是一个关于冲浪者在 $t$ 时刻处在各个网页的概率分布。

有了这些概率分布，我们如何进一步研究冲浪者在 $t+1$ 时刻所处的位置？

我们利用邻接矩阵得到下一时刻节点位置的概率 $\boldsymbol{p}(\boldsymbol{t}+\mathbf{1})=\boldsymbol{M}\cdot \boldsymbol{p}(\boldsymbol{t})$ 我们假设随机游走到达一个平稳状态，即 $\boldsymbol{p}(\boldsymbol{t}+\mathbf{1})=\boldsymbol{M}\cdot \boldsymbol{p}(\boldsymbol{t})=\boldsymbol{p}(\boldsymbol{t})$ , $\boldsymbol{p}(\boldsymbol{t})$ 是随机游走的平稳分布。我们原来的排序向量 $r$ 满足 $\boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}$

按照矩阵论中的知识，我们可以将等式 $\boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}$ 解释为， $\boldsymbol{M}$ 的特征向量为 $r$ ,特征值为1。现在需要确定的是，矩阵 $\boldsymbol{M}$ 的特征值是否为1，其中

$\boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}, r_j=\sum_{i\rightarrow j}{\frac{r_i}{d_i}}$

$\boldsymbol{M}$ 的列之和为1，所以 $\boldsymbol{M}$ 的特征值包含1.

综上可以将排序向量 $\boldsymbol{r}$ 解释为随机邻接矩阵 $\boldsymbol{M}$ 的特征值为1的特征向量。我们可以从任一个向量 $u$ 开始， $\boldsymbol{M}(\boldsymbol{M}(...\boldsymbol{M}(\boldsymbol{Mu})))$ 是冲浪者的长期分布。

网页排序=极限分布= $\boldsymbol{M}$ 的主特征向量

注意如果 $r$ 是乘积 $\boldsymbol{M}(\boldsymbol{M}(...\boldsymbol{M}(\boldsymbol{Mu})))$ 的极限，那么 $\boldsymbol{r}$ 满足 $1\cdot \boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}$ 我们可以使用迭代的形式求出特征向量 $\boldsymbol{r}$ ，即给向量 $\boldsymbol{r}$ 随机设置非零值更新参数： $\boldsymbol{r}_{t+1}=\boldsymbol{r}_t-2\boldsymbol{M}^T\boldsymbol{Mr}$ 或者 $\boldsymbol{r}_t_1=\boldsymbol{Mr}_t$ 如果 $\left\| \boldsymbol{r}_{t+1}-\boldsymbol{r}_t \right\| \delta$ 满足，则结束；否则继续重新到2.

网页排序小节：

使用图的边结构测量图中节点的重要性使用随机邻接矩阵建模一个随机网上冲浪者求解等式 $1\cdot \boldsymbol{r}=\boldsymbol{M}\cdot \boldsymbol{r}$ ，其中向量 $\boldsymbol{r}$ 被认为是就是随机游走的平稳分布。

下面讨论这里面涉及的三个问题：

$r_{j}^{(t+1)}=\sum_{i\rightarrow j}{\frac{r_{i}^{(t)}}{d_i}}\quad \,\,\mathrm{equivalently} \quad r=Mr$

使用上述的迭代方式求解向量 $\boldsymbol{r}$ 的算法是否收链？是否收敛到我们想要的？得到的结果是否是合理的？

我们分析一些特殊问题：

一些网页处在dead ends，即没有out-links不指向其他的网页这样的网页会导致重要性“泄露”Spider trap即这样的网页将会吸收所有的重要性 Spider trap

Dead end

解决Spider solution的方法：

在每一次迭代中随机冲浪者有两个选择以概率 $\beta$ 执行自己的一个连接（如果只有一个连接，且连接到自身同样执行）以概率 $1-\beta$ 跳到其他的连接；一般情况下 $\beta$ 的范围为0.8到0.9.最终冲浪者将在几步内跑出spider solution.

解决Dead ends的方法：

Teleport: 以总概率1跑出Dead ends.

我们已经知道可以用Teleport方法解决dead-ends和spider traps的问题。但是我需要考虑为什么这个两个是个问题？以及为什么Teleport可以解决上述问题？

Spider-traps并不是一个问题，但是我们得到的traps PageRank scores并不是我们想要的。解决方法：在有限的步骤中转移至其他点。Dead-ends 是一个问题。矩阵的列并不是列随机的，不满足我们的假设。（这里的列随机（column stochastic）指列之和不等于1）. 解决方法：当无节点可去的时候，通过teleporting使列满足column stochastic.

随机Teleport：

在每一迭代中，随机冲浪者有两个选择（Google’s solution）：

以概率 $\beta$ 停留在原点以概率 $1-\beta$ 跳到其他随机节点处

Google 矩阵G（上述等式的矩阵表示）：

同样，我们拥有一个递归的等式 $\boldsymbol{r}=\boldsymbol{G}\cdot \boldsymbol{r}$ ，在实际中 $\beta =0.8,0.9$

求解 Pagerank小结：

PageRank 求解 $\boldsymbol{r}=\boldsymbol{Gr}$ ，并且我们可以通过迭代高效地计算向量 $\boldsymbol{r}$ 添加随机均匀teleporation能够解决dead-ends和spider traps问题。重新开始的随机游走以及个性化排序

推荐系统示例：

目标：图邻近。

我们应该给接触了物品 $Q$ 的用户推荐哪些物品？直觉上来看，如果物品 $P$ 通过许多相似的用户与 $Q$ 产生联系，那么当另一个用户选择物品 $P$ 的时候，我们就可以推荐 $Q$ .

下面的二部图将是我们讲述推荐系统的基础，现在我们需要判定是 $A, A'$ 关联度高还是 $B, B'$ 关联度高。

Proximity on graph

PageRank:

通过重要性来对节点进行排序以均匀概率传送到网络中的任何节点

Personalized PageRank：

排列节点与传送节点的相似程度

Proximity on graphs

Q: 哪些节点是物品 $Q$ 的对邻近节点？带有Restarts的随机游走传送回初始节点： $\boldsymbol{S}=\{\boldsymbol{Q}\}$ （后面将详细说明这个）

主要思路：随机游走

Idea:

每一个节点都有重要性重要性在所有边缘之间平均分配，并推到相邻的边缘

给定一个请求节点集，模拟一个随机游走：

向随机邻居迈出一步并记录访问(访问计数)以概率alpha在请求节点集中某个节点重新开始这个随机游走最高访问数量的节点表示对这个访问节点有最高的相似性。

随机游走算法：

首先给出访问节点集 $Q$ ，设置好这个alpha，具体算法如下，简单来说就是从query_nodes 得到user的集合，然后从user集合中抽取一个用户，再从用户得到nodes集合；这样循环多次，其中这里还涉及到restart的判断，即取一随机数判断这个数是否小于设定的alpha，以确定是否重新开始游走。

下图是随机游走得到的结果：

为什么这是个好的解？因为这个相似性考虑了：多重连接多重路径直接和非直接路径节点度

网页排序的变体

网页排序传送到其他点节点特定主题网页排名又名个性化网页排序传送到一组特定的节点冲浪者节点可以有不同的概率降落在不同的节点上。带有Restart的随机游走 Topic-Specific PageRank，传送总是到相同的节点; 总结一个图自然表示成一个矩阵我们定义了图上的随机游走过程随机冲浪者通过链接和随机传送来移动随机邻接矩阵（stochastic adjacency matrix）网页排序=冲浪者位置的极限分布表示节点的重要性对应于变换邻接矩阵M的主特征向量

矩阵分解和节点嵌入

Recall：编码器作为嵌入查找

节点嵌入与矩阵分解的联系：

最简单的节点相似：节点 $u,v$ 是相似的，如果他们之间有边相连接。这意味着： $\mathbf{z}_{v}^{\mathrm{T}}\mathbf{z}_u=A_{u,v}$ 表示图邻接矩阵中第 $\left( u,v \right)$ 位置的元素因此 $\mathbf{Z}^{\boldsymbol{T}}\mathbf{Z}=\mathbf{A}$

矩阵分解：

嵌入维度 $\boldsymbol{d}$ ，即 $\boldsymbol{Z}$ 的行数，要比节点 $\boldsymbol{n}$ 的个数小的多。精确的分解 $\mathbf{A}=\mathbf{Z}^{\boldsymbol{T}}\mathbf{Z}$ 通常是不可能的然而，我们可以学习 $\boldsymbol{Z}$ 的近似分解目标： $\mathop {\min} \limits_{\mathrm{Z}}\left\| \mathrm{A}-\boldsymbol{Z}^T\boldsymbol{Z} \right\| _2$ 我们最优化 $\boldsymbol{Z}$ 以至于它能最小化 $\mathrm{A}-\boldsymbol{Z}^T\boldsymbol{Z}$ 的 $L_2$ 范数在第三章中，我们使用了softmax函数而不是 $L_2$ 范数，不过目标是相同的都是 $\boldsymbol{Z}^T\boldsymbol{Z}$ 逼近 $A$ .结论：与边相关的节点相似性的内积解码等价于 $A$ 的矩阵分解。

【本文地址】

第四章、图上的节点排序（pagerank）

第四章、图上的节点排序（pagerank）

今日新闻

推荐新闻