《大规模分布式计算深入解析》5.2 PageRank:幂等收敛的迭代账本

PageRank 用 damping 0.85 的迭代账本收敛:三角形图 rank 均匀 1/3、总和 1,悬挂节点重分布仍保总和 1,20 轮与 100 轮差 < 1e-9。

幂等收敛的迭代账本

PageRank 每轮把 rank 沿出边分摊、按 damping 折减并回注基础分。结果不依赖初始值,只依赖图结构,因此幂等收敛。

公式与核算

三角形图三个顶点互相指向,damping 0.85、20 轮后 rank 均匀 1/3,无悬挂节点时总和恒为 1(用例 45-47)。链式图 0→1→2 中 rank 沿传递方向递增:rank2 > rank1 > rank0,被指向越多聚集越多(用例 48)。

悬挂节点与收敛

出度为 0 的悬挂节点吸收 rank 而不释放,直接求和会漏分。重分布把漏出的分加回各顶点,总和仍为 1(用例 49)。收敛判据看轮间差:三角形图 20 轮与 100 轮差 < 1e-9,已收敛(用例 56)。

对齐卷十:打分迭代

卷十的检索打分是文档侧迭代,这里是顶点侧迭代。同样的账本要点:每轮计算量 ∝ 边数、消息数 = 边数、跨区边决定通信量。

验证

从卷十一实验包 解包,用 algo 用例 45、46 验证三角形图 rank 均匀 1/3;用例 47、49 验证有无悬挂节点 rank 总和都为 1;用例 48 验证链式图 rank 递增;用例 56 验证 20 轮与 100 轮差 < 1e-9。原生探针 neo4j-probe.sh 手写 Cypher PageRank 三角图一轮,rank 保持均匀 0.3333,与用例 45-46 公式一致。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图