# Leiden Community Detection and Oversized Community Splitting in code-review-graph

> Explore how the Leiden algorithm in code-review-graph detects communities and splits oversized clusters for efficient code knowledge analysis. Learn about its automatic recursive splitting.

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

---

**The `code-review-graph` library uses the Leiden algorithm from igraph to cluster code-knowledge graph nodes into tightly-coupled communities, with automatic recursive splitting for clusters exceeding 25% of total nodes.**

The `code-review-graph` project applies advanced network science to software architecture analysis. Its **Leiden community detection** implementation transforms raw code dependencies into meaningful clusters—while its **oversized community splitting** mechanism ensures no single community dominates the graph. Understanding these algorithms is essential for interpreting the architecture overviews and coupling warnings the library produces.

## How the Leiden Algorithm Is Implemented

The community detection pipeline lives in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py). When the optional **igraph** package is available, the system executes a ten-step process culminating in the Leiden optimization.

### Optional Dependency Handling and Setup

The detection begins with a defensive import strategy. At line 33, the code attempts `import igraph`; failure triggers automatic fallback to a pure-Python file-based detector. This design ensures the library remains functional across diverse environments without mandating heavy native dependencies.

Node and edge translation follows immediately. The system constructs two bidirectional mappings:

- `qn_to_idx`: Maps qualified node names to contiguous integers for igraph
- `idx_to_node`: Reverses the mapping for result translation

These dictionaries appear at line 68, enabling efficient conversion between the library's `GraphNode` objects and igraph's vertex indices.

### Graph Construction and Parameter Scaling

Edge assembly (line 84) traverses all `GraphEdge` instances, converting each to `(src_idx, tgt_idx)` pairs. Undirected edges are deduplicated, and weights are assigned based on edge kind—`CALLS`, `IMPORTS_FROM`, and other relationship types receive differentiated weights that influence community boundaries.

The resolution parameter receives special treatment at line 100. Rather than using a fixed value, the system computes:

```

resolution ∝ 1 / log(node_count)

```

This logarithmic scaling yields **coarser clusters for very large repositories**, preventing fragmentation when analyzing enterprise-scale codebases.

Determinism is guaranteed through environment variable `CRG_LEIDEN_SEED` (default: `42`), configured at line 110. This seed feeds igraph's random number generator, ensuring identical community IDs across repeated runs on the same graph—critical for CI/CD integration and regression testing.

### Core Leiden Execution

The actual algorithm invocation at line 116 uses:

```python
g.community_leiden(
    objective_function="modularity",
    weights=edge_weights,
    resolution=computed_resolution,
    n_iterations=2
)

```

The **fixed iteration count of 2** represents a deliberate trade-off: sufficient for code-dependency graphs to reach near-optimal partitions while avoiding the exponential computation blow-up that deeper optimization would incur on dense graphs.

### Post-Processing: Test Nodes and Community Assembly

After partitioning, `_reassign_test_nodes` (line 61) migrates test-only nodes. Each test node joins the community containing the largest number of *unique* subjects it exercises—preserving deterministic results while improving semantic coherence.

Community objects are built in `_detect_leiden` starting at line 138. The system:

1. Filters communities below `min_size` threshold
2. Gathers member nodes for each surviving cluster
3. Computes cohesion via `_compute_cohesion_batch` (line 87)
4. Determines dominant programming language
5. Generates human-readable community names

The cohesion computation uses a **single-pass O(edges) routine** that tallies internal versus external edges for all communities simultaneously—far more efficient than naive per-community scanning.

## Oversized Community Splitting

The most distinctive feature of this implementation is its **recursive splitting mechanism**. When a community exceeds 25% of total node count, the algorithm invokes `_split_oversized` at line 66 to fragment it into a hierarchy of sub-communities.

### The Splitting Threshold and Recursion

The 25% threshold prevents "mega-communities" that would obscure architectural structure—common in monorepos where a single module dominates connectivity. The splitting process:

