Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.core.k_truss

k_truss(G, k)

Returns the k-truss of G.

The k-truss is the maximal subgraph of G which contains at least three vertices where every edge is incident to at least k triangles.

Parameters

• G (NetworkX graph) – An undirected graph

• k (int) – The order of the truss

Returns

H – The k-truss subgraph

Return type

NetworkX graph

Raises

NetworkXError – The k-truss is not defined for graphs with self loops or parallel edges or directed graphs.

Notes

A k-clique is a (k-2)-truss and a k-truss is a (k+1)-core.

Not implemented for digraphs or graphs with parallel edges or self loops.

Graph, node, and edge attributes are copied to the subgraph.

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.