专栏首页程序生活图神经网络07-PageRank算法

图神经网络07-PageRank算法

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

将Web看做Graph

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

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

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

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

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

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

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

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

有向图的更多细节

有向图有两种类型:

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《数学之美》与算法

    《数学之美》是一本非常好的算法进阶书,它与吴军老师从事的工作领域密切相关,所以工程性很强。半年时间断断续续读完此书,这里做个笔记,也希望能帮助还未读过本书的同学...

    陶辉
  • 机器学习常见算法优缺点总结!

    2、使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题。

    石晓文
  • 机器学习常见算法及优缺点!

    2、使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题。

    Datawhale
  • 神经网络算法

    我们在设计机器学习系统时,特别希望能够建立类似人脑的一种机制。神经网络就是其中一种。但是考虑到实际情况,一般的神经网络(BP网络)不需要设计的那么复杂,不需要包...

    Angel_Kitty
  • 神经网络算法

    20 世纪五、六⼗年代,科学家 Frank Rosenblatt其受到 Warren McCulloch 和 Walter Pitts早期的⼯作的影响,发明了感...

    foochane
  • 神经网络算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明...

    狼啸风云
  • MLK | 机器学习常见算法优缺点了解一下

    2、使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题。

    Sam Gor
  • 从图嵌入算法到图神经网络

    近几年来,伴随着计算机算力的急剧提升,神经网络从历史的尘埃中走出,横扫各大领域,完成一次次颠覆性的创新。依托高度弹性的参数结构,线性与非线性的矩阵变换,神经网络...

    张小磊
  • BP 神经网络算法

    x的值可能为[−∞,+∞],为了方便处理,需要将其压缩到一个合理的范围,还需 这样的激励函数,能够将刚才的区间压缩到[0,1]。

    一个会写诗的程序员

扫码关注云+社区

领取腾讯云代金券