介数中心性

简介

介数中心性是一种检测节点对图中信息流影响程度的方法。它常用于查找作为图不同部分之间桥梁的节点。

该算法计算图中所有节点对之间的最短路径。每个节点都会获得一个分数，该分数基于穿过该节点的最短路径数量。更频繁地位于其他节点之间最短路径上的节点将具有更高的介数中心性分数。

介数中心性适用于无权重图或正权重图。Neo4j Snowflake图分析的实现基于Brandes 的无权重图近似算法。该实现需要 O(n + m) 空间，并以 O(n * m) 时间运行，其中 n 是节点数，m 是图中关系数。

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

考量事项和抽样

介数中心性算法计算起来可能非常消耗资源。Brandes 的近似算法为一组源节点计算单源最短路径 (SSSP)。当所有节点都被选作源节点时，算法会产生精确结果。然而，对于大型图来说，这可能导致非常长的运行时间。因此，通过仅计算节点子集的 SSSP 来近似结果会很有用。在 Neo4j Snowflake图分析中，我们将此技术称为抽样，其中源节点集的大小是抽样大小。

在大型图上执行此算法时，有两点需要考虑：

更高的并行度会导致更高的内存消耗，因为每个线程都顺序执行源节点子集的 SSSP。
- 在最坏情况下，单个 SSSP 需要将整个图在内存中复制一份。
更大的抽样大小会带来更准确的结果，但也可能导致更长的执行时间。

分别更改配置参数 concurrency 和 samplingSize 的值有助于管理这些考量事项。

抽样策略

Brandes 定义了几种选择源节点的策略。Neo4j Snowflake图分析的实现基于随机度数选择策略，该策略以与其度数成比例的概率选择节点。此策略背后的想法是，这些节点很可能位于图中的许多最短路径上，因此对介数中心性分数贡献更大。

语法

本节介绍执行介数中心性算法所使用的语法。

运行介数中心性。

CALL Neo4j_Graph_Analytics.graph.betweenness(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);

1	计算池选择器。
2	表引用的可选前缀。
3	项目配置。
4	计算配置。
5	写入配置。

表 1. 参数
名称	类型	默认值	可选	描述
computePoolSelector	字符串	`不适用`	否	用于运行介数中心性作业的计算池选择器。
configuration	映射	`{}`	否	用于图项目、算法计算和结果写回的配置。

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

有关以下项目配置的更多详细信息，请参阅项目文档。

表 2. 项目配置
名称	类型
nodeTables	节点表列表。
relationshipTables	关系类型到关系表的映射。

表 3. 计算配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`'betweenness'`	是	将写回 Snowflake 数据库的节点属性。
samplingSize	整数	`节点计数`	是	用于计算中心性分数的源节点数量。
samplingSeed	整数	`null`	是	用于选择起始节点的随机数生成器的种子值。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将运行无权重计算。

有关以下写入配置的更多详细信息，请参阅写入文档。

表 4. 写入配置
名称	类型	默认值	可选	描述
nodeProperty	字符串	`'betweenness'`	是	将写回 Snowflake 数据库的节点属性。

示例

在本节中，我们将展示在具体图上运行介数中心性算法的示例。目的是说明结果的样式，并提供在实际设置中如何使用该算法的指南。我们将在一个由少数节点以特定模式连接的小型社交网络图上进行演示。示例图如下所示：

以下 SQL 语句将为我们的示例图创建节点和关系数据：

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.USERS (NODEID STRING);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.USERS VALUES
  ('Alice'),
  ('Bob'),
  ('Carol'),
  ('Dan'),
  ('Eve'),
  ('Frank'),
  ('Gale');

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.FOLLOWS (SOURCENODEID STRING, TARGETNODEID STRING, WEIGHT DOUBLE);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.FOLLOWS VALUES
  ('Alice', 'Carol', 1.0),
  ('Bob',   'Carol', 1.0),
  ('Carol', 'Dan',   1.0),
  ('Carol', 'Eve',   1.3),
  ('Dan',   'Frank', 1.0),
  ('Eve',   'Frank', 0.5),
  ('Frank', 'Gale',  1.0);

有了 Snowflake 中的节点和关系表，我们现在可以将其作为算法作业的一部分进行投影。在以下示例中，我们将演示在此图上使用介数中心性算法。

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

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

运行作业

运行介数中心性作业包括三个步骤：项目、计算和写入。

以下将运行介数中心性作业：

CALL Neo4j_Graph_Analytics.graph.betweenness('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'USERS' ],
        'relationshipTables': {
            'FOLLOWS': {
                'sourceTable': 'USERS',
                'targetTable': 'USERS'
            }
        }
    },
    'compute': {
        'mutateProperty': 'score'
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'USERS_CENTRALITY',
        'nodeProperty': 'score'
    }]
});

