Spanner Graph 算法目录

预览版 - Spanner Graph 算法

此功能受服务专用条款的“通用服务条款”部分中的“非正式版产品条款”的约束。 非正式版功能“按原样”提供，可能只能获得有限的支持。 如需了解详情，请参阅发布阶段说明。

注意：此功能适用于 Spanner 企业版和企业 Plus 版。如需了解详情，请参阅 Spanner 版本概览。

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'],
    resolution => 0.5
  ) YIELD node, cluster
RETURN node.id, cluster;

LabelPropagation

LabelPropagation 使用标签传播技术将节点分配给集群，从可能使用输入中提供的种子标签的初始标签开始。随着节点迭代采用其大多数邻居共享的标签，紧密连接的群组会收敛到一致的标签，从而形成社区。如需了解算法详情，请参阅标签传播。

函数签名

LabelPropagation(input_parameters) YIELD node, cluster

输入参数

所有通用输入参数以及：

名称	类型	必需	默认	说明
seed_label_property	字符串	否	（无）	种子标签的节点属性名称。
max_iterations	整数	否	10	算法执行的标签传播迭代次数上限。必须是有限的正数。

输出

函数产生：

名称	类型	说明
节点	GRAPH_ELEMENT（节点）	图表中的节点。
集群	INT64	节点的传播集群/标签 ID。

示例

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

CliqueFinding

CliqueFinding 用于识别满足最低密度阈值的可能重叠的密集社区，以便每个派系（一组节点，其中每个节点都连接到所有其他节点）都包含在至少一个聚类中。如需了解算法详情，请参阅集团汇总器。

函数签名

CliqueFinding(input_parameters) YIELD node, clique

注意：与大多数算法不同，由于一个节点可能属于多个派系，因此同一节点可以对应多行。

输入参数

所有通用输入参数以及：

名称	类型	必需	默认	说明
min_density	双精度	否	0.9	要返回的聚类的最小密度。必须介于 [0, 1] 之间。

输出

函数产生：

名称	类型	说明
节点	GRAPH_ELEMENT（节点）	图中的节点。
clique	INT64	节点所属派系的 ID。

示例

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

相似度

相似性算法会根据节点邻域的结构量化节点对的相似程度。这有助于推断节点之间缺失的边，以进行实体解析、推荐等。

Spanner Graph 支持以下成对节点相似度，其中相似度得分是根据节点的邻域计算的。

• JaccardSimilarity：基于共同邻居与总邻居的比率
• CosineSimilarity：基于共同邻居的边权重
• CommonNeighborsSimilarity：基于共享邻居的数量
• TotalNeighborsSimilarity：基于至少一个节点的邻居数量

如需了解算法详情，请参阅成对节点相似度。

这四种算法具有相同的实参和输出结构。

函数签名

[JaccardSimilarity|CosineSimilarity|CommonNeighborsSimilarity|TotalNeighborsSimilarity](input_parameters) YIELD source_node, target_node, similarity

输入参数

所有通用输入参数以及：

名称	类型	必需	默认	说明
source_nodes	节点数组	是	不适用
target_nodes	节点数组	是	不适用

输出

函数产生：

名称	类型	说明
source_node	GRAPH_ELEMENT（节点）	用于相似度计算的源节点。
target_node	GRAPH_ELEMENT（节点）	用于相似度计算的目标节点。
相似度	FLOAT64	来源节点与目标节点之间计算出的相似度得分。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/jaccard-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL JaccardSimilarity(
    source_nodes => ARRAY {
                      MATCH (n:Account {id: 7})
                      RETURN n
                    },
    target_nodes => ARRAY {
                      MATCH (n:Account)
                      WHERE n.id != 7
                      RETURN n
                    }
  ) YIELD source_node, target_node, similarity
RETURN source_node.id AS source_id, target_node.id AS target_id, similarity;

路径查找

路径查找算法用于计算节点之间的最佳路线。这有助于确定供应链中最便宜的路线、评估网络安全中的漏洞等。

ShortestPath

ShortestPath 用于计算给定的一组源节点与给定的一组目标节点之间的最短路径。如需了解算法详情，请参阅多对多最短路径。

函数签名

ShortestPath(input_parameters) YIELD source_node, target_node, path, cost

输入参数

所有通用输入参数以及：

名称	类型	必需	默认	说明
source_nodes	节点数组	是	不适用
target_nodes	节点数组	是	不适用

输出

函数产生：

名称	类型	说明
source_node	GRAPH_ELEMENT（节点）	路径的源节点。
target_node	GRAPH_ELEMENT（节点）	路径的目标节点。
路径	GRAPH_PATH	找到的最短路径。
费用	FLOAT64	最短路径的费用。

示例

EXPORT DATA OPTIONS (
  uri = "gs://my-bucket-name/shortest-path-output.csv",
  format = "csv"
) AS
GRAPH FinGraph
CALL ShortestPath(
    source_nodes => ARRAY {
                      MATCH (n:Account {id: 7})
                      RETURN n
                    },
    target_nodes => ARRAY {
                      MATCH (n:Account {id: 16})
                      RETURN n
                    }
  ) YIELD source_node, target_node, path, cost
RETURN source_node.id AS source_id, target_node.id AS target_id, PATH_LENGTH(path) AS length, cost;

后续步骤

• Spanner Graph 运行算法。
• Spanner Graph 算法架构要求和功能兼容性。
• Spanner Graph 算法最佳实践。