作者:郑光杰
引言
K-Core 算法是一种用来在图中找出合乎指定外围度的严密关联的子图构造,在 K -Core 的后果子图中,每个顶点至多具备 k 的度数,且所有顶点都至多与该子图中的 k 个其余节点相连。K-Core 通常用来对一个图进行子图划分,通过去除不重要的顶点,将合乎逾期的子图裸露进去进行进一步剖析。K-Core 图算法罕用来辨认和提取图中的严密连通群组,因具备较低的工夫复杂度(线性)及较好的直观可解释性,广泛应用于金融风控、社交网络和生物学等钻研畛域。
K-Core 算法介绍
一张图的 K-Core 子图是指从图中重复去掉度(不思考自环边)小于 k 的节点之后失去的子图。该计算过程是一个重复迭代剪枝的过程,在某一轮剪枝之前度大于等于 k 的节点,可能会在该轮剪枝后变为度小于 k。比方 3 -core 子图的切分过程如图 1 所示:
3-core 子图切分过程
TuGraph-Analytics 实现 K -Core 算法
要运行 K -Core 算法,咱们能够指定应用的图,间接在图查问里调用 K -Core 算法,语法模式如下:
INSERT INTO tbl_result
CALL kcore(3) YIELD (id, value)
RETURN id, value;
运行该语法之后,就能够从图中查问到 k = 3 的子图的 id 以及该 id 的街坊数。
TuGraph-Analytics 曾经内置了许多算法,如果想要自定义算法,能够基于 AlgorithmUserFunction 接口实现,比方自定义 k -core 算法实现如下:
package com.tugraph.demo;
import com.antgroup.geaflow.common.type.primitive.IntegerType;
import com.antgroup.geaflow.dsl.common.algo.AlgorithmRuntimeContext;
import com.antgroup.geaflow.dsl.common.algo.AlgorithmUserFunction;
import com.antgroup.geaflow.dsl.common.data.RowEdge;
import com.antgroup.geaflow.dsl.common.data.RowVertex;
import com.antgroup.geaflow.dsl.common.data.impl.ObjectRow;
import com.antgroup.geaflow.dsl.common.function.Description;
import com.antgroup.geaflow.dsl.common.types.StructType;
import com.antgroup.geaflow.dsl.common.types.TableField;
import com.antgroup.geaflow.model.graph.edge.EdgeDirection;
import java.util.Iterator;
import java.util.List;
@Description(name = "kcore", description = "built-in udga for KCore")
public class KCore implements AlgorithmUserFunction<Object, Integer> {
private AlgorithmRuntimeContext<Object, Integer> context;
private int k = 1;
@Override
public void init(AlgorithmRuntimeContext<Object, Integer> context, Object[] params) {
this.context = context;
if (params.length > 1) {
throw new IllegalArgumentException(
"Only support zero or more arguments, false arguments"
+ "usage: func([alpha, [convergence, [max_iteration]]])");
}
// 设置 k 值,默认 k =1
if (params.length > 0) {k = Integer.parseInt(String.valueOf(params[0]));
}
}
@Override
public void process(RowVertex vertex, Iterator<Integer> messages) {
boolean isFinish = false;
// 第一轮迭代将所有顶点初始化,指标点的 value 值初始化为 -1,并向邻点发送音讯
if (this.context.getCurrentIterationId() == 1) {this.context.updateVertexValue(ObjectRow.create(-1));
} else {
// v = 0, 则示意须要删除
int currentV = (int) vertex.getValue().getField(0, IntegerType.INSTANCE);
if (currentV == 0) {return;}
// 计算点的输出音讯数
int sum = 0;
while (messages.hasNext()) {sum += messages.next();
}
// 如果点接管的音讯数小于 k 的则须要删除
if (sum < k) {
isFinish = true;
sum = 0;
}
// 更新以后点的值为接管音讯数
context.updateVertexValue(ObjectRow.create(sum));
}
if (isFinish) {return;}
// 向点的街坊发送音讯
List<RowEdge> outEdges = this.context.loadEdges(EdgeDirection.OUT);
for (RowEdge rowEdge : outEdges) {context.sendMessage(rowEdge.getTargetId(), 1);
}
List<RowEdge> inEdges = this.context.loadEdges(EdgeDirection.IN);
for (RowEdge rowEdge : inEdges) {context.sendMessage(rowEdge.getTargetId(), 1);
}
// 向本点送音讯,避免该点因没有音讯不会触发下次迭代
context.sendMessage(vertex.getId(), 0);
}
@Override
public StructType getOutputType() {
return new StructType(new TableField("id", IntegerType.INSTANCE, false),
new TableField("v", IntegerType.INSTANCE, false)
);
}
}
TuGraph-Analytics 运行 K -Core 算法
图定义
如果想要在 dsl 中运行 k -core 算法,咱们能够第一步先进行图定义,比方:
CREATE GRAPH IF NOT EXISTS g (
Vertex v (
vid int ID,
value int
),
Edge e (
srcId int SOURCE ID,
targetId int DESTINATION ID
)
) WITH (
storeType='rocksdb',
shardCount = 1
);
图构建
有了图定义之后,咱们就能够往这个图中导入点边数据,将这个图构建起来。
CREATE TABLE IF NOT EXISTS v_source (
v_id int,
v_value int
) WITH (
type='file',
//vertex 文件中保留了点的信息,文件放在与 KCore 类目录下的 resources 目录下,此处能够换成其余数据源
geaflow.dsl.file.path = 'resource:///input/vertex'
);
CREATE TABLE IF NOT EXISTS e_source (
src_id int,
dst_id int
) WITH (
type='file',
//edge 文件中保留了边的信息,文件放在与 KCore 类目录下的 resources 目录下,此处能够换成其余数据源
geaflow.dsl.file.path = 'resource:///input/edge'
);
USE GRAPH g;
INSERT INTO g.v(vid, value)
SELECT
v_id, v_value
FROM v_source;
INSERT INTO g.e(srcId, targetId)
SELECT
src_id, dst_id
FROM e_source;
图剖析与输入
当图构建之后,咱们就能够在图数据根底上进行剖析查问和后果输入了。
// 定义后果表
CREATE TABLE IF NOT EXISTS tbl_result (
v_id int,
value int
) WITH (
type='file',
geaflow.dsl.file.path = '/tmp/result'
);
// 注册 kcore 函数
CREATE Function kcore AS 'com.tugraph.demo.KCore';
USE GRAPH g;
INSERT INTO tbl_result(v_id, value)
// 调用 kcore 函数,并返回后果
CALL kcore(3) YIELD (vid, value)
RETURN vid, value
;
运行示例
基于以上定义的 dsl,咱们以图 1 的数据作为输出,来计算一下图 1 的 3 -core 子图。
输出
//vertex 文件内容:
1,1
2,1
3,1
4,1
5,1
6,1
7,1
8,1
9,1
//edge 文件内容:
1,3
2,3
3,4
3,9
3,5
4,9
4,5
5,9
5,6
5,7
6,7
6,8
7,8
输入
3,3
4,3
5,3
9,3
总结
在本篇文章中咱们介绍了如何在 TuGraph Analytics 上实现 K -Core 算法,如果你感觉比拟乏味,欢送关注咱们的社区(https://github.com/TuGraph-family/tugraph-analytics)。开源不易,如果你感觉还不错,能够给咱们 star 反对一下~
GeaFlow(品牌名 TuGraph-Analytics) 已正式开源,欢送大家关注!!!
欢送给咱们 Star 哦!
Welcome to give us a Star!
GitHub👉https://github.com/TuGraph-family/tugraph-analytics
更多精彩内容,关注咱们的博客 https://geaflow.github.io/