功能介绍

GraphCompute中内置了4大类常用图分析算法，分别为：最短路径、PageRank，Connected Components, Label Propagation algorithm （LPA）。

具体算子列表如下：

算法	说明	示例	参数说明
Connected Component	计算每个顶点属于的弱联通分量	.cc(“cid”, 10)	• “cid”为输出结果属性的属性名; • 10是迭代轮次
PageRank	通过沿着边传播相互影响，计算每个顶点的流行程度。	.pageRank(“pagerank”, 0.85, 10)	• “pagerank”为输出结果属性的属性名; • 0.85是pagerank算法中的参数（damping factor）; • 10是迭代轮次
LPA	节点都带有初始标签，并通过边传播标签相互影响，计算每个顶点最终稳定的标签。	.lpa(“out”, “label”, “lpa”, 10)	• “out”为标签传播方向; • “label”为初始标签属性名（已有标签）; • “lpa”为输出结果标签的属性名; • 10是迭代轮次
HITS	通过沿着边传播相互影响，通过内容权威度（Authority）和链接权威度（Hub）来对顶点质量进行评估。	.hits(“auth”, “hub”, 10)	• “auth”为输出的auth属性名 • “hub”为输出的hub属性名 • 10是迭代轮次
SSSP	给定源顶点s，找到从s到图中所有可达顶点的最短路径。支持无权图和有权图的计算。	.shortestPath(sid, “path”,”id”,10) 或 .shortestPath(sid, “weight”,”path”, “id”,10)	• sid为起始点的id; • “weight”可选，有权图中边权重的属性名; • “path”为输出路径的属性名; • “id”为输出路径组成元素的属性名，如”id”代表输出路径由id组成 • 10是迭代轮次
All Pair Shortest Path	计算图中任意两点之间的最短路径。支持无权图和有全图的计算。	.shortestPath(“path”, “id”,10) 或 .shortestPath( “weight”, “path”, “id”, 10)	• “weight”可选，有权图中边权重的属性名; • “path”为输出路径的属性名; • “id”为输出路径组成元素的属性名，如”id”代表输出路径由id组成 • 10是迭代轮次
s-t Shortest Path	给定源顶点s和目标顶点t，找到从v到t之间的最短路径。支持无权图计算。	.shortestPath(sid,tid,”path”, “id”, 10)	• sid为起始点的id; • tid为终止点的id • “weight”可选，有权图中边权重的属性名; • “path”为输出路径的属性名; • “id”为输出路径组成元素的属性名，如”id”代表输出路径由id组成 • 10是迭代轮次

使用示例

下面将以Connected Component算法为例，介绍内置算法的语法及使用方式，用户可以直接通过Query节点或Console提交Gremlin语句来执行。

算子语法

输入

算法支持全图或子图（edge-induced subgraph）输入，例如：

全图：

g.E().subgraph("s").cap("s")

子图：

g.E().hasLabel('knows').subgraph("s").cap("s")

其中，subgraph之前接入的算子的输出一定是E（即目前支持的子图是edge-induced subgraph），如果是全图，则会作为一种子图的特殊形式。

算法算子

在cc算法中，输出是包含一个long类型的属性，代表当前点属于的component。这个属性是需要用户预先在点的schema中设置好对应属性字段及类型（long类型），并且在cc语法中指定输出属性名（例如，”cid”）以及迭代次数（例如，10）。算子示例如下：

.cc("cid",10)

属性读取

用户可以指定读取哪些属性，例如:

.map(Prop.fill("id","cid")

算法输出

算法支持输出属性（”cid”）作为临时属性；同时，也支持将结果输出到odps表。导出到odps的示例如下：

用户需要预先建好输出边，schema需要和write里面的字段的顺序和类型一致，例如：

CREATE TABLE IF NOT EXISTS cc_result(id BIGINT, cid BIGINT) lifecycle 7;

输出结果语句：

.output('tunnel://accsessID:accessKey@service.odpsstg.aliyun-inc.com/stgnew#project=maxgraph&table=cc_result', "id", "cid")

SDK提交算法调用

除了直接编写query语句外，我们也可以通过SDK接口来提交算法，示例如下：

// add temporary property "cid"
String queryScript = "g.timeoutSec(600).E().hasLabel('cname_to').subgraph('s').cap('s')"
     + "               .cc('cid',50)"
     + "               .map(Prop.fill('id','cid'))";
client.submit(queryScript);

图算法分析列表