图神经网络07-PageRank算法

在本节中，我们将探讨PageRank算法，其实这是一个老生常谈的概念或者算法，在这里我们重新温故下这个经典算法。这是一种使用Web Graph中的链接结构按重要性对网页进行排名的方法，这也是Google普及的网络搜索常用算法。 在讨论PageRank之前，让我们先将Web概念化为图，然后尝试使用图论语言来研究其结构。

将Web看做Graph

我们可以将万维网是将网页看成节点，网页之间的超链接看做成边组成的Graph，同时我们可以一下假设：

• 仅考虑静态网页 忽略网络上的暗网（即无法访问的网页，防火墙保护的页面） 所有链接都是可导航的。不考虑交易或者行为链接（例如：喜欢，购买，关注等）。

通过上述方式将万维网概念化为Graph之后，我们看看当前流行的搜索引擎如何使用它。 例如，Google使用爬虫为网页编制索引，这些爬虫通过按广度优先遍历访问链接来浏览网络。 可以通过这种方式遍历的图的还有很多其他例子，比如：科学研究论文之间的引文图，我们写论文的时候参考文献引用；百科全书中的参考文献。

万维网的Graph到底长什么样子

在2000年，AltaVista的创始人进行了一项实验[Graph structure in the Web - ScienceDirect ]，以探索Web的形状。论文抛出了一个问题：给定一个节点

v

,这个节点可以到达哪些节点；有哪些其他节点可以访问到这个节点

v

？

这样会就产出两种类型的节点：

In(v)= \{ w | w \quad can \quad reach \quad v \}

Out(v)= \{ w | v \quad can \quad reach \quad w \}

上面两个集合可以通过运行简单的BFS来遍历得到。例如，在下图中

In(v)= \{ A，B，C，E，G \}

Out(v)= \{ A，B，C，D，F \}

有向图的更多细节

有向图有两种类型：

• 强连通图：任何节点都可以访问到任何其他节点的图。
• 有向无环图（DAG）：在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG, Directed Acyclic Graph）。

任何有向图都可以表示为这两种类型的组合，可以通过以下两个步骤实现：

** 获取有向图中的强连通图** 将SCC合并到超节点中，创建一个新图形G’