cugraph.k_truss

cugraph.k_truss(G: Union[Graph, networkx.Graph], k: int) → Union[Graph, networkx.Graph]

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

NOTE: this function is currently not available on CUDA 11.4 systems.

The k-truss of a graph is a subgraph where each edge is part of 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 and was define in [1]. Finding cliques is computationally demanding and finding the maximal k-clique is known to be NP-Hard.

Parameters:

GcuGraph.Graph or networkx.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 or networkx.Graph

A cugraph graph descriptor with the k-truss subgraph for the given k. The networkx graph will NOT have all attributes copied over

Examples

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