本文首发于知乎(实现为例进行具体展示 。
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值为止 。这个计算方法复杂度比较高 ， 不实用 。PageRank算法的第二个模块提供了一个复杂度较低的算法 ， 用来较快地、近似的求出各个节点的PR 。
4. 迭代算法及其冷启动PageRank算法为所有的节点设置了一个初始得分(通常是1.0) ， 然后用前面所述的PR值计算公式更新所有节点的PR值 ， 不断更新 ， 直到PR值收敛 。
【对PageRank算法的简单理解】我们再用符号来表示一下这个操作 。用一个向量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] = 0else: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#计算prdef 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算法可以被看做一个框架 ， 可以在这个基础上做一些变化 ， 进而解决实际问题 。
推荐阅读
- 浩瀚宇宙 对地外文明感兴趣的星座？
- 礼貌在社会上的好处 礼貌对社会的重要性
- 对联上都写些什么
- 兜兜转转还是你星座配对
- 鸡是怎么交配的 鸡是怎么配对的
- 吃什么对头发好
- 谁了解 UFC对冲基金 还有雷恩斯虚拟货币的能说一下吗
- word文档一键对齐下划线 Word文档如何对齐下划线文字
- 怎么处理比熊乱尿
- 蓝牙耳机怎么重新配对 森海塞尔蓝牙耳机怎么重新配对