对PageRank算法的简朴明白

时间:2022-08-25 04:05 作者:ob欧宝体育官网入口
本文摘要:本文首发于知乎(https://zhuanlan.zhihu.com/p/81691075),对PageRank,这一重要的网络节点权重盘算方法的思想、细节举行了简要先容,并以其python实现为例举行详细展示。1. 引言PageRank是谷歌的镇店之宝,一种用来对网络中节点的重要性排序的算法。为什么叫“PageRank”呢?一方面这个算法最初是用来对网页重要性举行排序的,另一方面它是Sergey Brin和Lawrence Page提出的。这个名字一语双关,特别好。

ob欧宝体育官网入口

本文首发于知乎(https://zhuanlan.zhihu.com/p/81691075),对PageRank,这一重要的网络节点权重盘算方法的思想、细节举行了简要先容,并以其python实现为例举行详细展示。1. 引言PageRank是谷歌的镇店之宝,一种用来对网络中节点的重要性排序的算法。为什么叫“PageRank”呢?一方面这个算法最初是用来对网页重要性举行排序的,另一方面它是Sergey Brin和Lawrence Page提出的。这个名字一语双关,特别好。

人们对PageRank举行个种种改动,基于相关算法在推荐、社社会网络分析、自然语言处置惩罚等领域推出了许多实用的解决方案,好比用于文本摘要的TextRank算法。PageRank算法是怎么来的呢?怎么盘算?2. 场景我们在生活和生产运动中,经常遇到对网络中节点排序的任务。好比互联网中存在数以亿计的网页,哪些网页比力重要、值得投放医疗广告呢?学术论文在引用和被引用的历程中实现了知识的通报,那么哪些论文是学科生长的关键节点呢?一个由人组成的社会网络中,哪些是“大人物”呢?我们可以把这些问题用图(graph)来表述一下。

如图1-1,是一个有向图,包罗了4个节点,以及4条边。边的起点是一个网页、论文或者人,终点指向的是起点所引用的网页、论文或者人。Node1节点引用node0节点,表现前者从后者获取信息、知识、权力或者财富。

引用其他节点就是获益;反过来讲,被他人引用就是在流传福报。问题来了,网络中哪个节点是流传力最强,也就是最重要的呢?图1-1 一个简朴的有向图3. PageRank的思想PageRank认为,一个节点对系统施加影响的效果,就是与它相连的节点也具有一定的影响力。

如果图1-1是一个财富分发网络:Node1向其他节点通报财富,node1吸收不能搞流传从node0获得的财富;等等。Node0的影响力,可以用与之相连的node1的影响力来怀抱。这个套路有点类似“通过看一小我私家的朋侪来分析这小我私家”。我们用符号来形貌一下PageRank的想法。

假设一个节点的影响力值是。Node0节点的影响力就是,类似的,node1的影响力就是。这是PageRank的第一个模块。

看起来很简朴的样子,实际上给我们留了一个问题:各个节点的PR值盘算是存在依赖的,得先盘算出PR(node1)才气盘算PR(node0)。也就是说,我们需要首先把所有未被引用的节点的PR值算出来(一般默认是1.0);然后把以它们为源头、只和源头相连、距离为1的节点的PR值算出来;接着盘算距离为2、只和已经具有PR值节点相连的,所有节点的PR值;直到所有的节点都有PR值为止。

ob欧宝体育在线官网

这个盘算方法庞大度比力高,不实用。PageRank算法的第二个模块提供了一个庞大度较低的算法,用来较快地、近似的求出各个节点的PR。

4. 迭代算法及其冷启动PageRank算法为所有的节点设置了一个初始得分(通常是1.0),然后用前面所述的PR值盘算公式更新所有节点的PR值,不停更新,直到PR值收敛。我们再用符号来表现一下这个操作。

用一个向量S来存储每个节点的PR值:。表现初始状态下,各个节点的PR值,下角标表现迭代的轮次;表现第0轮时,1号节点的PR值。

假设各个节点的临接矩阵为,那么第一轮迭代的效果是:第二轮迭代的效果是:以此类推,我们可以执行这个迭代历程,直到PR值收敛。一定收敛吗?可以看做一个概率转移矩阵,一连乘以它的效果肯定会收敛。这是可以证明的。5. 伶仃节点的处置惩罚互联网这样的图里存在许多伶仃节点,即不被其他节点引用的网页。

PageRank增加了一个计谋,就是为所有的节点设置一个最小得分,使得搜索用户有一定几率检索到这些网页。详细做法是为PR值的盘算公式增加一个阻尼系数:式中,d是一个取值规模为[0,1]的数,物理寄义是搜索用户随机看到这个网页的概率,实际作用相当于对PR值做了一个平滑、把非伶仃节点的PR值转移给伶仃节点一些。6. 穷人版PageRank算法的Python实现#用于存储图class Graph(): def __init__(self): self.linked_node_map = {}#毗邻表, self.PR_map ={}#存储每个节点的入度 #添加节点 def add_node(self, node_id): if node_id not in self.linked_node_map: self.linked_node_map[node_id] = set({}) self.PR_map[node_id] = 0 else: print("这个节点已经存在") #增加一个从Node1指向node2的边。允许添加新节点 def add_link(self, node1, node2): if node1 not in self.linked_node_map: self.add_node(node1) if node2 not in self.linked_node_map: self.add_node(node2) self.linked_node_map[node1].add(node2)#为node1添加一个毗邻节点,表现ndoe2引用了node #盘算pr def get_PR(self, epoch_num=10, d=0.5):#设置迭代轮数,以及阻尼系数 for i in range(epoch_num): for node in self.PR_map:#遍历每一个节点 self.PR_map[node] = (1-d) + d*sum([self.PR_map[temp_node] for temp_node in self.linked_node_map[node]])#原始版公式 print(self.PR_map)edges = [[1,2], [3,2], [3,5], [1,3], [2,3], [3, 1], [5,1]]#模拟的一个网页链接网络if __name__ == '__main__': graph = Graph() for edge in edges: graph.add_link(edge[0], edge[1]) graph.get_PR()7. 结语PageRank算法可以被看做一个框架,可以在这个基础上做一些变化,进而解决实际问题。

注意:本文为李鹏宇(知乎小我私家主页https://www.zhihu.com/people/py-li-34)原创作品,受到著作权相关法例的掩护。如需引用、转载,请注明泉源信息:(1)作者名,即“李鹏宇”;(2)原始网页链接,即https://zhuanlan.zhihu.com/p/81691075。如有疑问,可发邮件至我的邮箱:lipengyuer@126.com。


本文关键词:对,PageRank,算法,的,简朴,明白,本文,首发,ob欧宝体育官网入口

本文来源:ob欧宝体育官网入口-www.xyseaweed.com