图算法

选择图范围,在样例上运行算法,并理解结果和资源占用。

本页目录

按问题选择算法和图范围

最短路径
寻找两个已知端点之间成本较低的路线,成本可以是跳数,也可以是映射后的数值边属性。
PageRank
在有向图上综合入边和对应源节点的分配权重,对节点进行排序。
弱连通分量
忽略边方向,找出彼此连通的节点组。
社区与向量
用 Louvain 或 Leiden 划分社区,用 Node2Vec 为节点生成向量特征。

执行前确定边类型、方向和权重。使用权重时,各候选边类型都要映射该字段且取值满足算法要求。以下示例使用三个账户的样例图。

用 PageRank 排序账户

Cypher
CALL algo.pagerank({relationshipTypes: ['Transfer']})
YIELD id, rank
RETURN id.key AS account, rank
ORDER BY rank DESC, account

应返回三个账户及其分数。比较同一个图投影里的分数。选择另一种边或方向时,计算所用的图也会改变。

找出连通群组

Cypher
CALL algo.wcc({relationshipTypes: ['Transfer']})
YIELD id, component
RETURN id.key AS account, component
ORDER BY account

Alice、Bob 和 Carol 属于同一个连通分量。对比分量标识即可判断节点是否同组。如需判断某个方向是否可达,再执行路径查询。

查找加权路线

在样例目录执行下方命令。此处用转账金额演示如何指定成本字段。

Shell
/opt/graphlake/current/bin/graphlake --catalog graph.yaml route \
  --edge Transfer --weight amount \
  --start-label Account --start 1 --target-label Account --target 3

预期结果 从账户 1 到 3 有一条两跳路线,精确成本为 37.75。

选择在线数据或 CSR 代次

重复遍历时,管理员或具备发布权限的成员可为已发布模型构建 CSR 代次,也就是压缩后的邻接快照。在查询选项中选择代次前,核对它的图范围和来源状态。需要反映数据或范围的变更时,重新构建。

集群上的部分 PageRank 和弱连通分量任务可使用分区 CSR。社区检测和 Node2Vec 在执行节点上使用完整投影。支持的操作、内存预算和权重约束见算法参考。