该文档涉及的组件

最大联通分量 (ConnectedComponentsBatchOp)

Java 类名:com.alibaba.alink.operator.batch.graph.ConnectedComponentsBatchOp

Python 类名:ConnectedComponentsBatchOp

功能介绍

在无向图G中,若从顶点A到顶点B有路径相连,则称A和B是连通的;
在图G种存在若干子图,其中每个子图中所有顶点之间都是连通的,但在不同子图间不存在顶点连通,那么称图G的这些子图为最大连通子图。

最大联通子图的应用场景有ID-Mapping,节点分类,社区发现,反作弊等。比如识别作弊或者有风险的账号,与作弊账号在同一个子图中的账号,就有潜在的风险。

参数说明

名称 中文名称 描述 类型 是否必须? 取值范围 默认值
edgeSourceCol 边表中起点所在列 边表中起点所在列 String
edgeTargetCol 边表中终点所在列 边表中终点所在列 String
asUndirectedGraph 是否为无向图 是否为无向图 Boolean true
maxIter 最大迭代次数 最大迭代次数 Integer x >= 1 50
vertexCol 边的源顶点 边的源顶点 String “vertex”

代码示例

Python 代码

from pyalink.alink import *

import pandas as pd

useLocalEnv(1)

df = pd.DataFrame([[1, 2],\
[2, 3],\
[3, 4],\
[4, 5],\
[6, 7],\
[7, 8],\
[8, 9],\
[9, 6]])

data = BatchOperator.fromDataframe(df, schemaStr="source int, target int")
ConnectedComponentsBatchOp()\
    .setEdgeSourceCol("source")\
    .setEdgeTargetCol("target")\
    .linkFrom(data)\
    .print()

Java 代码

import org.apache.flink.types.Row;

import com.alibaba.alink.operator.batch.BatchOperator;
import com.alibaba.alink.operator.batch.source.MemSourceBatchOp;
import com.alibaba.alink.testutil.AlinkTestBase;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class ConnectedComponentsBatchOpTest {
	@Test
	public void test() throws Exception {
		List<Row> edgeRows = Arrays.asList(
			Row.of(1, 2),
			Row.of(2, 3),
			Row.of(3, 4),
			Row.of(4, 5),
			Row.of(6, 7),
			Row.of(7, 8),
			Row.of(8, 9),
			Row.of(9, 6)
		);
		BatchOperator edgeData = new MemSourceBatchOp(edgeRows, "source int,target int");

		BatchOperator res = new ConnectedComponentsBatchOp()
			.setSetStable(false)
			.setEdgeSourceCol("source")
			.setEdgeTargetCol("target")
			.linkFrom(edgeData).print();
	}
}

运行结果

node groupId
1 0
2 0
5 0
9 4
4 0
3 0
8 4
6 4
7 4