1. Extracts the sub-graph induced by oversized community members
2. Re-runs Leiden detection on this subgraph with identical parameters
3. Recursively evaluates resulting sub-communities for further splitting
4. Preserves the hierarchy for downstream analysis

This recursive approach continues until all communities fall below the threshold or reach irreducible minimum size.

### Implementation Details

The actual splitting in `_split_oversized` mirrors the main detection pipeline but operates on pre-filtered node and edge sets. Cohesion scores are recomputed for sub-communities, and naming follows hierarchical conventions that preserve traceability to parent communities.

Name collisions across the final community set are resolved by `_dedupe_community_names` at line 332, which appends distinctive keywords or numeric suffixes to exact duplicates—ensuring unambiguous identification in reports and visualizations.

## Complete Detection Example

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

# Load your graph (store construction happens elsewhere in the library)

store = GraphStore(path="my_repo_graph.db")

# Detect communities—Leiden runs 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']}")
    if c.get('sub_communities'):
        print(f"  └─ Split into {len(c['sub_communities'])} sub-communities")

# Obtain architecture overview with cross-community coupling warnings

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

```

The same call automatically switches to directory-based detection if igraph is unavailable—no code modification required.

## File-Based Fallback Path

When igraph import fails, `_detect_file_based` (line 73) provides degraded but functional clustering. This implementation:

- Groups nodes by directory depth
- Applies identical cohesion computation logic
- Uses the same naming and deduplication pipelines

While lacking Leiden's optimization quality, this fallback ensures continuous operation in constrained environments and provides comparable output structures for upstream analysis.

## Key Source Files and Their Roles

| File | Responsibility |
|------|--------------|
| [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) | Core Leiden integration, test reassignment, cohesion batch computation, oversized splitting, fallback logic |
| [`code_review_graph/graph.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph.py) | `GraphNode`, `GraphEdge`, `GraphStore` definitions consumed by the detector |
| [`code_review_graph/analysis.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/analysis.py) | Higher-level utilities consuming community data (e.g., `get_architecture_overview`) |
| [`tests/test_communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/tests/test_communities.py) | Complete pipeline verification for both Leiden and file-based paths |

## Summary

- **Leiden integration** in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py) uses igraph with modularity objective, logarithmically-scaled resolution, and capped iterations for predictable performance
- **Deterministic execution** is enforced via `CRG_LEIDEN_SEED` environment variable with default value 42
- **Test node reassignment** improves semantic coherence by aligning tests with their dominant subject communities
- **Cohesion computation** uses optimized O(edges) batch processing rather than per-community scanning
- **Oversized splitting** recursively partitions communities exceeding 25% of nodes, preventing architectural obscurity
- **Seamless fallback** to directory-based detection maintains functionality without igraph

## Frequently Asked Questions

### What is the Leiden algorithm and why does code-review-graph use it?

The Leiden algorithm is a community detection method that optimizes modularity through iterative local moves and aggregation phases. `code-review-graph` selects it for its superior speed and partition quality compared to Louvain, particularly on the directed, weighted dependency graphs typical of software systems. The implementation at line 116 fixes iterations at 2 to balance optimization depth against computational cost.

### How does the 25% oversized community threshold work in practice?

Communities containing more than 25% of total graph nodes trigger `_split_oversized` at line 66. The algorithm extracts the induced subgraph and re-runs Leiden detection, producing sub-communities that are themselves evaluated for further splitting. This threshold prevents single massive clusters that would hide internal structure in monorepos or tightly-coupled legacy systems.

### Can I reproduce identical community results across different runs?

Yes, by default. The system reads `CRG_LEIDEN_SEED` (defaulting to 42) at line 110 and seeds igraph's random number generator before partitioning. Identical graph structures with identical seeds yield identical community assignments—essential for regression testing and continuous integration scenarios.

### What happens if igraph is not installed on my system?

The library gracefully degrades. The defensive import at line 33 catches the failure and routes execution to `_detect_file_based` at line 73, which clusters by directory depth while preserving all downstream cohesion computation and naming logic. No code changes are required; the same `detect_communities()` call works identically.