中介中心性 (Betweenness Centrality)

简介

介数中心性是一种用于检测节点对图中信息流影响程度的方法。它常用于寻找在图的各部分之间充当桥梁的节点。

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

介数中心性适用于无权重图或具有正权重的图。用于 Snowflake 的 Neo4j 图分析实现基于 Brandes 的近似算法（用于无权图）。对于加权图，则使用多个并发的 Dijkstra 算法。该实现的存储空间需求为 O(n + m)，运行时间为 O(n * m)，其中 n 是图中的节点数，m 是关系数。

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

注意事项与采样

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

在大型图上执行算法时，有两个因素需要考虑：

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

更改配置参数 concurrency（并发性）和 samplingSize（采样大小）的值有助于管理这些考量因素。

采样策略

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

语法

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

运行介数中心性。

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	字符串	`不适用`	否	用于运行介数中心性作业的计算池选择器。
配置	Map	`{}`	否	用于图项目、算法计算和结果回写的配置。

配置映射由以下三个条目组成。

有关下方项目 (Project) 配置的更多详细信息，请参阅作业项目文档。

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

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

有关下方写入 (Write) 配置的更多详细信息，请参阅作业写入文档。

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

示例

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

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

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.USERS (NODEID VARCHAR);
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 VARCHAR, TARGETNODEID VARCHAR, WEIGHT FLOAT);
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。如果您在安装过程中选择了不同的应用程序名称，请将其替换为该名称。

运行作业

运行介数中心性作业涉及三个步骤：投影 (Project)、计算 (Compute) 和写入 (Write)。

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

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

表 5. 结果
JOB_ID	JOB_STATUS	JOB_START	JOB_END	JOB_RESULT
job_18ec2c6bfa744a9d866acffc86e6ecba	SUCCESS	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, "nodeLabels": [ "" ], "relationshipTypes": [ "" ], "resultProperty": "score" } }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeLabels": ..., "nodeMillis": 183, "relationshipCount": 7, "relationshipMillis": 602, "relationshipTypes": ..., "totalMillis": 785 }, "write_node_property_1": { "copyIntoTableMillis": 1765, "nodeLabel": "USERS", "nodeProperty": "score", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY", "rowsWritten": 7, "stageUploadMillis": 1166, "writeMillis": 2336 } }

表 5. 结果

JOB_ID

JOB_STATUS

JOB_START

JOB_END

JOB_RESULT

job_18ec2c6bfa744a9d866acffc86e6ecba

SUCCESS

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,
      "nodeLabels": [
        "*"
      ],
      "relationshipTypes": [
        "*"
      ],
      "resultProperty": "score"
    }
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 7,
    "nodeLabels": ...,
    "nodeMillis": 183,
    "relationshipCount": 7,
    "relationshipMillis": 602,
    "relationshipTypes": ...,
    "totalMillis": 785
  },
  "write_node_property_1": {
    "copyIntoTableMillis": 1765,
    "nodeLabel": "USERS",
    "nodeProperty": "score",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY",
    "rowsWritten": 7,
    "stageUploadMillis": 1166,
    "writeMillis": 2336
  }
}

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

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY;

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

表 6. 结果
NODEID	SCORE
Alice	0
Bob	0
Carol	8
Dan	3
Eve	3
Frank	5
Gale	0

采样

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

以下代码将以采样大小为 2 运行介数中心性作业：

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

表 7. 结果
JOB_ID	JOB_STATUS	JOB_START	JOB_END	JOB_RESULT
job_ef884b37416642ab93ca80e53fb3346a	SUCCESS	2025-06-30 13:33:03.633	2025-06-30 13:33:09.296	{ "betweenness_1": { "centralityDistribution": { "max": 4.000030517578124, "mean": 1.4285736083984375, "min": 0, "p50": 2, "p75": 2, "p90": 4.0000152587890625, "p95": 4.0000152587890625, "p99": 4.0000152587890625, "p999": 4.0000152587890625 }, "computeMillis": 32, "configuration": { "concurrency": 2, "nodeLabels": [""], "relationshipTypes": [""], "resultProperty": "score", "samplingSeed": 4, "samplingSize": 2 } }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeLabels": ..., "nodeMillis": 465, "relationshipCount": 7, "relationshipMillis": 676, "relationshipTypes": ..., "totalMillis": 1141 }, "write_node_property_1": { "copyIntoTableMillis": 1751, "nodeLabel": "USERS", "nodeProperty": "score", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_SAMPLED", "rowsWritten": 7, "stageUploadMillis": 1369, "writeMillis": 4295 } }

