Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/pagerank/ Documentation version: v5.3.2 # PageRank 本文介绍 PageRank 算法，并演示如何用 GQL 实现该算法。 ## 算法介绍 PageRank 算法由 Google 开发，用于对其搜索引擎结果中的网页进行排名。它通过计算指向某个页面的链接数量来确定网页的重要性。此算法假设更重要的网页更有可能收到来自其他网页的引用链接。 每个页面都会被分配一个 PageRank 分数，表示该页面的重要性。某页面的 PageRank 分数是基于指向它的其他页面的分数通过迭代计算得出的。计算页面 PageRank 分数的公式如下： \[ PR(i) = \frac{1 - d}{N} + d \sum_{j \in In(i)} \frac{PR(j)}{Out(j)} \] 其中： - `PR(i)`：页面`i`的 PageRank 分数。 - `d`：阻尼因子，表示用户从当前页面跳转到其他页面的概率。取值范围：[0, 1)。 - `N`：页面总数。 - `In(i)`：链接到页面`i`的页面集合。 - `Out(j)`：页面`j`的出链数量。 关于 PageRank 算法的更多信息，请参见 [PageRank](https://zh.wikipedia.org/wiki/PageRank)。 ## 数据模型 为了用 GQL 实现 PageRank 算法，将基于以下数据模型来创建图类型： - 页面被抽象为人，由类型为`Person`的点表示。 - 页面之间的链接被抽象为人与人之间的关系，由类型为`Knows`的边表示。 该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/pagerank/#1_prepare_graph_data)。 ## 过程实现[]() 为了计算图中所有点的 PageRank 分数，将创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)来实现 PageRank 算法。 该过程的完整定义，请参见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/pagerank/#2_create_a_procedure)。下文将介绍该过程的关键组成部分及其工作原理。 该过程接受以下输入参数： - `damping`：阻尼因子。 - `max_iter`：最大迭代次数。 此外，在过程内部定义了以下变量： | 变量名 | 变量类型 | 描述 | `cur_iter` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前迭代次数。 | `add_constant` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 在每次迭代中给每个点添加的基础分。这样即使没有入边的点也能获得一定的分数。 | `delta` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 在每次迭代中所有点的 PageRank 分数的总变化量。用于判断是否停止迭代。 | `total_nodes` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 图中点的总数。 | `current_score` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点在当前迭代的 PageRank 分数。 | `next_score` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点在下一迭代的 PageRank 分数。 | `out_edge` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点的出边数量。 | `result_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 存储所有点最终的 PageRank 分数的文件。 以下步骤概述了该过程的逻辑： 1. 将每个点的`out_edge`初始化为其出边数量。 2. 将`total_nodes`初始化为图中点的总数。 3. 将`add_constant`设置为基于`damping`和`total_nodes`计算得到的常量。 4. 将每个点的`current_score`初始化为`1.0 / total_nodes`。 5. 开始迭代更新 PageRank 分数。若当前迭代次数超过最大迭代次数（由`max_iter`指定）或达到收敛阈值（`delta`小于等于`0.01`），就停止迭代： 1. 将`delta`重置为`0.0`。 2. 对于每条边，将目标点的`next_score`设置为起始点的`current_score`除以其`out_edge`，再乘以阻尼因子后的值。 3. 对于每个点，将`add_constant`累加到其`next_score`。 4. 计算`delta`，也即所有点的`next_score`与`current_score`的绝对差值之和。 5. 准备下一次迭代，将`current_score`设置为`next_score`，并将`next_score`重置为`0.0`。 6. 迭代次数`cur_iter`加`1`。 6. 在最后一次迭代结束后，将每个点的 ID 和最终的`current_score`导出到`result_file`。 ## 操作步骤 在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。 ### 1. 准备图数据[]() 1. 创建一个与数据模型匹配的图类型。 ```` ''' CREATE GRAPH TYPE IF NOT EXISTS pagerank_graph_type AS { NODE Person (LABEL Person {id INT PRIMARY KEY, name STRING}), EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY()}]->(Person) } ''' ```` 2. 下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/pagerank/`： - [pagerank_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/pagerank/pagerank_node.csv)：点数据。 - [pagerank_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/pagerank/pagerank_edge.csv)：边数据。 查看 CSV 内容 pagerank_node.csv ```` u_id,u_name 1,Alice 2,Bob 3,Charlie 4,David ```` pagerank_edge.csv ```` src_id,dst_id 1,2 2,3 1,4 3,4 4,2 ```` 3. 基于图类型创建一个临时图，并将数据文件加载到临时图中。 ```` CREATE TEMPORARY GRAPH IF NOT EXISTS #pagerank_graph TYPED pagerank_graph_type ```` ```` ''' USE #pagerank_graph IMPORT INTO GRAPH { NODE (v@Person {id: u_id, name: u_name}) FROM DATAFILE { PATH: "file:///examples/algorithms/pagerank/pagerank_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src_id)-[e@Knows{}]->(id: dst_id) FROM DATAFILE { PATH: "file:///examples/algorithms/pagerank/pagerank_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } ''' ```` 导入成功后，在控制台执行以下查询核对点数： ```` ''' USE #pagerank_graph MATCH (n) RETURN count(n) AS node_count ''' ```` `node_count`应为`4`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。 ### 2. 创建过程[]() 创建实现 PageRank 算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/pagerank/#procedure_implement)。 ```` ''' CREATE OR REPLACE PROCEDURE pagerank(damping DOUBLE, max_iter INT) RETURNS () AS { VALUE cur_iter INT64 = 1 VALUE add_constant DOUBLE = 1.0 - damping VALUE delta SumAgg = 1.0 VALUE total_nodes SumAgg = 0 NODE VALUE current_score SumAgg = 0.0 NODE VALUE next_score SumAgg = 0.0 NODE VALUE out_edge SumAgg = 0 FILE result_file {vid INT64, score DOUBLE} = DATAFILE {PATH:"file:///examples/algorithms/pagerank/output", FORMAT:"CSV", INCLUDE_HEADER: true} MATCH (s:Person)-[e:Knows]->(t:Person) PER PATH { SET s.@out_edge += 1 } MATCH (s:Person) PER NODE (s) { SET @total_nodes += 1 } SET add_constant = add_constant / @total_nodes MATCH (s:Person) PER NODE (s) { SET s.@current_score = 1.0 / @total_nodes } LOG_INFO("Start Iteration") WHILE cur_iter <= max_iter AND @delta > 0.01 THEN { LOG_INFO("current iter: ", cur_iter) SET @delta = 0.0 MATCH (s:Person)-[e:Knows]->(t:Person) PER PATH { SET t.@next_score += damping * s.@current_score / s.@out_edge } MATCH (s:Person) PER NODE (s) { SET s.@next_score += add_constant } MATCH (s:Person) PER NODE (s) { SET @delta += abs(s.@next_score - s.@current_score) } MATCH (s:Person) PER NODE (s) { SET s.@current_score = s.@next_score SET s.@next_score = 0.0 } SET cur_iter = cur_iter + 1 } LOG_INFO("Finish Iteration") LOG_INFO("Final @delta: " , @delta) MATCH (s:Person) PER NODE (s) { EXPORT s.id, s.@current_score INTO result_file } } ''' ```` ### 3. 调用过程 调用过程来计算 PageRank 分数。以下示例将阻尼因子设置为`0.85`、最大迭代次数设置为`30`。 ```` USE #pagerank_graph CALL pagerank(0.85, 30) FINISH ```` 此调用将结果写入 CSV，控制台不返回结果表。 返回： 执行日志示例 ```` Log: 2025-09-24T21:19:18.213020 INFO - Start Iteration 2025-09-24T21:19:18.213542 INFO - current iter: 1 2025-09-24T21:19:18.225369 INFO - current iter: 2 2025-09-24T21:19:18.236810 INFO - current iter: 3 2025-09-24T21:19:18.246852 INFO - current iter: 4 2025-09-24T21:19:18.257173 INFO - current iter: 5 2025-09-24T21:19:18.267120 INFO - current iter: 6 2025-09-24T21:19:18.276807 INFO - current iter: 7 2025-09-24T21:19:18.286623 INFO - current iter: 8 2025-09-24T21:19:18.296545 INFO - current iter: 9 2025-09-24T21:19:18.306014 INFO - current iter: 10 2025-09-24T21:19:18.315761 INFO - current iter: 11 2025-09-24T21:19:18.325485 INFO - current iter: 12 2025-09-24T21:19:18.335015 INFO - current iter: 13 2025-09-24T21:19:18.344843 INFO - current iter: 14 2025-09-24T21:19:18.354806 INFO - current iter: 15 2025-09-24T21:19:18.365031 INFO - current iter: 16 2025-09-24T21:19:18.375710 INFO - current iter: 17 2025-09-24T21:19:18.385460 INFO - current iter: 18 2025-09-24T21:19:18.395477 INFO - current iter: 19 2025-09-24T21:19:18.405343 INFO - current iter: 20 2025-09-24T21:19:18.414832 INFO - Finish Iteration 2025-09-24T21:19:18.414987 INFO - Final @delta: 0.00968988 ```` 在宿主机的部署目录下，打开`examples/algorithms/pagerank/output/`中的 CSV 文件。示例内容如下： ```` "vid","score" 1,0.037500000000000006 2,0.32800999035091527 3,0.316308491798278 4,0.3181815178508066 ```` 将结果写入图中 如果需要将 PageRank 结果持久化到图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)： - 先将 PageRank 输出字段导出到表变量（通常为`id`、`score`）。 - 若写入远程图，使用`table_split(...)`分批，并通过`nebula_exec`执行批量`USE + INSERT`。 建议在目标图类型中预留分数字段，例如在`Person`上增加`pagerank_score`属性。