PageRank

简介

PageRank 算法根据传入关系的数量和相应源节点的重要性来衡量图中每个节点的重要性。粗略地说，其基本假设是，一个页面的重要性仅取决于链接到它的页面的重要性。

PageRank 在原始的 Google 论文中被引入，它是一个解决以下等式的函数

page rank formula

其中，

  • 我们假设页面 A 有页面 T1 到 Tn 指向它。

  • d 是一个阻尼因子，可以在 0（包含）到 1（不包含）之间设置。它通常设置为 0.85。

  • C(A) 被定义为从页面 A 出去的链接数量。

此等式用于迭代更新候选解并得出同一等式的近似解。

有关此算法的更多信息，请参阅

注意事项

使用 PageRank 算法时需要注意以下几点

  • 如果一组页面内部没有指向该组外部的关系，则该组被视为蜘蛛陷阱（spider trap）。

  • 当页面网络形成无限循环时，可能会出现排名陷阱（rank sink）。

  • 当页面没有传出关系时，会出现死胡同（dead-ends）。

改变阻尼因子有助于解决上述所有问题。这可以解释为网页冲浪者有时会跳转到随机页面，从而避免陷入陷阱的概率。

语法

本节介绍执行 PageRank 算法所使用的语法。

运行 PageRank。
CALL graph.page_rank(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);
1 计算池选择器。
2 表引用的可选前缀。
3 项目配置。
4 计算配置。
5 写入配置。
表 1. 参数
名称 类型 默认值 可选 描述

computePoolSelector

字符串

不适用

否

用于运行 PageRank 作业的计算池选择器。

configuration

映射

{}

否

图项目、算法计算和结果回写的配置。

配置映射包含以下三个条目。

有关以下项目配置的更多详细信息，请参阅项目文档。
表 2. 项目配置
名称 类型

nodeTables

节点表列表。

relationshipTables

关系类型到关系表的映射。
表 3. 计算配置
名称 类型 默认值 可选 描述

mutateProperty

字符串

'pageRank'

是

将回写到 Snowflake 数据库的节点属性。

dampingFactor

浮点数

0.85

是

PageRank 计算的阻尼因子。必须在 [0, 1) 范围内。

maxIterations

整数

20

是

PageRank 运行的最大迭代次数。

tolerance

浮点数

0.0000001

是

迭代之间分数的最小变化。如果所有分数的变化都小于容差值，则结果被认为是稳定的，算法将返回。

relationshipWeightProperty

字符串

空

是

用作权重的关系属性名称。如果未指定，算法将运行非加权模式。

sourceNodes

节点/数字或列表或成对列表

[]

是

用于计算个性化 PageRank 的节点、节点 ID 或节点-偏差对。要为不同的源节点使用不同的偏差，请使用以下语法：[[nodeId1, bias1], [nodeId2, bias2], …​]。

scaler

字符串或映射

无

是

应用于最终分数的缩放器名称。支持的值包括 None、MinMax、Max、Mean、Log 和 StdScore。要应用特定于缩放器的配置，请使用映射语法：{scaler: 'name', …​}。
有关以下写入配置的更多详细信息，请参阅写入文档。
表 4. 写入配置
名称 类型 默认值 可选 描述

nodeLabel

字符串

不适用

否

内存中图中要写入节点属性的节点标签。

nodeProperty

字符串

'pageRank'

是

将回写到 Snowflake 数据库的节点属性。

outputTable

字符串

不适用

否

Snowflake 数据库中写入节点属性的表。

示例

本节将展示在具体图上运行 PageRank 算法的示例。目的是说明结果的样式，并提供在实际环境中如何使用算法的指南。我们将在一个由少数节点以特定模式连接的小型 Web 网络图上进行此操作。示例图如下所示

