✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

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。

Ultipa 的 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
e--[110]--f
f--[111]--c
i--[113]--m
d--[107]--f
g--[120]--k
m--[121]--k
i--[122]--f
f--[108]--d
d--[109]--e
m--[123]--f
f--[124]--g
k--[117]--f
g--[125]--m
i--[114]--g

直接返回

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