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

> Discover how the Leiden algorithm detects communities in the code-review-graph repository. Learn about reproducible clustering using deterministic seeding, resolution scaling, and bounded iterations for large codebases.

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

---

**The repository clusters related code entities into communities by running the Leiden algorithm on a graph of code nodes, using deterministic seeding, resolution scaling, and bounded iterations to ensure reproducible results on large codebases.**

Community detection in `tirth8205/code-review-graph` automatically groups functions, classes, and files into cohesive clusters by applying the **Leiden algorithm** to the code graph. This process, implemented in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py), transforms raw repository structure into meaningful architectural units that power downstream analyses like impact diagnostics and architecture overviews.

## Graph Preparation and Adjacency Building

The detection process begins in `detect_communities`, which queries the `GraphStore` to collect all non-file nodes and their connecting edges. The function builds an adjacency list while logging node and edge counts for observability.

The system operates on undirected edges, assigning weights based on edge kind using the `EDGE_WEIGHTS` mapping. This allows the algorithm to respect semantic relationships—such as inheritance or import dependencies—when calculating community boundaries.

## Running the Leiden Algorithm with igraph

When `igraph` is available, the internal `_detect_leiden` function constructs an igraph instance and configures the Leiden optimization with three critical parameters for stability and performance:

- **Resolution scaling** – The resolution parameter scales inversely with graph size using the formula `max(0.05, 1 / log10(N))`. This ensures large repositories receive coarser clusters while smaller projects retain fine-grained separation.
- **Deterministic seeding** – A fixed random seed (`CRG_LEIDEN_SEED` environment variable or default `42`) guarantees identical community structures across different machines and executions.
- **Bounded iterations** – The algorithm caps iterations at `n_iterations=2` to constrain runtime on massive graphs without sacrificing partition quality.

This configuration produces reproducible community partitions optimized for software dependency graphs.

## Post-Processing and Community Refinement

After the initial partition, the pipeline applies several refinement steps to improve practical usability:

### Test Node Reassignment

Test files are initially clustered by the Leiden algorithm based on their structural position, but the `_reassign_test_nodes` function moves them to the community containing the most unique subjects they actually test. This binds tests to their implementation domains rather than leaving them in structural outliers.

### Cohesion Calculation and Size Filtering

Communities smaller than the `min_size` threshold are discarded. For remaining clusters, `_compute_cohesion_batch` calculates cohesion scores in a single O(edges) pass, measuring internal connectivity density. Meanwhile, communities occupying more than 25% of the total graph trigger `_split_oversized`, which recursively re-runs Leiden on the subgraph to prevent single massive clusters from dominating the architecture.

### Naming and Deduplication

The `_generate_community_name` function derives human-readable labels from common file prefixes, dominant class names, or frequent keywords. `_dedupe_community_names` resolves collisions by appending disambiguating suffixes before `store_communities` persists the final results to SQLite.

## Fallback and Incremental Detection

If `igraph` is not installed, the system falls back to `_detect_file_based`, grouping nodes by their containing filepath instead of algorithmic clustering.

For evolving repositories, `incremental_detect_communities` accepts a list of changed files and re-runs detection only on affected subgraphs, updating the SQLite store without recomputing the entire partition.

```python

# 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']})")

```

```python

# Incremental detection after specific 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")

```

```python

# Retrieve stored communities sorted by cohesion

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

- **Leiden algorithm** serves as the primary clustering engine in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py), operating on an igraph representation of the code dependency graph.
- **Resolution scaling** (`max(0.05, 1 / log10(N))`) and **deterministic seeding** (default `42`) ensure reproducible, repository-size-appropriate partitions.
- **Post-processing** includes test reassignment, cohesion calculation, oversized community splitting (>25% threshold), and intelligent naming before SQLite storage.
- **Fallback** to file-based grouping occurs when `igraph` is unavailable, while `incremental_detect_communities` supports efficient updates for changing codebases.

## Frequently Asked Questions

### Why does the code use the Leiden algorithm instead of Louvain?

The Leiden algorithm provides guaranteed convergence and produces higher-quality partitions than Louvain by refining the clustering through a fast local move phase followed by aggregation. According to the source code in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py), this guarantees well-connected communities that better represent actual software modules.

### How does the system ensure reproducible community detection results?

Reproducibility is enforced through a fixed random seed controlled by the `CRG_LEIDEN_SEED` environment variable (defaulting to `42`) and deterministic resolution calculations based solely on graph size. These settings eliminate stochastic variation across different machines and execution times.

### What happens if igraph is not installed in the environment?

When `igraph` is unavailable, the detection pipeline automatically falls back to `_detect_file_based`, which groups code entities by their containing directory and filename patterns rather than graph topology. This ensures the tool remains functional while sacrificing algorithmic clustering quality.

### How are community names generated from the detected clusters?

The `_generate_community_name` function analyzes each community's members to extract common file path prefixes, dominant class names, or frequently occurring keywords. If multiple communities generate identical names, `_dedupe_community_names` appends numerical suffixes to maintain unique identifiers in the database.