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

TLDR: The code-review-graph library clusters code entities into tightly-coupled communities by running the Leiden algorithm through igraph, then refines the raw partition by reassigning test nodes, splitting oversized clusters, and computing per-community cohesion scores.

The code-review-graph project transforms a codebase into a structured knowledge graph where functions, classes, and files are nodes and their relationships are edges. To make sense of large graphs, the repository implements community detection using the Leiden algorithm, which partitions the code into meaningful, tightly-coupled units. When the optional igraph dependency is present, the system follows a deterministic, multi-stage pipeline that scales from small packages to expansive monorepos.

Preparing the Graph for the Leiden Algorithm

Before calling the community detector, code-review-graph must translate its internal graph representation into an igraph object. This preparation happens entirely inside code_review_graph/communities.py.

Optional igraph Import and Fallback

At line 33, the module attempts to import igraph. If the import fails, the system silently falls back to a pure-Python directory-based detector implemented in _detect_file_based (line 73). This fallback groups nodes by directory depth and still applies the same cohesion and naming logic, so the public API remains unchanged.

Node and Edge Translation

The algorithm builds two lookup dictionaries: qn_to_idx, which maps each qualified node name to an integer vertex index, and idx_to_node, which maps that integer back to the original GraphNode object (line 68). It then traverses every GraphEdge to assemble an undirected edge list where duplicate connections are removed and each edge receives a weight based on its kind, such as CALLS or IMPORTS_FROM (line 84). These weights tell the Leiden algorithm which relationships are strongest.

Running the Leiden Algorithm on the Code Graph

Once the igraph object is ready, the pipeline executes the actual partition in a reproducible, resource-conscious manner.

Resolution Scaling and Deterministic Seeding

The resolution parameter is computed inversely to the logarithm of the node count (line 100). This design choice produces coarser clusters for very large repositories so that the results remain human-readable. To guarantee deterministic output across repeated runs, the code reads the CRG_LEIDEN_SEED environment variable—defaulting to 42—and seeds igraph’s random number generator before clustering (line 110).

The Leiden Call

With the graph, weights, resolution, and seed in place, the system invokes g.community_leiden with objective_function="modularity" (line 116). The call uses a fixed iteration count of 2, which the authors chose because it is sufficient for code-dependency graphs while avoiding exponential runtime blow-up on large inputs.

Refining Partitions: Test Nodes, Oversized Clusters, and Cohesion

Raw Leiden output does not always align with software architecture, so code-review-graph applies several post-processing steps.

Reassigning Test Nodes

After the initial partition, test-only nodes are reassigned via _reassign_test_nodes (line 61). Each test node moves to the community that contains the largest number of unique subjects it tests, keeping the deterministic order intact. This binds tests to the production code they exercise rather than leaving them in isolated clusters.

Splitting Oversized Communities

If any community exceeds 25 percent of the total node count, _split_oversized (line 66) recursively re-runs the Leiden algorithm on that sub-graph. This prevents a single giant cluster from swallowing an entire monorepo and yields a useful hierarchy of sub-communities.

Cohesion Scoring and Community Assembly

The pipeline discards communities smaller than the configurable min_size threshold. For each survivor, it gathers members and computes a cohesion score equal to internal edges divided by total edges. Rather than scanning each community individually, the code uses _compute_cohesion_batch (line 87), a single-pass O(edges) routine that tallies internal versus external edges for every community at once. It also determines the dominant language and generates a readable community name. Finally, _dedupe_community_names (line 332) appends distinctive keywords or numeric suffixes to resolve exact duplicates.

Public API and Usage Example

The entire workflow is exposed through the detect_communities function in code_review_graph/communities.py.

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

# 1. Load your graph (the store is built elsewhere in the library)

store = GraphStore(path="my_repo_graph.db")

# 2. Detect communities – Leiden is used automatically if igraph is installed

communities = detect_communities(store, min_size=5)

for c in communities:
    print(f"Community {c['name']!r}: {c['size']} nodes, cohesion={c['cohesion']}")

# 3. Higher-level architecture overview with cross-community coupling warnings

overview = get_architecture_overview(store)
print("Warnings:")
for w in overview["warnings"]:
    print(" •", w)

If igraph is not installed, the same call transparently switches to the file-based fallback, so no client code changes are required.

Key Files in the Detection Pipeline

• code_review_graph/communities.py: Core implementation of Leiden-based detection, test-node reassignment, cohesion calculation, oversized-community splitting, and fallback logic.
• code_review_graph/graph.py: Defines GraphNode, GraphEdge, and GraphStore, the data structures consumed by the community detector.
• code_review_graph/analysis.py: Provides higher-level utilities such as get_architecture_overview that rely on the generated community data.
• tests/test_communities.py: Test suite exercising the full detection pipeline for both Leiden and file-based paths.

Summary

• Translation layer: code_review_graph/communities.py converts internal nodes and weighted edges into an igraph representation before running the Leiden algorithm.
• Deterministic tuning: The pipeline scales resolution by graph size, fixes the random seed via CRG_LEIDEN_SEED, and caps Leiden iterations at 2.
• Post-processing: Test nodes are reassigned to the communities they exercise, oversized clusters are recursively split, and cohesion is computed in a single O(edges) pass.
• Fallback: When igraph is unavailable, _detect_file_based groups nodes by directory depth and applies the same naming and cohesion logic.
• Public API: Call detect_communities(store, min_size=2) to receive a list of named, scored community dictionaries ready for storage or display.

Frequently Asked Questions

How does code-review-graph handle repositories too large for a single Leiden run?

The system mitigates monolithic clusters through _split_oversized in code_review_graph/communities.py (line 66). Any community larger than 25 percent of the total node count is recursively re-clustered with Leiden on its sub-graph, producing smaller, hierarchical sub-communities without manual intervention.

Why does the Leiden algorithm use a fixed iteration count of 2?

According to the source in code_review_graph/communities.py (line 116), two iterations are sufficient for typical code-dependency graphs while preventing exponential runtime growth. This trade-off keeps the tool fast on large codebases without sacrificing useful partition quality.

What happens to test files during community detection?

After the raw Leiden partition, _reassign_test_nodes (line 61) moves test-only nodes into the community that contains the largest number of unique subjects they test. This ensures that tests are grouped with the production code they validate rather than forming disconnected clusters.

Can I use community detection without installing igraph?

Yes. If igraph cannot be imported, detect_communities automatically falls back to _detect_file_based (line 73), which clusters nodes by directory depth and still computes cohesion scores and readable names. The public API remains identical, so no code changes are necessary.

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