Skip to main content
`Ctrl`+`K`

# k_truss

k_truss(G, k)

  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:
    G NetworkX graph

      An undirected graph

    k int

      The order of the truss

  Returns:
    H NetworkX 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))