关于后端:TuGraph-Analytics图计算快速上手之Kcore算法

作者：郑光杰

引言

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/