37 | 矩阵（上）：如何使用矩阵操作进行PageRank计算？

使用networkx中的pagerank函数,计算出来的数值和直接基于矩阵计算出来的数值有一点点差别,但相对大小还是一样的 import networkx as nx import matplotlib.pyplot as plt # 创建有向图 G = nx.DiGraph() # 添加带权重有向边 G.add_weighted_edges_from([(1, 3, 1), (2, 1, 1), (2, 3, 1), (3, 1, 1), (5, 2, 1)]) # 添加孤立节点 G.add_node(4) # 计算pagerank值 pagerank_list = nx.pagerank(G, alpha=0.85) print("pagerank 值是：", pagerank_list) nx.draw(G, with_labels=True, font_weight='bold') plt.show() pagerank 值是： {1: 0.43042160902192195, 3: 0.43042160902192195, 2: 0.06686758646711714, 5: 0.03614459774451953, 4: 0.03614459774451953}

思考题 https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/37_Matrix2PageRank/lesson37_1.py # 计算前后两次的 PageRank 数值的误差，判断是否需要结束迭代 delta = list(map(abs, (pr/pr_tmp))) # pr_tmp 是前一次的值 delta = abs(np.max(delta) - 1) # 最大误差的百分比 if delta <= delta_threshold: return pr else: continue 经计算，示例最大循环 6 次，迭代结束。 round 6 [[0.46010028 0.03905229 0.46010028 0.02037357 0.02037357]]

茶艺师学编程 可惜我目前还没有能力去跑代码。 但整篇课文消化下来，pagerank这么复杂的函数，用矩阵“嵌套”两层就搞定了……体会到矩阵工具的强大。

以上两个公式在形式上是基本一致的。。。怎么看出是一致的？简化公式和矩阵点乘公式

一直想搞明白pagerank的计算流程，这节课真值

邻接矩阵的行表示每个节点出边，列表示每个节点的入边。行做归一化是为了出边平均分配权重，矩阵的乘法恰好按照入边累加pr值。 随机跳转还是线性关系，依然可以用矩阵处理，这里用到矩阵分块思想。

pagerank的时间复杂度是O( r * n^ 2)，其中，r是指迭代次数。 当数据量达到一定的程度的时候，network联图的建立都无法完成的时候，我们应该如何处理呢？ 这里的大数据量大概是300万条数据的样子。谢谢

Never too old to learn!

思考题： 我尝试改了一下老师的代码，把迭代结束条件改为计算前后两次PageRank向量的差的平均值是否小于指定精度，发现这个迭代过程收敛很快，只用了7轮循环就结束了，程序部分代码如下，不当之处请老师指正： # 采样迭代方式，判断前后两次PageRank向量的差的平均值是否小于指定精度。 pricision = 1e-9 # 设置计算精度 last_pr = None i = 0 while True: # 进行点乘，计算Σ(PR(pj)/L(pj)) pr = np.dot(pr, adj) # 转置保存Σ(PR(pj)/L(pj))结果的矩阵，并增加长度为N的列向量，其中每个元素的值为1/N，便于下一步的点乘。 pr_jump = np.full([N, 2], [[0, 1/N]]) pr_jump[:,:-1] = pr.transpose() # 进行点乘，计算α(Σ(PR(pj)/L(pj))) + (1-α)/N) pr = np.dot(pr_jump, jump) # 归一化PageRank得分，由于计算后pr是列向量，因此需要做转置 pr = pr.transpose() pr = pr / pr.sum() print("round", i + 1, pr) if last_pr is not None: diff = np.average(np.absolute(pr - last_pr)) if diff <= pricision: break last_pr = pr.copy() i += 1 ############程序输出############# round 1 [[0.37027027 0.24864865 0.37027027 0.00540541 0.00540541]] round 2 [[0.46740902 0.02498642 0.46740902 0.02009777 0.02009777]] round 3 [[0.46023676 0.03878962 0.46023676 0.02036842 0.02036842]] round 4 [[0.46010283 0.03904738 0.46010283 0.02037348 0.02037348]] round 5 [[0.46010033 0.0390522 0.46010033 0.02037357 0.02037357]] round 6 [[0.46010028 0.03905229 0.46010028 0.02037357 0.02037357]] round 7 [[0.46010028 0.03905229 0.46010028 0.02037357 0.02037357]]

#上面的代码中pr变值改为pr_tmp #========================== i = 0 errorRate = 0.000001 while (True): # 进行点乘，计算Σ(PR(pj)/L(pj)) pr = np.dot(pr_tmp, adj) # 转置保存Σ(PR(pj)/L(pj))结果的矩阵，并增加长度为N的列向量，其中每个元素的值为1/N，便于下一步的点乘。 pr_jump = np.full([N, 2], [[0, 1 / N]]) pr_jump[:, :-1] = pr.transpose() # 进行点乘，计算α(Σ(PR(pj)/L(pj))) + (1-α)/N) pr = np.dot(pr_jump, jump) # 归一化PageRank得分 pr = pr.transpose() pr = pr / pr.sum() delta = list(map(abs, (pr/pr_tmp))) delta = abs(np.max(delta)-1) if delta <= errorRate: break else: pr_tmp = pr i += 1 continue print('round:', i) print('pr:', pr)