cuGraph Community Algorithms#

Zachary Karate Community Graph

The RAPIDS cuGraph Community folder contains a collection of Jupyter Notebooks that demonstrate algorithms to identify clusters or communities that are tightly related within the structure of the graph. In the diagram above, the color-encoded communities are determined my maximizing modularity and are likely answers to questions like:

  • What communities(clusters) within the graph have the most internal interaction but less external interaction?

  • How many and what size are the communities within the graph?

  • How strongly are they connected?

  • Are there overlapping communities?

Different algorithms work faster and better on different graphs (directed, weighted, sparse)? New notebooks are being created and available here

Summary#

Algorithm Notebooks Containing Description
Louvain Community Louvain and Leiden Extracts clusters based on comparing existing edges to a random distribution
Leiden Community Louvain and Leiden Efficiency improvement over Louvain that creates connected clusters only
Spectral Clustering Spectral Clustering Uses Eigenvectors and Laplacian to cluster graph
Subgraph Extraction Subgraph-Extraction Creates a subgraph including all edges of the supplied nodelist
Triangle Counting Triangle Counting Counts the number of fully connected triples in the graph
K Truss K Truss Returns the largest relaxed clique (k-truss) in the graph