How Community Detection Using the Leiden Algorithm Clusters Code in code-review-graph

The code-review-graph repository implements community detection in code_review_graph/communities.py by constructing a weighted knowledge graph of code entities and applying the Leiden algorithm to optimize modularity, followed by post-processing steps that reassign test nodes and calculate cohesion scores.

The code-review-graph project transforms a codebase into a knowledge graph where functions, classes, and modules become discoverable clusters. When the optional igraph library is present, the system employs the Leiden algorithm to detect these communities, revealing architectural coupling and logical groupings within the source code.

Graph Construction and Edge Weighting

Community detection begins with building a weighted graph that represents code relationships. In code_review_graph/communities.py, the EDGE_WEIGHTS mapping defines the strength of connections between entities:

• CALLS = 1.0 represents function or method invocations
• IMPORTS_FROM = 0.5 captures module dependencies

These weights create an undirected igraph.Graph where vertices represent code entities (functions, classes, etc.) and edges reflect structural relationships like calls, imports, and inheritance. The weight list attaches directly to the graph object before clustering begins.

Running the Leiden Algorithm

The core clustering logic resides in the Leiden implementation that optimizes graph modularity. The algorithm configuration in code_review_graph/communities.py prioritizes reproducibility and performance through three key mechanisms:

1. Deterministic seeding – Uses the CRG_LEIDEN_SEED environment variable or defaults to 42 to guarantee identical partitions across runs
2. Dynamic resolution – Scales the resolution parameter inversely with the logarithm of the node count, ensuring larger repositories receive appropriately coarser clusters
3. Iteration limiting – Caps execution at n_iterations=2 to bound runtime while maintaining community stability

The algorithm operates on the assumption that densely connected subgraphs represent logical code units, separating utility functions from core business logic based on call patterns and import structures.

Post-Processing and Community Refinement

After Leiden generates initial partitions, several refinement steps improve cluster quality and usefulness:

Test node reassignment – The _reassign_test_nodes helper examines test files and moves them to communities containing the most unique subjects they validate, keeping tests logically grouped with their implementation.

Cohesion scoring – The _compute_cohesion_batch function calculates a quantitative metric for each community using the formula internal_edges / (internal + external), measuring how tightly bound the cluster is compared to external connections.

Community naming – The _generate_community_name function derives human-readable labels from file path prefixes, dominant class names, or frequent keywords (e.g., service-auth-token), making raw cluster IDs meaningful to developers.

Size filtering – Clusters below the min_size threshold (default 2) are discarded to eliminate noise from isolated utility functions.

Handling Oversized Communities and Fallbacks

The system includes safeguards against degenerate clusters that capture too much of the codebase:

• Recursive splitting – Communities exceeding a configurable fraction of the total graph trigger _split_oversized, which applies Leiden recursively to the subgraph
• igraph fallback – When the igraph library is unavailable, the system gracefully degrades to file-based grouping by directory depth, ensuring the pipeline completes even in minimal environments

Public API Methods

Two primary entry points expose the community detection functionality:

detect_communities(store, min_size=2) – Runs the complete pipeline including graph construction, Leiden optimization, post-processing, and oversized splitting. Returns a list of community dictionaries containing names, members, and cohesion scores.

incremental_detect_communities(store, changed_files, min_size=2) – Optimizes for CI/CD workflows by re-running detection only when changed files affect existing communities, saving computational work for small incremental updates.

Practical Examples

Detect communities from a codebase using the Leiden algorithm:

from code_review_graph.graph import GraphStore
from code_review_graph.communities import detect_communities

# Build graph from source tree

store = GraphStore.from_path("/path/to/project")

# Detect communities (Leiden requires igraph)

communities = detect_communities(store, min_size=5)

for comm in communities:
    print(f"🗂 {comm['name']} (size={comm['size']}, cohesion={comm['cohesion']})")
    print(f"   Members: {', '.join(comm['members'][:3])}...")

For incremental updates during code reviews:

from code_review_graph.communities import incremental_detect_communities

changed = ["src/api/auth.py", "tests/test_auth.py"]
new_count = incremental_detect_communities(store, changed, min_size=5)
print(f"🔄 Re-detected {new_count} communities")

Visualizing the detected clusters:

from code_review_graph.visualization import plot_communities

plot_communities(store, output_path="architecture_graph.png")

Summary

Community detection using the Leiden algorithm in code-review-graph follows a structured pipeline:

• Constructs weighted graphs from code relationships using EDGE_WEIGHTS definitions in code_review_graph/communities.py
• Applies deterministic Leiden clustering with configurable seeds and resolution scaling
• Reassigns test nodes to their corresponding implementation communities via _reassign_test_nodes
• Calculates cohesion scores using _compute_cohesion_batch to quantify cluster tightness
• Generates human-readable names through _generate_community_name
• Splits oversized communities recursively with _split_oversized while maintaining a file-based fallback

Frequently Asked Questions

How does the Leiden algorithm handle large repositories differently than small ones?

The implementation scales the resolution parameter inversely with the logarithm of the node count in code_review_graph/communities.py. This design choice ensures that larger repositories with thousands of files receive coarser, more manageable clusters rather than fragmented micro-communities, while smaller projects retain fine-grained distinctions between modules.

What happens if igraph is not installed?

The system gracefully falls back to file-based grouping by directory depth. While this produces less precise clusters than the Leiden algorithm's modularity optimization, it guarantees that the detect_communities() function always returns valid community structures even in minimal Python environments without compiled dependencies.

How are test files prevented from forming isolated communities?

The _reassign_test_nodes helper function in code_review_graph/communities.py post-processes the Leiden partitions by analyzing which subjects each test file validates. Test nodes move to the community containing the most unique subjects they test, effectively binding unit tests to their implementation modules rather than leaving them in disconnected clusters based on import similarities.

What determines the quality score assigned to each community?

The cohesion metric calculated by _compute_cohesion_batch measures the ratio of internal edges to total edges (internal plus external). A score approaching 1.0 indicates a highly cohesive cluster where members interact primarily with each other rather than external code, while lower scores suggest boundary-spanning code that bridges multiple architectural concerns.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}