概述
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。
![](https://img.ultipa.cn/draw/draw_89d92df096414bd69a3e1ed22f6a58a2.jpg?v='1686670542500')
嬴图的k-Truss算法识别图中每个连通分量的最大Truss。
特殊说明
- 每个Truss中至少包含3个节点(当k≥3)。
- 在两点之间可能存在多条边的复杂图中,Truss中的三角形是按边计数的。另请参阅三角形计算算法。
- k-Truss算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(k_truss)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
k | int | ≥2 | / | 否 | k-Truss中的每条边都包含在至少k-2个三角形中 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_1c68121b9ba64d14889a65b9608d5cfb.jpg?v='1686709939980')
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id--[_uuid]--_id |
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
直接返回
别名序号 |
类型 |
描述 |
---|---|---|
0 | []path |
Truss中的一步路径:_uuid (起点) -- [_uuid] (边) -- _uuid (终点) |
algo(k_truss).params({k: 5}) as truss return truss
结果:truss
4--[102]--1 |
4--[104]--3 |
6--[105]--1 |
6--[106]--4 |
4--[107]--6 |
6--[108]--4 |
4--[109]--5 |
5--[110]--6 |
6--[111]--3 |
流式返回
别名序号 |
类型 |
描述 |
---|---|---|
0 | []path |
Truss中的一步路径:_uuid (起点) -- [_uuid] (边) -- _uuid (终点) |
algo(k_truss).params({k: 5}).stream() as truss5
with pedges(truss5) as e
find().edges(e) as edges
return edges{*}
结果:edges
_uuid | _from | _to | _from_uuid | _to_uuid |
---|---|---|---|---|
102 | d | a | 4 | 1 |
104 | d | c | 4 | 3 |
105 | f | a | 6 | 1 |
106 | f | d | 6 | 4 |
107 | d | f | 4 | 6 |
108 | f | d | 6 | 4 |
109 | d | e | 4 | 5 |
110 | e | f | 5 | 6 |
111 | f | c | 6 | 3 |