对算法的描述

本文首发于知乎(以实现为例)。

1.简介PageRank是Google的宝贝，一种用来对网络中节点的重要性进行排名的算法。为什么叫“PageRank”？一方面，这个算法原本是用来对网页的重要性进行排序的；另一方面，它是由谢尔盖布林和劳伦斯佩奇提出的。这个名字一语双关，特别好。人们对PageRank进行了各种各样的修改，基于相关算法，在推荐、社交网络分析、自然语言处理等领域推出了许多实用的解决方案。，比如用于文本摘要的TextRank算法。PageRank算法是怎么来的？怎么算？

2.场景在我们的日常和生产活动中，经常会遇到对网络中的节点进行排序的任务。例如，互联网中有数以亿计的网页。哪些网页比较重要，值得做医疗广告？学术论文在引用和引证的过程中实现知识的转移，那么哪些论文是学科发展的关键节点呢？在由人组成的社交网络中，有哪些「大人物」？

我们可以用图表来表达这些问题。如图1-1所示，它是一个有四个节点和四条边的有向图。一条边的起点是网页、纸张或人，终点是起点引用的网页、纸张或人。Node1指node0，表示前者从后者获得信息、知识、权力或财富。参考其他节点是有益的；反过来，被别人引用就是在传播好消息。

问题来了。网络中哪个节点的传输功率最强，也就是最重要？

图1-1简单的有向图

3.PageRank思想PageRank认为，一个节点对系统产生影响的结果是与之相连的节点也产生一定的影响。如果图1-1是一个财富分配网络:节点1向其他节点传递财富，节点1接收而不能传播从节点0获得的财富；等一下。节点0的影响力可以通过与之相连的节点1的影响力来衡量。这个套路有点类似于“通过看一个人的朋友来分析他”。

让我们用符号来描述PageRank的思想。假设一个节点的影响力值为。类似地，节点0的影响是，节点1的影响是。这是PageRank的第一个模块。

看起来很简单，但实际上给我们留下了一个问题:每个节点的PR值的计算是依赖的，可以先计算PR(node1)，再计算PR(node0)。也就是说，我们需要先计算所有未被引用节点的PR值(一般默认为1.0)；然后，计算以它们为源的节点的PR值，只连接到源且距离为1；其次，计算所有距离为2且只与PR值相连节点的PR值；直到所有节点都有PR值。这种计算方法复杂，不实用。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 ={}#存储每个节点的信用#添加节点定义add_node(self，node_id):如果node_id不在self . linked _ node _ map:self . linked _ node _ map[node _ id]= set({ })self .PR _ map[node _ id]= 0 else:print( # 34；该节点已经存在 # 34；)#添加一条从节点1到节点2的边。添加新节点def add_link(self，node1，node2):如果node1不在self中。link _ node _ map:self。Add _ node (node2)自身。链接节点映射[节点1]。Add (node2) #为node1添加一个相邻节点，意味着ndoe2引用node #计算pr def get _ pr (self，epoch _ num = 10，d = 0.5): #配置迭代轮数，以及阻尼系数为I in range(epoch _ num):for node in self . pr _ map:#遍历每个节点self。PR_map[node] = (1-d)+d* SUM ([self。自身中临时节点的PR _ map[临时节点]。Linked _ node _ map [node]] #原公式打印(self。PR _ map) edges = [[1，2]，[3，2]，[3，5]，[1，3]，[2，3]，[3，1]，[5，1]]#一个模拟的web链接网络if _ _ name _ = = # 39_ _ main _ _ # 39:graph = graph()for edges in edges:graph . add _ link(edge[0]，edge [1]) graph.get _ pr () 7 .结论PageRank算法可以看作是一个框架，在这个框架上可以做一些修改来解决实际问题。

注:本文为李鹏宇(知乎)个人主页。