Spanner Graph 算法目录

Spanner Graph 与 Google 研究 Graph Mining 密切合作，提供了一套算法，可满足以下应用场景的图分析需求：

中心性

中心性算法会根据节点在图中的结构重要性对节点进行排名。 它可以帮助您识别金融科技中的欺诈性账号、社交图谱中的网红、电信网络中的关键路由器等。

PageRank

PageRank 按重要性对节点进行评分。如果许多其他重要节点都链接到某个节点，则该节点被视为更重要。该算法会模拟在图中的随机游走。在此随机游走中访问频率更高的节点被认为更重要。如需了解算法详情，请参阅网页排名。

函数签名

PageRank(input_parameters) YIELD node, score

输入参数

所有通用输入参数以及：

名称 类型 必需 默认 说明
source_nodes 图表节点数组 否 （无） 如果存在，则表示个性化 PageRank 的来源。
damping_factor 双精度 否 0.85 在任何给定的迭代中，算法选择遍历当前节点的某个出边的概率。必须介于 [0, 1) 之间。
max_iterations 整数 否 10 算法的最大迭代次数。必须为正值。 迭代次数越多，结果往往越精确，但运行时间也会更长。
approx_precision 双精度 否 1e-2 算法的近似精度阈值。必须为非负数。值越小，结果往往越精确，但运行时间也会更长。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图中的节点。
得分 FLOAT64 节点的 PageRank 得分。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL PageRank(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    source_nodes => ARRAY {
                      MATCH (n:Account {id:7})
                      RETURN n
                    }
  ) YIELD node, score
RETURN node.id, score;

BetweennessCentrality

BetweennessCentrality 用于衡量某个节点位于其他节点对之间的最短路径上的频率。介数中心性较高的节点通常充当连接图不同部分的关键桥梁。如需了解算法详情，请参阅中介中心性。

函数签名

BetweennessCentrality(input_parameters) YIELD node, centrality

输入参数

所有通用输入参数以及：

名称 类型 必需 默认 说明
num_source_nodes INT64 否 （无） 如果设置，则必须为正值，用于指定算法应选择多少个源节点来计算近似中介中心性。如果未设置，或设置为大于图表中节点数量的数字，则所有节点都将用作源节点，也就是说，该算法会计算精确的介数中心性。值越高，近似效果越好，但运行时间也会越长。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图表中的节点。
中心性 FLOAT64 节点的中心性得分。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL BetweennessCentrality(
    node_labels => ['Account'], edge_labels => ['Transfers'], num_source_nodes => 5
  ) YIELD node, centrality
RETURN node.id, centrality;

ClosenessCentrality

ClosenessCentrality 用于衡量节点与图表中所有其他节点的接近程度。具有较高紧密中心性的节点可以通过较短的路径到达其他节点。如需了解算法详情，请参阅接近中心性。

函数签名

ClosenessCentrality(input_parameters) YIELD node, centrality

输入参数

所有通用输入参数以及：

名称 类型 必需 默认 说明
模式 STRING 否 EXACT 算法模式。支持的值包括 EXACT 和 HYBRID。
use_wasserman_faust 布尔值 否 FALSE 如果为 `false`，则计算标准紧密度中心性。如果为 true，则计算 Wasserman-Faust 紧密中心性。
epsilon FLOAT64 否 0.1 仅用于 `HYBRID` 算法。必须介于 (0.0, 1.0) 之间。 值越小，精确度通常越高。值越大，算法的执行速度通常越快。
sample_size INT64 否 0 仅用于 `HYBRID` 算法。用于近似计算中心性值的透视节点的数量。必须为非负数。 如果未设置或为零，则使用默认值 min(100 * ln(N), N)，其中 N 是输入图的节点数。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图中的节点。
中心性 FLOAT64 节点的紧密中心性得分。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/my-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ClosenessCentrality(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    mode => 'EXACT'
  ) YIELD node, centrality
RETURN node.id, centrality;

聚簇

聚类算法将节点分组为聚类（也称为社区），以便每个聚类中的节点彼此之间的连接比与其他聚类中的节点之间的连接更密集。这有助于检测金融科技领域的潜在欺诈团伙、识别零售领域的客户细分等等。

WeaklyConnectedComponents

WeaklyConnectedComponents 查找不相交的节点集，以便集中的每个节点都可以从同一集中的任何其他节点访问，但不能从其他集中的节点访问。如需了解算法详情，请参阅连通分量。

函数签名

WeaklyConnectedComponents(input_parameters) YIELD node, cluster

输入参数

所有常见输入参数。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图中的节点。
集群 INT64 节点所属的已连接组件/集群的 ID。 在 [0, N) 范围内，其中 N 是图中的节点数。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/wcc-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL WeaklyConnectedComponents(
    node_labels => ['Account'], edge_labels => ['Transfers']
  ) YIELD node, cluster
RETURN node.id, cluster;

ModularityClustering

ModularityClustering 通过优化模块化程度（一种衡量集群内连接密度相对于随机网络中预期连接密度的质量指标）将图划分为集群。如需了解算法详情，请参阅模块化聚类。

函数签名

ModularityClustering(input_parameters) YIELD node, cluster

输入参数

所有通用输入参数以及：

名称 类型 必需 默认 说明
分辨率 双精度 否 1.0 控制聚类的粒度。必须是有限且非负的。分辨率值越小，聚类往往越大。 典型值介于 [0.5, 5] 范围内。当分辨率为零时，算法（在迭代次数足够的情况下）会找到图的连通分量（忽略权重为零的边）。
max_iterations 整数 否 10 算法的外部迭代次数上限。必须为正值。 值越大，聚类质量往往越高，但运行时长也会越长。
max_inner_iterations 整数 否 10 算法的内部迭代次数上限。必须为正值。 值越大，聚类质量往往越高，但运行时长也会越长。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图中的节点。
集群 INT64 节点所属的社区/集群的 ID。 在 [0, N) 范围内，其中 N 是图中的节点数。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/modularity-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ModularityClustering(
    node_labels => ['Account'], edge_labels => ['Transfers'],
    resolution => 1.0, max_iterations => 10
  ) YIELD node, cluster
RETURN node.id, cluster;

CorrelationClustering

CorrelationClustering 根据节点的成对相似性或相异性对节点进行划分，旨在将相似的节点分组在一起，同时将相异的节点分开。如需了解算法详情，请参阅相关性聚类。

函数签名

CorrelationClustering(input_parameters) YIELD node, cluster

输入参数

所有通用输入参数以及：

名称 类型 必需 默认 说明
分辨率 双精度 是 （无） 控制聚类的粒度。必须由客户端明确定义。必须是有限的非负数。值越小，聚类往往越大。当分辨率为零且所有边权重均为正值时，该算法（在迭代次数足够的情况下）会找到图的连通分量。
max_iterations 整数 否 10 算法的外部迭代次数上限。必须为正值。 值越大，聚类质量往往越高，但运行时长也会越长。
max_inner_iterations 整数 否 10 算法的内部迭代次数上限。必须为正值。 值越大，聚类质量往往越高，但运行时长也会越长。

输出

函数产生：

名称 类型 说明
节点 GRAPH_ELEMENT（节点） 图中的节点。
集群 INT64 节点所属的社区/集群的 ID。 在 [0, N) 范围内，其中 N 是图中的节点数。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/correlation-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL CorrelationClustering(
    node_labels => ['Account'], edge_labels => ['Transfers'