cugraph.ktruss_subgraph#

cugraph.ktruss_subgraph(G: Union[Graph, networkx.Graph], k: int, use_weights=True) → Graph[source]#

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.

In contrast, finding a k-truss is computationally tractable as its key building block, namely triangle counting, can be executed in polnymomial time.Typically, it takes many iterations of triangle counting to find the k-truss of a graph. Yet these iterations operate on a weakly monotonically shrinking graph. Therefore, finding the k-truss of a graph can be done in a fairly reasonable amount of time. The solution in cuGraph is based on a GPU algorithm first shown in [2] and uses the triangle counting algorithm from [3].

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. The current implementation only supports undirected graphs.

kint

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

use_weightsbool, optional (default=True)

Whether the output should contain the edge weights if G has them.

Deprecated: If ‘weights’ were passed at the graph creation, they will be used.

Returns:

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

References

[1] Cohen, J., “Trusses: Cohesive subgraphs for social network analysis” National security agency technical report, 2008

[2] O. Green, J. Fox, E. Kim, F. Busato, et al. “Quickly Finding a Truss in a Haystack” IEEE High Performance Extreme Computing Conference (HPEC), 2017 https://doi.org/10.1109/HPEC.2017.8091038

[3] O. Green, P. Yalamanchili, L.M. Munguia, “Fast Triangle Counting on GPU” Irregular Applications: Architectures and Algorithms (IA3), 2014

Examples

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