cugraph.k_truss

cugraph.k_truss(G: Graph, k: int) → Graph

Returns the K-Truss subgraph of a graph for a specific k.

The k-truss of a graph is a subgraph where each edge is incident to at least (k−2) triangles. K-trusses are used for finding tighlty knit groups of vertices in a graph. A k-truss is a relaxation of a k-clique in the graph. Finding cliques is computationally demanding and finding the maximal k-clique is known to be NP-Hard.

Parameters:

GcuGraph.Graph

cuGraph graph descriptor with connectivity information. k-Trusses are defined for only undirected graphs as they are defined for undirected triangle in a graph.

kint

The desired k to be used for extracting the k-truss subgraph.

Returns:

G_trusscuGraph.Graph

A cugraph graph descriptor with the k-truss subgraph for the given k.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> k_subgraph = cugraph.k_truss(G, 3)