How the Leiden Community Detection Algorithm Works in code-review-graph

The Leiden community detection algorithm clusters related code entities into communities by optimizing modularity on a dependency graph, using resolution scaling, deterministic seeding, and capped iterations to ensure fast, reproducible results across large repositories.

The tirth8205/code-review-graph repository implements the Leiden community detection algorithm to automatically group functions, classes, and files into logical communities based on their relationships. This process, defined in code_review_graph/communities.py, transforms code dependencies into a weighted graph structure and applies the Leiden method to discover architectural boundaries without manual configuration.

Graph Preparation and Node Collection

The detection process begins in the detect_communities function, which prepares the graph by extracting all non-file nodes from the GraphStore and fetching their connecting edges. The function builds an adjacency list representation and logs the total node and edge counts to provide visibility into the graph size before processing begins.

This preparation step ensures that only relevant code entities—functions, classes, and methods—are considered for clustering, while file nodes serve as structural containers in the underlying storage.

Leiden Detection with igraph

When the igraph library is available, the system invokes _detect_leiden to execute the algorithm. This function constructs an undirected igraph instance, adding a single edge per node pair to avoid duplicate connections. Edge weights are assigned according to the EDGE_WEIGHTS mapping, which differentiates relationship types based on edge kind (e.g., imports, inheritance, function calls).

The Leiden algorithm optimizes modularity by greedily moving nodes between communities, then refining the partition to ensure all communities are well-connected. This two-phase approach prevents degenerate partitions and produces higher-quality clusters than simpler methods like Louvain.

Resolution Scaling and Deterministic Seeding

To handle repositories of varying sizes, the implementation dynamically scales the resolution parameter inversely with graph size. The resolution is calculated as max(0.05, 1 / log10(N)), where N represents the number of nodes. Large repositories receive coarser clustering (lower resolution), while smaller projects retain finer granularity.

Reproducibility is enforced through deterministic random seeding. The code checks for a CRG_LEIDEN_SEED environment variable, defaulting to 42 if not set. This ensures that community assignments remain identical across repeated runs and different machines, critical for consistent code review workflows.

Bounded Iterations for Performance

Runtime is controlled by capping the Leiden optimization at 2 iterations (n_iterations=2). This limit keeps execution time bounded when processing large graphs with thousands of nodes and edges, while still achieving high-quality partitions. The bounded approach balances community quality against the latency requirements of interactive code review tools.

Post-Processing and Community Refinement

After initial detection, communities undergo several refinement steps:

• Test Node Reassignment: The _reassign_test_nodes function moves test files to the community containing the most unique subjects they test, aligning tests with their corresponding implementation code.
• Cohesion Calculation: The _compute_cohesion_batch function computes community cohesion scores in a single O(edges) pass, measuring internal connectivity strength.
• Size Filtering: Communities smaller than the min_size threshold are discarded to prevent noise from isolated or trivial groupings.
• Semantic Naming: The _generate_community_name function creates human-readable labels by analyzing common file prefixes, dominant class names, or frequent keywords found in member nodes.

Fallback Strategies and Edge Case Handling

If igraph is not installed, the system gracefully degrades to _detect_file_based, which groups entities by their containing files rather than graph topology. This ensures community detection remains functional in constrained environments.

For communities that dominate more than 25% of the total graph—indicating overly broad clusters—the _split_oversized function recursively re-runs Leiden on the subgraph. This prevents single communities from swallowing entire codebases and maintains meaningful granularity in monolithic architectures.

Storage and Deduplication

Final results pass through _dedupe_community_names to resolve naming collisions before storage. The store_communities function persists community data, member assignments, and cohesion scores to the SQLite-backed GraphStore, enabling retrieval via get_communities for downstream analysis and visualization tools.

Code Examples

# Detect all communities in a freshly built graph

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

store = GraphStore(path="my_repo_graph.db")
communities = detect_communities(store, min_size=5)
for c in communities:
    print(f"{c['name']} (size={c['size']}, cohesion={c['cohesion']})")

# Incremental detection after files change

from code_review_graph.communities import incremental_detect_communities

changed = ["src/module_a.py", "tests/test_module_a.py"]
num_updated = incremental_detect_communities(store, changed_files=changed, min_size=5)
print(f"Re-detected {num_updated} communities")

# Retrieve communities sorted by cohesion score

from code_review_graph.communities import get_communities

high_cohesion = get_communities(store, sort_by="cohesion", min_size=10)
for c in high_cohesion[:5]:
    print(c["name"], c["cohesion"])

Summary

• The Leiden community detection algorithm in code_review_graph/communities.py clusters code entities by optimizing modularity on a weighted dependency graph.
• Resolution scales automatically with repository size (max(0.05, 1 / log10(N))) to ensure appropriate granularity.
• Deterministic seeding via CRG_LEIDEN_SEED (default 42) and capped iterations (2) guarantee reproducible, fast execution.
• Post-processing includes test reassignment, cohesion scoring, and semantic naming to produce actionable community structures.
• Oversized communities (>25% of graph) are recursively split, while the file-based fallback ensures functionality without igraph.

Frequently Asked Questions

How does the Leiden algorithm differ from Louvain in this implementation?

The Leiden algorithm improves upon Louvain by adding a refinement phase after the greedy moving of nodes, ensuring that all communities remain well-connected and non-empty. In code_review_graph/communities.py, this refinement prevents degenerate partitions that could occur in large codebases with uneven connection densities, resulting in more stable and meaningful community structures.

Why is the resolution parameter scaled based on graph size?

The resolution parameter controls the coarseness of communities. By setting resolution to max(0.05, 1 / log10(N)), the implementation automatically adjusts for repository scale. Large graphs with thousands of nodes receive lower resolution values to prevent fragmentation into hundreds of tiny communities, while small projects retain higher resolution for fine-grained clustering without manual tuning.

What happens if igraph is not installed?

If igraph is unavailable, the detection falls back to _detect_file_based, which groups code entities strictly by their containing files. While this lacks the sophisticated relationship modeling of Leiden detection, it preserves basic structural grouping and ensures the tool remains operational in environments with limited dependencies.

How does the system ensure deterministic results across different machines?

Determinism is enforced through a configurable random seed. The code checks for the CRG_LEIDEN_SEED environment variable before falling back to seed 42. Combined with the fixed iteration limit of 2, this guarantees that the same repository always produces identical community assignments regardless of the execution environment, essential for consistent CI/CD integration and code review workflows.

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