表 7. 结果

JOB_ID

JOB_STATUS

JOB_START

JOB_END

JOB_RESULT

job_ef884b37416642ab93ca80e53fb3346a

SUCCESS

2025-06-30 13:33:03.633

2025-06-30 13:33:09.296

 {
"betweenness_1": {
    "centralityDistribution": {
        "max": 4.000030517578124,
        "mean": 1.4285736083984375,
        "min": 0,
        "p50": 2,
        "p75": 2,
        "p90": 4.0000152587890625,
        "p95": 4.0000152587890625,
        "p99": 4.0000152587890625,
        "p999": 4.0000152587890625
    },
    "computeMillis": 32,
    "configuration": {
        "concurrency": 2,
        "nodeLabels": ["*"],
        "relationshipTypes": ["*"],
        "resultProperty": "score",
        "samplingSeed": 4,
        "samplingSize": 2
        }
    },
    "project_1": {
        "graphName": "snowgraph",
        "nodeCount": 7,
        "nodeLabels": ...,
        "nodeMillis": 465,
        "relationshipCount": 7,
        "relationshipMillis": 676,
        "relationshipTypes": ...,
        "totalMillis": 1141
    },
    "write_node_property_1": {
        "copyIntoTableMillis": 1751,
        "nodeLabel": "USERS",
        "nodeProperty": "score",
        "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_SAMPLED",
        "rowsWritten": 7,
        "stageUploadMillis": 1369,
        "writeMillis": 4295
    }
}

表 8. 结果
NODEID	score
Alice	0
Bob	0
Carol	4
Dan	2
Eve	2
Frank	2
Gale	0

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

通过我们选择的采样种子 4，我们似乎选择了“Alice”和“Bob”节点中的任意一个，以及“Carol”节点。我们可以看到，“Alice”或“Bob”中的任何一个都会为“Carol”节点的分数增加 4，并且“Alice”、“Bob”和“Carol”中的每一个都会为“Dan”、“Eve”和“Frank”增加 1。

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

无向图

介数中心性也可以在无向图上运行。为了说明这一点，我们将使用 UNDIRECTED 方向投影我们的示例图。然后，我们可以在无向图上运行介数中心性。算法会自动识别该图是无向的。

在无向图上运行该算法的计算强度大约是有向图的两倍。

以下示例演示了在无向图上运行介数中心性：

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

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_UNDIRECTED;

表 9. 结果
JOB_ID	JOB_STATUS	JOB_START	JOB_END	JOB_RESULT
job_ef884b37416642ab93ca80e53fb3346a	SUCCESS	2025-06-30 13:33:03.633	2025-06-30 13:33:09.296	{ "betweenness_1": { "centralityDistribution": { "max": 9.500061035156248, "mean": 3.000006539481027, "min": 0, "p50": 3, "p75": 5.5000152587890625, "p90": 9.500045776367188, "p95": 9.500045776367188, "p99": 9.500045776367188, "p999": 9.500045776367188 }, "computeMillis": 34, "configuration": { "concurrency": 2, "nodeLabels": [""], "relationshipTypes": [""], "resultProperty": "score" } }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeLabels": ..., "nodeMillis": 204, "relationshipCount": 14, "relationshipMillis": 375, "relationshipTypes": ..., "totalMillis": 579 }, "write_node_property_1": { "copyIntoTableMillis": 1262, "nodeLabel": "USERS", "nodeProperty": "score", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_UNDIRECTED", "rowsWritten": 7, "stageUploadMillis": 1081, "writeMillis": 2622 } }

表 9. 结果

JOB_ID

JOB_STATUS

JOB_START

JOB_END

JOB_RESULT

job_ef884b37416642ab93ca80e53fb3346a

SUCCESS

2025-06-30 13:33:03.633

