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
G (NetworkX graph) – An undirected graph
k (int) – The order of the truss
 Returns
H – The ktruss subgraph
 Return type
NetworkX graph
 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.