如何用 Python 实现 PageRank 算法并对网页图节点执行幂迭代收敛计算

如何用 Python 实现 PageRank 算法并对网页图节点执行幂迭代收敛计算【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/PythonTheAlgorithms Python 仓库的 graphs/page_rank.py 给出了一个只用标准库实现的 PageRank 计算从一组网页节点和它们的入链、出链出发反复用幂迭代式更新每个节点的 rank 值直到相邻两轮迭代的差值小于容差即收敛。本文的目标是跑通这个脚本、看懂收敛判定的写法并把page_rank函数复用到自己的网页图数据上。整个文件不依赖任何第三方包运行环境要求见 pyproject.tomlrequires-python 3.14即需要 Python 3.14 及以上版本。文件里与当前任务相关的代码结构打开 graphs/page_rank.py完成幂迭代计算只涉及三块顶部的邻接矩阵graph是脚本的示例输入。文件 docstring 说明该输入图如下矩阵为[[0, 1, 1], [0, 0, 1], [1, 0, 0]]A B C A 0 1 1 B 0 0 1 C 1 0 0行i列j为 1 表示存在从节点i到节点j的边即 A→B、A→C、B→C、C→A 四条边。Node类保存节点名和inbound/outbound两个邻居名称列表并提供add_inbound、add_outbound两个方法__repr__会打印成nodeA inbound[...] outbound[...]的形式脚本用它做输出展示。page_rank(nodes, max_iter100, d0.85, tol1e-8)函数幂迭代的核心逻辑def page_rank(nodes, max_iter100, d0.85, tol1e-8): n len(nodes) ranks {node.name: 1.0 / n for node in nodes} outbounds {} for node in nodes: outbounds[node.name] len(node.outbound) for _ in range(max_iter): dangling_sum sum( ranks[node.name] for node in nodes if outbounds[node.name] 0 ) new_ranks {} for node in nodes: new_ranks[node.name] (1 - d) / n d * ( sum(ranks[ib] / outbounds[ib] for ib in node.inbound) dangling_sum / n ) if sum(abs(new_ranks[k] - ranks[k]) for k in ranks) tol: ranks new_ranks break ranks new_ranks return ranks对照代码可以读出各参数的实际作用max_iter100是迭代次数上限tol1e-8是收敛容差判据是所有节点上新、旧 rank 绝对差之和小于tol时提前breakd0.85是更新公式中入链 rank 贡献部分的加权系数。每轮更新公式为(1 - d) / n d * (入链 rank / 其出链数之和 dangling_sum / n)初始 rank 全部取1/n。没有任何出链的节点dangling 节点不会造成 rank 流失它的 rank 通过dangling_sum / n均匀分摊给每个节点。运行示例脚本在仓库根目录下执行python graphs/page_rank.py脚本通过input(Enter Names of the Nodes: )从标准输入读取节点名以空格分隔。示例图中固定了 3×3 的邻接矩阵main用矩阵的行、列下标直接索引nodes[ri]、nodes[ci]所以输入必须恰好是 3 个名字与矩阵规模一致Enter Names of the Nodes: A B C随后脚本输出两段内容 Nodes 段每个节点的repr用于核对入链、出链是否按矩阵建对 Ranks 段page_rank(nodes)返回的字典键为输入的节点名值为收敛后的 rank 数值形如{A: ..., B: ..., C: ...}。具体数值由迭代过程决定不要把它当成固定预期值但可以核对两点键集与你输入的名字一致以及所有节点 rank 值之和应为 1——这是更新公式保持的总和不变量初始各为1/n每轮更新后总和仍为 1可直接用它自检输出。如果输入的名字数量与矩阵规模不符nodes[ci]的下标访问会直接抛IndexError这是当前脚本对输入规模的唯一约束。验证收敛行为收敛是否发生、迭代了多少轮都由tol和max_iter两个参数控制验证方式与代码中的判定行一一对应收敛判据sum(abs(new_ranks[k] - ranks[k]) for k in ranks) tol。把tol调大例如放宽到1e-4会在更早的迭代轮次停止收敛到的 rank 更粗略调小则更严格。迭代上限max_iter100内未达到tol时循环正常结束返回最后一轮new_ranks函数本身不报错所以“是否真正收敛”需要由你通过调参观察或自行记录迭代次数来判断。默认参数d0.85出现在更新公式的加权位置改变它会影响每轮 rank 变化的幅度与收敛位置。复用到自己的网页图page_rank只接收Node对象列表不依赖那个 3×3 示例矩阵所以可以直接导入使用。下面这个示例完整复用文件中 docstring 给出的 A、B、C 图展示按文件内main相同约定建边并调用计算from graphs.page_rank import Node, page_rank names [A, B, C] nodes [Node(name) for name in names] # graphs/page_rank.py docstring 中的邻接矩阵 # A B C # A 0 1 1 # B 0 0 1 # C 1 0 0 # (i, j) 表示 i - j 的边 edges [(0, 1), (0, 2), (1, 2), (2, 0)] for i, j in edges: nodes[j].add_inbound(names[i]) nodes[i].add_outbound(names[j]) ranks page_rank(nodes, max_iter100, d0.85, tol1e-8) print(ranks)换成自己的网页图时替换names和edges即可建边约定保持为存在i - j时j的inbound记录i、i的outbound记录j与 graphs/page_rank.py 中main里的add_inbound/add_outbound调用方向一致。含 dangling 节点的图也可以直接使用更新公式已对其做均匀分摊处理。适用限制仓库 README.md 明确说明这些实现仅用于学习目的可能不如 Python 标准库的对应实现高效用它验证算法行为可以作为生产环境方案需要自行评估。main的交互入口绑定固定的 3 节点示例矩阵更换图规模时要么修改文件中的graph矩阵要么按上一节直接调用page_rank函数。graphs/tests 目录下没有针对page_rank的单元测试文件验证只能靠脚本输出与上文给出的收敛判据自检。项目目录中该算法的导航入口在 DIRECTORY.md“Page Rank” 条目。【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/Python创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考