# How Community Detection with Leiden Algorithm Splits Large Graphs in code-review-graph

> Discover how the Leiden algorithm splits large graphs in code-review-graph. Learn about its two-stage approach for efficient community detection and recursive splitting of oversized communities.

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

---

**The code-review-graph project implements a two-stage Leiden algorithm approach that first runs community detection with capped iterations and size-adjusted resolution on the entire graph, then recursively splits oversized communities that exceed 25% of total nodes or 10 nodes minimum.**

Community detection in large codebases presents a significant challenge: naive algorithms produce thousands of tiny clusters that are useless for architecture analysis. The `code-review-graph` repository solves this by building a code knowledge graph where nodes represent code entities and edges capture relationships like calls, imports, and inheritance. When processing repositories containing hundreds of thousands of nodes, the system employs a sophisticated **two-stage Leiden algorithm** approach to generate manageable, hierarchical communities that reflect logical code zones.

## Two-Stage Leiden Algorithm Approach

The implementation in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) avoids exponential blow-up on large graphs through a carefully orchestrated pipeline that balances granularity with performance.

### Stage 1: Initial Detection with Iteration Limits

The first pass runs the Leiden algorithm once across the entire graph with strict constraints to prevent computational explosion. In `_detect_leiden` (lines 549-564), the system:

- Caps iterations at **`n_iterations=2`** to prevent the exponential runtime that previously occurred on repositories exceeding 100,000 nodes
- Scales resolution inversely with graph size using the formula: `resolution = max(0.05, 1.0 / log10(node_count))`
- Uses deterministic seeding via `CRG_LEIDEN_SEED` environment variable (fallback to `42`) for reproducible results
- Builds an undirected `igraph` with **edge weights** defined in `EDGE_WEIGHTS` to preserve relationship strength

After detection, the system reassigns test nodes to communities containing most of their tested subjects via `_reassign_test_nodes`, filters clusters smaller than `min_size`, and computes cohesion scores in batches using `_compute_cohesion_batch`.

### Stage 2: Recursive Splitting of Oversized Communities

Large monolithic communities require further decomposition without affecting well-sized clusters. The `_split_oversized` function (lines 660-720) implements this recursive refinement:

- Calculates a dynamic threshold: **`max(total_node_count * 0.25, 10)`**
- Extracts subgraphs for any community exceeding this threshold
- Re-runs Leiden detection on isolated subgraphs with fresh deterministic seeding
- Generates hierarchical metadata including `level` and `parent_id` for nested communities
- Reassigns test nodes and recomputes cohesion for each new sub-community

This targeted approach isolates dense sub-structures only where needed, preserving computational resources for the broader graph.

## Implementation Details and Key Parameters

The community detection pipeline relies on several critical implementation choices that ensure robustness across varying repository sizes.

### Graph Construction and Adjacency

The `GraphStore` class gathers all nodes (excluding file nodes) and edges, then builds an in-memory adjacency list via `_build_adjacency` for fast cohesion calculations. This preprocessing step enables efficient subgraph extraction during the oversized-community splitting phase.

### Cohesion and Quality Metrics

Each community receives a **cohesion score** calculated during the batch computation phase. This metric helps identify tightly-coupled code modules versus loosely-associated collections of files. Communities below the `min_size` threshold are filtered out to eliminate noise from tiny, insignificant clusters.

### Fallback Mechanisms

If `igraph` is unavailable in the environment, the system gracefully degrades to `_detect_file_based`, which groups nodes by directory depth. This ensures the pipeline always produces usable communities even when optional dependencies are missing.

### Naming and Deduplication

Community names derive from common file prefixes, dominant class names, or frequent keywords via `_generate_community_name`. The `_dedupe_community_names` function handles collisions, ensuring unique identifiers for downstream analysis tools in [`code_review_graph/tools/community_tools.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/tools/community_tools.py).

## Practical Usage and Code Examples

### CLI – List Communities with Size Filtering

```bash
code-review-graph communities --sort size --min-size 5

```

This command executes the two-stage detection pipeline and displays results sorted by community size, filtering out clusters smaller than five nodes.

### CLI – Generate Architecture Overview

```bash
code-review-graph architecture --detail-level standard

```

Returns a JSON object containing community metadata, cross-community edges, and high-coupling warnings using the complete Leiden workflow.

### Python API – Programmatic Community Detection

```python
from code_review_graph.graph import GraphStore
from code_review_graph.communities import detect_communities

store = GraphStore("path/to/graph.db")
communities = detect_communities(store, min_size=3)

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

```

This invokes the full detection pipeline, automatically running `_detect_leiden` followed by `_split_oversized` when communities exceed the size threshold.

### Python API – Manual Oversized Community Splitting

```python
from code_review_graph.communities import _split_oversized

# Assume `communities` is the list returned by `detect_communities`

refined = _split_oversized(
    communities, 
    store.get_all_nodes(), 
    store.get_all_edges()
)

```

Useful for experimentation with custom thresholds or post-processing specific communities.

## Summary

- **Two-stage processing** prevents exponential blow-up by capping initial iterations at 2 and using size-adjusted resolution parameters.
- **Dynamic thresholds** split communities exceeding 25% of total nodes (minimum 10 nodes) through recursive subgraph analysis.
- **Deterministic seeding** via `CRG_LEIDEN_SEED` ensures reproducible results across identical codebases.
- **Cohesion metrics** and batch processing optimize performance while maintaining analytical quality.
- **Graceful degradation** to file-based grouping when `igraph` is unavailable ensures pipeline reliability.

## Frequently Asked Questions

### How does the Leiden algorithm handle repositories with over 100,000 nodes?

The implementation caps iterations at `n_iterations=2` during the initial pass and scales resolution inversely with graph size using `max(0.05, 1.0 / log10(node_count))`. This prevents the exponential runtime growth that would otherwise occur on massive graphs while still producing meaningful initial clusters.

### What determines when a community gets split into sub-communities?

A community triggers recursive splitting when its size exceeds the threshold calculated as `max(total_node_count * 0.25, 10)`. This means communities larger than 25% of the total graph or containing more than 10 nodes (whichever is larger) undergo additional Leiden detection on their isolated subgraphs.

### Why does the resolution parameter decrease for larger graphs?

Larger graphs receive coarser resolution values (closer to 0.05) to prevent the algorithm from generating thousands of tiny, unusable clusters. The logarithmic scaling ensures that as node count increases, the algorithm favors broader communities that reflect architectural boundaries rather than microscopic implementation details.

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

The system falls back to `_detect_file_based`, which groups code entities by directory structure and depth. While less sophisticated than the Leiden approach, this ensures the community detection pipeline always produces usable results for architecture analysis even without optional dependencies.