1，本Notebook介绍 此前介绍了一篇论文范例《基于LDA模型的新冠疫情微博用户主题聚类图谱及主题传播路径研究》，论文提到了使用PageRank做为辅助工具来做确定各个网络社群的意见领袖。 PageRank算法到底是怎样的， 今天这个Notebook，基于简单的测试数据，测试一下PageRank算法计算。PageRank是一个比较成熟的算法了，本Notebook用两种计算方法做实验。 1.1，什么是PageRank PageRank算法最初作为互联网网页重要度的计算方法，1996年由Page和Brin提出，并用于谷歌搜索引擎的网页排序。事实上，PageRank 可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。 假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程。假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank值就是平稳概率。 直观上，一个网页，如果指向该网页的超链接越多，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。PageRank值依赖于网络的拓扑结构，一旦网络的拓扑(连接关系)确定，PageRank值就确定。 PageRank 的计算可以在互联网的有向图上进行，通常是一个迭代过程。先假设一个初始分布，通过迭代，不断计算所有网页的PageRank值，直到收敛为止。 更详细的解释参加知乎文章：PageRank算法详解 1.2，测试数据 我们假定有4网页，相互间的链接关系如下：
对应的节点间关系为： 以有向图的边表示：[("A", "B"), ("A", "C"), ("B", "A"), ("B", "D"), ("C", "B"), ("D", "C")] 以json数据表示：{"A":["B","C"], "B":["A","D"], "C":["B"], "D":["C"]} 1.3，本notebook所做的测试 使用2种方法计算测试模型数据的pagerank: 1. 通过有向图计算pagerank 2. 纯python代码计算pagerank 以下的代码参考了知乎文章：《鼎鼎大名的PageRank算法——理论+实战》 2，引入numpy库 Numpy是一个常用的Python科学技术库，通过它可以快速对数组进行操作，包括形状操作、排序、选择、输入输出、离散傅立叶变换、基本线性代数，基本统计运算和随机模拟等。许多Python库和科学计算的软件包都使用Numpy数组作为操作对象，或者将传入的Python数组转化为Numpy数组，因此在Python中操作数据离不开Numpy。 Numpy的核心是ndarray对象，由Python的n维数组封装而来，但通过C语言预编译相关的数组操作，因此比原生Python具有更高的执行效率，但仍然使用Python语言编码，这样就同时具有简洁的代码和高效的运行速度。ndarry与数组有些区别值得注意，numpy数组中的元素都具有相同的类型，并且在创建时就确定了固定的大小，这与Python数组对象可以动态增长不同。 # coding:utf-8 import numpy as np 3，引入networkx库 NetworkX是一个用Python语言开发的图论与复杂网络建模工具，内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。 Networkx支持创建简单无向图、有向图和多重图（multigraph）；内置许多标准的图论算法，节点可为任意数据；支持任意的边值维度，功能丰富，简单易用。 import networkx as nx 4，第一种方法: 使用纯python代码计算pagerank 4.1，初始化测试数据 针对前面说明的测试模型， 对应的json数据为： {"A":["B","C"], "B":["A","D"], "C":["B"], "D":["C"]} 把测试数据赋值给变量note_json node_json = {"A":["B","C"], "B":["A","D"], "C":["B"], "D":["C"]} 4.2，定义初始化函数nodes2matrix 定义初始化函数nodes2matrix，把通过入参传入的json转换为矩阵，同时为每个节点赋值一个初始的pagerank值 def nodes2matrix(node_json): node2id = {} dim = len(node_json) for id_ , key in enumerate(node_json.keys()): node2id[key] = id_ matrix = np.zeros((dim,dim)) for key in node_json.keys(): nodeid = node2id[key] for neighbor in node_json[key]: neighborid = node2id[neighbor] matrix[neighborid][nodeid] = 1 for i in range(dim): matrix[:,i] = matrix[:,i]/sum(matrix[:,i]) return matrix 4.3，定义计算pagerank的函数 定义计算pagerank值的函数pagerank，此函数有3个入参： 1. 传入测试数据矩阵 2. 迭代次数，缺省为10 3. 阻尼系数：其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率；该数值是根据上网者使用浏览器书签的平均频率估算而得 def pagerank(matrix, iter_ = 10, d=0.85): length = len(matrix[0]) inital_value = np.ones(length)/length pagerank_value = inital_value for i in range(10): pagerank_value = matrix@pagerank_value* d + (1-d)/length print("iter {}: the pr value is {}".format(i, pagerank_value)) return pagerank_value 4.4，计算pagerank 执行步骤为： 1. 调用初始化函数nodes2matrix 2. 调用计算pagerank函数pagerank matrix = nodes2matrix(node_json) print("the matrix is :\n",matrix) print("\n计算得到的pagerank结果：", pagerank(matrix)) 输出结果： the matrix is : [[0. 0.5 0. 0. ] [0.5 0. 1. 0. ] [0.5 0. 0. 1. ] [0. 0.5 0. 0. ]] iter 0: the pr value is [0.14375 0.35625 0.35625 0.14375] iter 1: the pr value is [0.18890625 0.40140625 0.22078125 0.18890625] iter 2: the pr value is [0.20809766 0.30544922 0.27835547 0.20809766] iter 3: the pr value is [0.16731592 0.36254365 0.30282451 0.16731592] iter 4: the pr value is [0.19158105 0.3660101 0.2508278 0.19158105] iter 5: the pr value is [0.19305429 0.33212557 0.28176584 0.19305429] iter 6: the pr value is [0.17865337 0.35904904 0.28364422 0.17865337] iter 7: the pr value is [0.19009584 0.35452527 0.26528305 0.19009584] iter 8: the pr value is [0.18817324 0.34378132 0.2798722 0.18817324] iter 9: the pr value is [0.18360706 0.355365 0.27742088 0.18360706] 计算得到的pagerank结果： [0.18360706 0.355365 0.27742088 0.18360706] 5，第二种方法: 使用有向图计算pagerank 5.1，创建一个有向图 # 创建有向图 G = nx.DiGraph() 5.2，把有向图的各条边的数据赋值给edges变量 # 有向图之间边的关系 edges = [("A", "B"), ("A", "C"), ("B", "A"), ("B", "D"), ("C", "B"), ("D", "C")] 5.3，为有向图添加所有的边 for edge in edges: G.add_edge(edge[0], edge[1]) 5.4，把生成的有向图显示出来做个验证 import matplotlib.pyplot as plt import pylab pos=nx.shell_layout(G) nx.draw(G,pos,with_labels=True, node_color='white', edge_color='red', node_size=800, alpha=1 ) pylab.title('directed graph',fontsize=25) pylab.show()
6，下载本Jupyter Notebook 下载notebook源代码请进：用Python做PageRank算法计算 |