2025-06-30 13:33:09.296

 {
    "betweenness_1": {
      "centralityDistribution": {
        "max": 9.500061035156248,
        "mean": 3.000006539481027,
        "min": 0,
        "p50": 3,
        "p75": 5.5000152587890625,
        "p90": 9.500045776367188,
        "p95": 9.500045776367188,
        "p99": 9.500045776367188,
        "p999": 9.500045776367188
      },
      "computeMillis": 34,
      "configuration": {
        "concurrency": 2,
        "nodeLabels": ["*"],
        "relationshipTypes": ["*"],
        "resultProperty": "score"
      }
    },
    "project_1": {
      "graphName": "snowgraph",
      "nodeCount": 7,
      "nodeLabels": ...,
      "nodeMillis": 204,
      "relationshipCount": 14,
      "relationshipMillis": 375,
      "relationshipTypes": ...,
      "totalMillis": 579
    },
    "write_node_property_1": {
      "copyIntoTableMillis": 1262,
      "nodeLabel": "USERS",
      "nodeProperty": "score",
      "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_UNDIRECTED",
      "rowsWritten": 7,
      "stageUploadMillis": 1081,
      "writeMillis": 2622
    }
}

中心节点的得分现在略高，因为图中有更多的最短路径，并且这些路径更有可能通过中心节点。“Dan”和“Eve”节点保持与有向情况相同的中心性分数。

表 10. 结果
NODEID	SCORE
Alice	0
Bob	0
Carol	9.5
Dan	3
Eve	3
Frank	5.5
Gale	0

加权图

以下示例演示了使用权重属性运行介数中心性：

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

表 11. 结果
JOB_ID	JOB_STATUS	JOB_START	JOB_END	JOB_RESULT
job_874ffb19764f4876950327c20b960262	SUCCESS	2025-06-30 13:43:25.928	2025-06-30 13:43:31.230	{ "betweenness_1": { "centralityDistribution": { "max": 8.000061035156248, "mean": 2.714290073939732, "min": 0, "p50": 0, "p75": 6, "p90": 8.000030517578125, "p95": 8.000030517578125, "p99": 8.000030517578125, "p999": 8.000030517578125 }, "computeMillis": 37, "configuration": { "concurrency": 2, "nodeLabels": [""], "relationshipTypes": [""], "relationshipWeightProperty": "WEIGHT", "resultProperty": "score" } }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeMillis": 168, "relationshipCount": 7, "relationshipMillis": 392, "totalMillis": 560 }, "write_node_property_1": { "copyIntoTableMillis": 1644, "nodeLabel": "USERS", "nodeProperty": "score", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_WEIGHTED", "rowsWritten": 7, "stageUploadMillis": 1583, "writeMillis": 3472 } }

表 11. 结果

JOB_ID

JOB_STATUS

JOB_START

JOB_END

JOB_RESULT

job_874ffb19764f4876950327c20b960262

SUCCESS

2025-06-30 13:43:25.928

2025-06-30 13:43:31.230

 {
    "betweenness_1": {
      "centralityDistribution": {
        "max": 8.000061035156248,
        "mean": 2.714290073939732,
        "min": 0,
        "p50": 0,
        "p75": 6,
        "p90": 8.000030517578125,
        "p95": 8.000030517578125,
        "p99": 8.000030517578125,
        "p999": 8.000030517578125
      },
      "computeMillis": 37,
      "configuration": {
        "concurrency": 2,
        "nodeLabels": ["*"],
        "relationshipTypes": ["*"],
        "relationshipWeightProperty": "WEIGHT",
        "resultProperty": "score"
      }
    },
    "project_1": {
      "graphName": "snowgraph",
      "nodeCount": 7,
      "nodeMillis": 168,
      "relationshipCount": 7,
      "relationshipMillis": 392,
      "totalMillis": 560
    },
    "write_node_property_1": {
      "copyIntoTableMillis": 1644,
      "nodeLabel": "USERS",
      "nodeProperty": "score",
      "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_CENTRALITY_WEIGHTED",
      "rowsWritten": 7,
      "stageUploadMillis": 1583,
      "writeMillis": 3472
    }
}

表 12. 结果
NODEID	SCORE
Alice	0
Bob	0
Carol	8
Dan	0
Eve	6
Frank	5
Gale	0