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

> Discover how the Leiden algorithm partitions code in code-review-graph. Learn about community detection, graph partitioning, and cluster refinement for better code analysis.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: deep-dive
- Published: 2026-08-07

---

**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`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py).

```python
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`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph.py): Defines `GraphNode`, `GraphEdge`, and `GraphStore`, the data structures consumed by the community detector.
- [`code_review_graph/analysis.py`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/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`](https://github.com/tirth8205/code-review-graph/blob/main/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.