Visualization of the example graph
以下 SQL 语句将在 Snowflake 数据库中创建示例图表
CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.PAGES (NODEID STRING);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PAGES VALUES
  ('Home'),
  ('About'),
  ('Product'),
  ('Links'),
  ('Site A'),
  ('Site B'),
  ('Site C'),
  ('Site D');

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.LINKS (SOURCENODEID STRING, TARGETNODEID STRING, WEIGHT DOUBLE);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.LINKS VALUES
  ('Home',    'About',   0.2),
  ('Home',    'Links',   0.2),
  ('Home',    'Product', 0.6),
  ('About',   'Home',    1.0),
  ('Product', 'Home',    1.0),
  ('Site A',  'Home',    1.0),
  ('Site B',  'Home',    1.0),
  ('Site C',  'Home',    1.0),
  ('Site D',  'Home',    1.0),
  ('Links',   'Home',    0.8),
  ('Links',   'Site a',  0.05),
  ('Links',   'Site B',  0.05),
  ('Links',   'Site C',  0.05),
  ('Links',   'Site D',  0.05);

此图表示八个相互链接的页面。每个关系都有一个名为 weight 的属性，它描述了关系的重要性。

运行作业

运行 PageRank 作业涉及三个步骤：项目、计算和写入。

要运行查询，需要为应用程序、您的消费者角色和您的环境设置必要的权限。有关此内容的更多信息，请参阅入门页面。

我们还假设应用程序名称是默认的 Neo4j_Graph_Analytics。如果您在安装过程中选择了不同的应用程序名称，请将其替换为该名称。

以下将运行一个 PageRank 作业
CALL Neo4j_Graph_Analytics.graph.page_rank('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'PAGES' ],
        'relationshipTables': {
            'LINKS': {
                'sourceTable': 'PAGES',
                'targetTable': 'PAGES'
            }
        }
    },
    'compute': {
        'mutateProperty': 'score'
    },
    'write': [{
        'nodeLabel': 'PAGES',
        'outputTable': 'PAGES_CENTRALITY',
        'nodeProperty': 'score'
    }]
});
表 5. 结果
作业 ID 作业开始时间 作业结束时间 作业结果

job_c755f1e112164f78b7054d162dc4aab4

2025-04-29 15:55:58.260000

2025-04-29 15:56:04.730000

 
 {
    "page_rank_1": {
      "centralityDistribution": {
        "max": 3.215682983398437,
        "mean": 0.9612393379211426,
        "min": 0.32785606384277344,
        "p50": 0.32785606384277344,
        "p75": 1.0542736053466797,
        "p90": 3.2156810760498047,
        "p95": 3.2156810760498047,
        "p99": 3.2156810760498047,
        "p999": 3.2156810760498047
      },
      "computeMillis": 73,
      "configuration": {
        "concurrency": 2,
        "dampingFactor": 0.85,
        "jobId": "e692cccc-34a9-4b9b-b41f-6b9c39530e7f",
        "logProgress": true,
        "maxIterations": 20,
        "mutateProperty": "score",
        "nodeLabels": [
          "*"
        ],
        "relationshipTypes": [
          "*"
        ],
        "scaler": "NONE",
        "sourceNodes": [],
        "sudo": false,
        "tolerance": 1.000000000000000e-07
      },
      "didConverge": false,
      "mutateMillis": 4,
      "nodePropertiesWritten": 8,
      "postProcessingMillis": 34,
      "preProcessingMillis": 10,
      "ranIterations": 20
    },
    "project_1": {
      "graphName": "snowgraph",
      "nodeCount": 8,
      "nodeMillis": 326,
      "relationshipCount": 14,
      "relationshipMillis": 470,
      "totalMillis": 796
    },
    "write_node_property_1": {
      "exportMillis": 2029,
      "nodeLabel": "PAGES",
      "nodeProperty": "score",
      "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PAGES_CENTRALITY",
      "propertiesExported": 8
    }
  }

返回的结果包含作业执行和结果分布的信息。中心性分布直方图可用于检查计算出的分数或执行归一化。此外，七个节点中每个节点的中心性分数都已回写到 Snowflake 数据库。我们可以这样查询它

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PAGES_CENTRALITY;
表 6. 结果
节点 ID 分数

主页

3.215681999884452

关于

1.0542700552146722

产品

1.0542700552146722

链接

1.0542700552146722

站点 A

0.3278578964488539

站点 B

0.3278578964488539

站点 C

0.3278578964488539

站点 D

0.3278578964488539

上述查询以“非加权”模式运行 PageRank 算法，并且返回的分数未标准化。

© . All rights reserved.