概述

三角形计算（Triangle Counting）算法用来统计无向图中由点、边构成的三角形的数量，并返回构成每个三角形的点或边。三角形计算能够体现图中任意三个点之间形成环路的能力，也是计算全局聚集系数时的一个基本概念。

三角形计算是一种通用图算法，常用于社交网络发现、社区识别、紧密度分析、稳定性分析等。例如，某金融机构发放的账户之间的交易所构成的三角形数量标识了该金融机构下账户间的连通度及连接紧密度。

基本概念

三元组

三元组，通常记作 Triplet 或 Triples，是拓扑学中的基本概念，指简单图中通过 2~3 条边连接的三个点（简单图中任意两点之间最多只有一条边）。其中，通过两条边相连的三元组称为开放式三元组，通过三条边相连的三元组称为封闭式三元组。

对一张简单图进行计算，用封闭式三元组的数量除以全部三元组的数量，就得到了全局聚集系数。全局聚集系数从三元组的角度反映图中一个点的邻接点之间相互连接的程度。

三角形

三角形计算算法计算的三角形是封闭式三元组。之前对于封闭式三元组的定义是在简单图中给出的，对于复杂图来说，任意两点之间可以有多条边，于是三角形的定义就分成了两类：

• 按边组装的三角形
• 按点组装的三角形

按边组装三角形的过程可以理解为在图中寻找能连接任意三个点的环路。由于是环路，还要去掉因路径的起点、方向等不同而产生的重复结果，为此可以令环路中的点的 ID 按一定顺序（例如简单的升序、降序等）排列:

上图中一共找到了 4 条环路，即 4 个按边组装的三角形。如果忽略这 4 条环路中的边，将环路看作点序列并去重，即可得到 2 个按点组装的三角形。按点组装三角形的过程相当于将图中任意两点之间的多重边合并为一条边（即将复杂图压缩为简单图），然后再寻找能连接任意三个点的环路。在复杂图中，按边组装的三角形数量通常多于按点组装的三角形数量。

计算三角形时，组装原则应根据应用场景而定。一般来说，以社交网络分析为主导的应用场景会采用按点组装的原则，而在金融网络分析中则需要采用按边组装的原则。

特殊处理

孤点、不连通图

孤点不参与三角形的构成。

不连通图在其各个连通分量内部组装三角形。

自环边

自环边不是构成三角形的要素，不参与三角形的组装。

有向边

本算法会忽略边的方向，按照无向边进行计算。

结果和统计值

以下面的图为例，运行三角形计算算法：

算法结果 1：按边计算三角形，根据设置的结果类型，返回 triangle_count 一列或返回 edge1、edge2、edge3 三列

算法统计值 1：三角形个数 triangle_count

算法结果 2：按点计算三角形，根据设置的结果类型，返回 triangle_count 一列或返回 node1、node2、node3 三列

算法统计值 2：三角形个数 triangle_count

命令和参数配置

• 命令：algo(triangle_counting)
• params() 参数配置项如下：

示例：按边计算全图三角形的数量

algo(triangle_counting).params({type: 1}) as tri
return tri

示例：按点计算全图三角形，返回 1 组构成三角形的点

algo(triangle_counting).params({
  type: 2, 
  result_type: 2, 
  limit: 1}) as tri
return tri

算法执行

任务回写

1. 文件回写

示例：按点计算全图三角形，将算法结果回写至名为 test 的文件

algo(triangle_counting).params({
  type: 2,
  result_type: 2
}).write({
  file:{
    filename: "test"
}})

2. 属性回写

算法不支持属性回写。

3. 统计回写

示例：按边计算全图三角形，将算法统计值回写至任务信息

algo(triangle_counting).params({
  result_type: 1
}).write()

直接返回

示例：按边计算全图三角形，将算法结果（三角形个数）定义为别名 count 并返回

algo(triangle_counting).params({
  result_type: 1
}) as count 
return count

示例：按边计算全图三角形，将算法结果（构成三角形的边）定义为别名 triangles 并返回

algo(triangle_counting).params({
  result_type: 2
}) as triangles 
return triangles

流式返回

示例：按点计算全图三角形，返回构成三角形的点的全部信息

algo(triangle_counting).params({
  type: 2, 
  result_type:2 
}).stream() as tri
find().nodes({_uuid == tri.node1 || _uuid == tri.node2 || _uuid == tri.node3}) as nodes
return nodes{*}

实时统计

示例：按边计算全图三角形，将算法统计值定义为别名 sta 并返回

algo(triangle_counting).params({
  result_type: 1
}).stats() as sta 
return sta