全部产品
云市场
云游戏

图算法分析列表

更新时间:2019-12-09 14:54:00

功能介绍

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)输入,例如:

全图:

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

子图:

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

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

算法算子

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

  1. .cc("cid",10)

属性读取

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

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

算法输出

算法支持输出属性(”cid”)作为临时属性;同时,也支持将结果输出到odps表。导出到odps的示例如下:

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

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

输出结果语句:

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

SDK提交算法调用

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

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