Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
networkx.algorithms.core.k_truss¶

k_truss
(G, k)[source]¶ Returns the ktruss of
G
.The ktruss is the maximal induced subgraph of
G
which contains at least three vertices where every edge is incident to at leastk2
triangles. Parameters
 GNetworkX graph
An undirected graph
 kint
The order of the truss
 Returns
 HNetworkX graph
The ktruss subgraph
 Raises
 NetworkXError
The ktruss is not defined for graphs with self loops or parallel edges or directed graphs.
Notes
A kclique is a (k2)truss and a ktruss 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.
Ktrusses were originally defined in [2] which states that the ktruss is the maximal induced subgraph where each edge belongs to at least
k2
triangles. A more recent paper, [1], uses a slightly different definition requiring that each edge belong to at leastk
triangles. This implementation uses the original definition ofk2
triangles.References
 1
Bounds and Algorithms for ktruss. 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.