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

> Discover how the Leiden algorithm detects communities in code-review-graph. This library clusters nodes using igraph, adaptive resolution, and post-processing for insightful code analysis.

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

---

**The `code-review-graph` library clusters code-knowledge graph nodes into tightly-coupled communities using the Leiden algorithm via igraph, with deterministic seeding, adaptive resolution scaling, and post-processing steps that reassign test nodes and split oversized clusters.**

The `code-review-graph` repository transforms repository analysis into a navigable knowledge graph by grouping related code units into communities. When the optional **igraph** library is available, the system employs the **Leiden algorithm** to partition the graph based on dependency patterns, edge weights, and structural cohesion.

## Prerequisites and Environment Setup

The detection engine first attempts to import the high-performance **igraph** library at [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) line 33. If unavailable, the system transparently falls back to a pure-Python directory-based detector without requiring code changes.

```python

# From communities.py - the optional import pattern

try:
    import igraph
    HAS_IGRAPH = True
except ImportError:
    HAS_IGRAPH = False

```

## The Leiden Detection Pipeline

The core implementation in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) follows a multi-stage pipeline to convert raw graph data into meaningful code communities.

### Node Indexing and Edge Assembly

Before running the algorithm, the system builds translation dictionaries to map between graph objects and integer indices required by igraph. The `qn_to_idx` dictionary maps qualified node names to integer indices, while `idx_to_node` provides the reverse lookup (line 68).

The edge construction phase traverses all `GraphEdge` objects, converting each to `(src_idx, tgt_idx)` pairs. Undirected edges are deduplicated, and weights are assigned based on edge kind—such as `CALLS` or `IMPORTS_FROM`—to reflect different dependency strengths (line 84).

### Adaptive Resolution and Deterministic Seeding

To ensure consistent results across runs, the system respects the `CRG_LEIDEN_SEED` environment variable (defaulting to `42`) when initializing igraph’s random number generator (line 110). The resolution parameter scales inversely with the logarithm of the node count (line 100), producing coarser clusters for larger repositories to maintain interpretability.

### Algorithm Execution

The actual clustering occurs through a call to `g.community_leiden` with `objective_function="modularity"`, passing the computed edge weights and resolution. To prevent exponential runtime growth on large codebases, the implementation fixes the iteration count at **2**, which the authors determined sufficient for code-dependency graphs (line 116).

### Post-Processing and Test Node Handling

After partitioning, the `_reassign_test_nodes` function (line 61) moves test-only nodes to the community containing the largest number of unique subjects they test. This preserves deterministic results while ensuring tests remain logically grouped with their target code.

## Optimization and Refinement Strategies

Beyond basic clustering, the system implements several refinement stages to improve community quality.

### Batch Cohesion Calculation

Rather than scanning edges repeatedly for each community, the `_compute_cohesion_batch` function (line 87) computes cohesion scores—defined as internal edges divided by total edges—in a single O(edges) pass across the entire graph.

### Recursive Splitting of Oversized Communities

Communities exceeding 25% of the total node count trigger the `_split_oversized` mechanism (line 66). This recursively applies the Leiden algorithm to the sub-graph, creating a hierarchy of sub-communities that prevents monolithic clusters in large monorepos.

### Community Naming and Deduplication

After detection, communities smaller than `min_size` are discarded. For each remaining cluster, the algorithm determines the dominant language and generates a readable name. The `_dedupe_community_names` function (line 332) resolves naming collisions by appending distinctive keywords or numeric suffixes to ensure each community has a unique identifier.

## File-Based Fallback Detection

When igraph is unavailable, the `_detect_file_based` function (line 73) groups nodes by directory depth, then applies the same cohesion calculation and naming logic to provide consistent API behavior across environments.

## Practical Usage Example

The public entry point `detect_communities(store, min_size=2)` orchestrates the entire workflow, automatically selecting the Leiden or file-based path based on library availability.

```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 will be used 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️⃣ Get a higher‑level architecture overview (cross‑community coupling warnings)

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

```

## Summary

- **Optional igraph dependency**: The system attempts to import `igraph` for Leiden algorithm support, falling back to directory-based detection if unavailable.
- **Deterministic clustering**: The `CRG_LEIDEN_SEED` environment variable (default 42) ensures reproducible community IDs across runs.
- **Adaptive resolution**: The resolution parameter scales inversely with the logarithm of node count to handle large repositories.
- **Fixed iterations**: The Leiden algorithm runs with exactly 2 iterations to balance accuracy and performance.
- **Test-aware post-processing**: The `_reassign_test_nodes` function moves test files to communities containing the code they test.
- **Oversized handling**: Communities exceeding 25% of total nodes are recursively split using `_split_oversized`.
- **Efficient cohesion**: Batch computation calculates all community cohesion scores in a single O(edges) pass.

## Frequently Asked Questions

### What happens if igraph is not installed?

If the `igraph` library is unavailable, the `detect_communities` function automatically delegates to `_detect_file_based` (line 73), which groups nodes by directory depth while preserving the same cohesion calculation and naming logic. No code changes are required to handle the fallback.

### How does the system handle test files during community detection?

After the initial Leiden partition, the `_reassign_test_nodes` function (line 61) identifies test-only nodes and moves them to the community containing the largest number of unique subjects they test. This ensures tests remain grouped with their corresponding implementation code while maintaining deterministic results.

### Why is the Leiden iteration count fixed at 2?

The implementation calls `g.community_leiden` with a fixed iteration count of 2 (line 116) because this provides sufficient convergence for code-dependency graphs while avoiding exponential runtime blow-up on large repositories. This trade-off prioritizes practical analysis speed over marginal modularity gains.

### How does code-review-graph prevent a single community from becoming too large?

The system monitors community sizes during post-processing. Any community exceeding 25% of the total node count triggers the `_split_oversized` function (line 66), which recursively applies the Leiden algorithm to that sub-graph. This hierarchical splitting prevents monolithic clusters in large monorepos while preserving the modular structure of the codebase.