k_truss

k_truss(G, k)

返回 G 的 k-truss。

k-truss 是 G 的一个最大诱导子图，该子图至少包含三个顶点，且每条边至少属于 k-2 个三角形。

参数:

GNetworkX 图

无向图

kint

truss 的阶

返回:

HNetworkX 图

k-truss 子图

抛出异常:

NetworkXNotImplemented

如果 G 是多重图或有向图，或者包含自环。

注意

k-clique 是一个 (k-2)-truss，而 k-truss 是一个 (k+1)-core。

图、节点和边的属性会被复制到子图。

K-truss 最初定义在 [2] 中，该定义指出 k-truss 是最大的诱导子图，其中每条边至少属于 k-2 个三角形。最近的一篇论文 [1] 使用了一个略有不同的定义，要求每条边至少属于 k 个三角形。本实现使用的是原始定义，即 k-2 个三角形。

参考文献

[1]

k-truss 的界和算法。Paul Burkhardt, Vance Faber, David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2

[2]

Trusses: 用于社交网络分析的内聚子图。Jonathan Cohen, 2005。

示例

>>> degrees = [0, 1, 2, 2, 2, 2, 3]
>>> H = nx.havel_hakimi_graph(degrees)
>>> H.degree
DegreeView({0: 1, 1: 2, 2: 2, 3: 2, 4: 2, 5: 3, 6: 0})
>>> nx.k_truss(H, k=2).nodes
NodeView((0, 1, 2, 3, 4, 5))
----

其他后端实现了此函数

cugraph : GPU 加速后端。

graphblas : 启用 OpenMP 的稀疏线性代数后端。