# How Leiden Community Detection Works in code-review-graph

> Learn how Leiden community detection works in code-review-graph. Discover its igraph implementation, resolution scaling, and post-processing for accurate code entity clustering.

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

---

**The Leiden algorithm in code-review-graph partitions code entities into tightly-coupled communities using a resolution-scaled, seeded igraph implementation with post-processing steps for test reassignment and oversized cluster splitting.**

The code-review-graph project leverages the **Leiden algorithm** to discover cohesive groups of functions, classes, and other code entities within its knowledge graph. Implemented primarily in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py), the detection pipeline combines deterministic random seeding, adaptive resolution parameters, and domain-specific refinements to produce stable, human-readable code communities.

## Core Algorithm Implementation

The Leiden detection follows a structured pipeline that begins with dependency checks and ends with refined community labels. The process is encapsulated in the `_detect_leiden` function within [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py).

### Dependency Check and Deterministic Seeding

The algorithm first verifies that the **igraph** library is available through a guarded import at lines 33-39. If the import fails, the system sets `IGRAPH_AVAILABLE` to `False` and falls back to `_detect_file_based`, which groups nodes by filesystem directory structure instead of graph topology.

Reproducibility is enforced through a configurable random seed. The default `_LEIDEN_SEED` is set to `42` at line 17, though this can be overridden via the `CRG_LEIDEN_SEED` environment variable (lines 13-14 and 21). This seed is passed directly to the igraph community detection call to ensure identical partitions across runs.

### Graph Construction and Resolution Scaling

Before clustering, the code constructs an undirected igraph instance from the internal graph store. It maps qualified node names to integer indices using `qn_to_idx` and `idx_to_node` dictionaries, deduplicates edges, and applies weights from the `EDGE_WEIGHTS` configuration (lines 68-82).

The **resolution parameter** adapts to graph size according to the formula `max(0.05, 1.0 / math.log10(max(n_nodes, 10)))` (lines 4-6). This inverse logarithmic scaling produces coarser clusters for larger codebases, preventing fragmentation in extensive repositories while maintaining granularity for smaller projects.

### Running the Leiden Algorithm

The actual detection occurs at lines 18-22 with the call `g.community_leiden(..., n_iterations=2)`. The method runs for exactly two iterations using the computed resolution and seeded random generator, balancing computational efficiency with partition quality.

## Post-Processing and Refinement

Raw partitions undergo several domain-specific transformations to improve utility for code review workflows.

### Test Node Reassignment

After initial partitioning, the `_reassign_test_nodes` function (lines 38-44) migrates test files to communities containing the most unique subjects they test. This ensures test code remains colocated with the implementation it validates rather than forming isolated clusters.

### Size Filtering and Cohesion Calculation

The pipeline filters communities against a configurable `min_size` threshold. For surviving clusters, `_compute_cohesion_batch` calculates the ratio of internal edges to total edges, providing a quantitative measure of community tightness (lines 38-45).

### Naming and Deduplication

Human-readable labels are generated via `_generate_community_name` (lines 52-54), which analyzes common file prefixes, dominant class names, and frequent keywords within each cluster. The `_dedupe_community_names` function (lines 52-57) then resolves collisions by appending keywords or numeric suffixes.

### Splitting Oversized Communities

When a community exceeds a configurable percentage of the total graph size, `_split_oversized` (lines 62-70) recursively applies Leiden detection to the subgraph. This prevents monolithic clusters that span unrelated subsystems while preserving the hierarchical structure of large codebases.

## Practical Usage Examples

The following examples demonstrate how to invoke the detection pipeline from Python.

### Basic Community Detection

To detect communities with a minimum size of three nodes:

```python
from code_review_graph.communities import detect_communities

# store is a GraphStore instance containing the parsed code graph

communities = detect_communities(store, min_size=3)

for community in communities:
    print(f"{community['name']}: size={community['size']}, cohesion={community['cohesion']}")

```

### Incremental Detection

For CI/CD workflows, detect communities only for affected files:

```python
from code_review_graph.communities import incremental_detect_communities

changed_files = ["src/auth.py", "tests/test_auth.py"]
count = incremental_detect_communities(store, changed_files, min_size=2)
print(f"Re-detected {count} communities")

```

### Persisting Results

Store detected communities back to the database:

```python
from code_review_graph.communities import store_communities

persisted = store_communities(store, communities)
print(f"Persisted {persisted} communities")

```

## Summary

- The Leiden algorithm implementation lives in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) and requires the **igraph** library.
- **Deterministic seeding** via `CRG_LEIDEN_SEED` ensures reproducible partitions, defaulting to seed `42`.
- **Adaptive resolution** scales inversely with the logarithm of node count to maintain cluster coherence in large repositories.
- **Post-processing** includes test reassignment, cohesion calculation, oversized cluster splitting via `_split_oversized`, and intelligent naming.
- A **file-based fallback** activates automatically when igraph is unavailable, grouping by directory structure.

## Frequently Asked Questions

### What happens if the igraph library is not installed?

If the import fails at lines 33-39, the system routes calls to `_detect_file_based`, which groups entities by their filesystem directory structure instead of using graph-based clustering. This ensures the tool remains functional even without the optional dependency.

### How does the resolution parameter adapt to different repository sizes?

The resolution is computed as `max(0.05, 1.0 / math.log10(max(n_nodes, 10)))`, meaning larger graphs receive smaller resolution values. This produces fewer, larger communities in big codebases to prevent excessive fragmentation while preserving granularity for smaller projects.

### Why are test files reassigned after initial detection?

The `_reassign_test_nodes` function moves test files to communities containing the implementation code they test, based on analysis of unique subjects. This keeps related test and source code together for more meaningful review groups rather than allowing tests to form isolated clusters.

### Can the random seed be changed for non-deterministic results?

Yes. While the default seed is `42`, setting the `CRG_LEIDEN_SEED` environment variable overrides this value. Removing the seed or changing it produces different partitions, though deterministic behavior is generally preferred for reproducible builds and consistent CI/CD outputs.