k_truss#
- k_truss(G, k)[source]#
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 leastk-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 leastk
triangles. This implementation uses the original definition ofk-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
- cugraphGPU-accelerated backend.
Currently raises
NotImplementedError
for graphs with more than one connected component when k >= 3. We expect to fix this soon.
graphblas : OpenMP-enabled sparse linear algebra backend.