概述

k-Truss算法能识别图中称为Truss（桁架）的最大的、紧密连接的子图。该算法在各个领域都有广泛的应用，包括社交网络、生物网络和交通网络，通过发现密切相关的节点组成的社区或集群，k-Truss算法为复杂网络的结构和连通性提供了有价值的见解。

k-Truss最初由J. Cohen在2005年定义：

• J. Cohen, Trusses: Cohesive Subgraphs for Social Network Analysis (2005)

基本概念

k-Truss

Truss的概念是根据对社交凝聚力的观察而提出的：如果两个人关系紧密，他们很可能也与他人有共同联系。由此创建k-Truss：A和B之间的连接只有在至少k-2个其他人的支持下才被认为是合法的，这些人分别与A和B有连接。换句话说，k-Truss中每条边所连接的两个节点至少有k–2个共同邻居。

正式的定义是，k-Truss是图中的最大子图，其中每条边至少由k-2对边支撑，与该边形成三角形。

下面是一个示例图，其中3-truss和4-truss以红色突出显示。此图没有k值为5或更大的truss。

嬴图的k-Truss算法识别图中每个连通分量的最大Truss。

特殊说明

• 每个Truss中至少包含3个节点（当k≥3）。
• 在两点之间可能存在多条边的复杂图中，Truss中的三角形是按边计数的。另请参阅三角形计算算法。
• k-Truss算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(k_truss)
• 参数：

示例

示例图如下：

文件回写

algo(k_truss).params({k: 4}).write({
  file:{
      filename: 'truss'
  }
})

结果：文件truss

d--[102]--a
c--[103]--a
d--[104]--c
f--[105]--a
f--[106]--d
d--[107]--f
f--[108]--d
d--[109]--e
e--[110]--f
f--[111]--c
k--[117]--f
k--[119]--l
g--[120]--k
m--[121]--k
i--[122]--f
m--[123]--f
f--[124]--g
g--[125]--m
m--[126]--l

直接返回

algo(k_truss).params({k: 5}) as truss return truss

结果：truss

流式返回

algo(k_truss).params({k: 5}).stream() as truss5
with pedges(truss5) as e
find().edges(e) as edges
return edges{*}

结果：edges