表 5. 结果
作业 ID	作业开始时间	作业结束时间	作业结果
job_18ec2c6bfa744a9d866acffc86e6ecba	2025-04-29 11:41:43.604000	2025-04-29 11:41:50.077000	{ "betweenness_1": { "centralityDistribution": { "max": 8.000061035156248, "mean": 2.714292253766741, "min": 0, "p50": 3, "p75": 5.0000152587890625, "p90": 8.000045776367188, "p95": 8.000045776367188, "p99": 8.000045776367188, "p999": 8.000045776367188 }, "computeMillis": 12, "configuration": { "concurrency": 2, "jobId": "0705b31c-8c41-4237-a543-5021c1fc675e", "logProgress": true, "mutateProperty": "betweenness", "nodeLabels": [ "" ], "relationshipTypes": [ "" ], "sudo": false }, "mutateMillis": 1, "nodePropertiesWritten": 7, "postProcessingMillis": 27, "preProcessingMillis": 8 }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeMillis": 183, "relationshipCount": 7, "relationshipMillis": 602, "totalMillis": 785 }, "write_node_property_1": { "exportMillis": 2336, "nodeLabel": "USERS", "nodeProperty": "score", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY", "propertiesExported": 7 } }

表 5. 结果

作业 ID

作业开始时间

作业结束时间

作业结果

job_18ec2c6bfa744a9d866acffc86e6ecba

2025-04-29 11:41:43.604000

2025-04-29 11:41:50.077000

 {
  "betweenness_1": {
    "centralityDistribution": {
      "max": 8.000061035156248,
      "mean": 2.714292253766741,
      "min": 0,
      "p50": 3,
      "p75": 5.0000152587890625,
      "p90": 8.000045776367188,
      "p95": 8.000045776367188,
      "p99": 8.000045776367188,
      "p999": 8.000045776367188
    },
    "computeMillis": 12,
    "configuration": {
      "concurrency": 2,
      "jobId": "0705b31c-8c41-4237-a543-5021c1fc675e",
      "logProgress": true,
      "mutateProperty": "betweenness",
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "sudo": false
    },
    "mutateMillis": 1,
    "nodePropertiesWritten": 7,
    "postProcessingMillis": 27,
    "preProcessingMillis": 8
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 7,
    "nodeMillis": 183,
    "relationshipCount": 7,
    "relationshipMillis": 602,
    "totalMillis": 785
  },
  "write_node_property_1": {
    "exportMillis": 2336,
    "nodeLabel": "USERS",
    "nodeProperty": "score",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY",
    "propertiesExported": 7
  }
}

返回的结果包含有关作业执行和结果分布的信息。此外，七个节点中每个节点的中心性分数已写回 Snowflake 数据库。我们可以这样查询：

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY;

显示存储在数据库中的计算结果：

表 6. 结果
节点 ID	分数
Alice	0.0
Bob	0.0
Carol	8.0
Dan	3.0
Eve	3.0
Frank	5.0
Gale	0.0

抽样

介数中心性计算起来可能非常消耗资源。为了解决这个问题，可以使用抽样技术来近似结果。配置参数 samplingSize 和 samplingSeed 用于控制抽样。我们通过将抽样大小设置为二来近似介数中心性，以此在我们的示例图上进行说明。种子值是一个任意整数，使用相同的值将在不同程序运行之间产生相同的结果。

以下将运行一个抽样大小为二的介数中心性作业：

CALL Neo4j_Graph_Analytics.graph.betweenness('CPU_X64_XS', {
    'project': {
        'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
        'nodeTables': [ 'USERS' ],
        'relationshipTables': {
            'FOLLOWS': {
                'sourceTable': 'USERS',
                'targetTable': 'USERS'
            }
        }
    },
    'compute': {
        'mutateProperty': 'score',
        'samplingSize': 2,
        'samplingSeed': 4
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_SAMPLED'
        'nodeProperty': 'score'
    }]
});
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_SAMPLED;

表 7. 结果
节点 ID	分数
Alice	0.0
Bob	0.0
Carol	4.0
Dan	2.0
Eve	2.0
Frank	2.0
Gale	0.0

在这里我们可以看到，'Carol' 节点的得分最高，其次是 'Dan'、'Eve' 和 'Frank' 节点之间的三方平局。我们只从两个节点中进行抽样，其中节点被选中进行抽样的概率与其出度成正比。'Carol' 节点具有最大度数，最有可能被选中。'Gale' 节点的出度为零，非常不可能被选中。其他节点被选中的概率都相同。

通过我们选择的抽样种子 0，我们似乎选择了 'Alice' 和 'Bob' 节点中的一个，以及 'Carol' 节点。我们可以看到，这是因为 'Alice' 和 'Bob' 中的任何一个都会给 'Carol' 节点的得分增加四分，并且 'Alice'、'Bob' 和 'Carol' 中的每一个都会给 'Dan'、'Eve' 和 'Frank' 的得分各增加一分。

为了提高近似的准确性，可以增加抽样大小。实际上，将 samplingSize 设置为图的节点计数（在本例中为七）将产生精确结果。