作者：郑光杰
引言
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_resultCALL 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)SELECTv_id, v_valueFROM v_source;INSERT INTO g.e(srcId, targetId)SELECT src_id, dst_idFROM 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,12,13,14,15,16,17,18,19,1//edge文件内容:1,32,33,43,93,54,94,55,95,65,76,76,87,8输入
3,34,35,39,3总结
在本篇文章中咱们介绍了如何在TuGraph Analytics上实现K-Core算法，如果你感觉比拟乏味，欢送关注咱们的社区（https://github.com/TuGraph-family/tugraph-analytics）。开源不易，如果你感觉还不错，能够给咱们star反对一下～
GeaFlow(品牌名TuGraph-Analytics) 已正式开源，欢送大家关注！！！
欢送给咱们 Star 哦!
Welcome to give us a Star!
GitHubhttps://github.com/TuGraph-family/tugraph-analytics
更多精彩内容，关注咱们的博客 https://geaflow.github.io/