k_truss

k_truss(G, k)

返回 G 的 k-truss。

k-truss 是 G 的最大诱导子图，其中包含至少三个顶点，并且每条边至少与 k-2 个三角形相关联。

Parameters:

GNetworkX 图

一个无向图

kint

truss 的阶数

Returns:

HNetworkX 图

k-truss 子图

Raises:

NetworkXNotImplemented

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

Notes

k-团是 (k-2)-truss，而 k-truss 是 (k+1)-核。

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

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

References

[1]

Bounds and Algorithms for k-truss. Paul Burkhardt, Vance Faber, David G. Harris, 2018. https://arxiv.org/abs/1806.05523v2

[2]

Trusses: Cohesive Subgraphs for Social Network Analysis. Jonathan Cohen, 2005.

Examples

>>> 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))

---

Additional backends implement this function

graphblas : OpenMP-enabled sparse linear algebra backend.