k_truss#

Returns the k-truss of G.

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

Parameters:

GNetworkX graph: An undirected graph
kint: The order of the truss

Returns:

HNetworkX graph: The k-truss subgraph

Raises:

NetworkXNotImplemented: If G is a multigraph or directed graph or if it contains self loops.

Notes

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

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

K-trusses were originally defined in [2] which states that the k-truss is the maximal induced subgraph where each edge belongs to at least k-2 triangles. A more recent paper, [1], uses a slightly different definition requiring that each edge belong to at least k triangles. This implementation uses the original definition of k-2 triangles.

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

cugraph : GPU-accelerated backend.

graphblas : OpenMP-enabled sparse linear algebra backend.