# Community Detection Using the Leiden Algorithm in code-review-graph: A Complete Guide

> Discover how community detection with the Leiden algorithm works in code-review-graph. Learn to convert your graph, apply the algorithm, and refine results for insightful community analysis.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: how-to-guide
- Published: 2026-08-09

---

**Community detection using the Leiden algorithm in code-review-graph works by converting the internal knowledge graph into igraph format, executing the Leiden algorithm with modularity optimization and exactly two iterations, then refining results through test-node reassignment, cohesion scoring, and recursive splitting of oversized clusters.**

The `code-review-graph` repository analyzes codebases as knowledge graphs where functions, classes, and files are nodes connected by dependency edges. To identify tightly-coupled code units, the library implements community detection using the Leiden algorithm, falling back to directory-based clustering when igraph is unavailable.

## Step-by-Step Leiden Algorithm Implementation

### Optional igraph Import and Fallback Strategy

The implementation first attempts to import the `igraph` library at runtime. If the import fails, the system automatically falls back to a pure-Python file-based detector that groups nodes by directory depth.

In [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py), the conditional import occurs at line 33:

```python
try: import igraph

```

The public entry point `detect_communities(store, min_size=2)` handles this selection transparently, ensuring the same API works regardless of available dependencies.

### Graph Construction and Index Mapping

Before running the algorithm, the system translates internal graph objects into igraph-compatible integer indices. The code constructs two critical dictionaries at line 68:

- `qn_to_idx`: Maps qualified node names (e.g., `module.Class.method`) to contiguous integers
- `idx_to_node`: Reverse mapping from integers back to `GraphNode` objects

This bidirectional mapping allows the Leiden algorithm to operate on dense integer indices while preserving the ability to correlate results with original source code entities.

### Edge Weighting and Resolution Scaling

The algorithm traverses all `GraphEdge` instances at line 84 to build the edge list. Each edge converts to a `(src_idx, tgt_idx)` pair with deduplication for undirected graphs. Weights are assigned based on edge kind—`CALLS`, `IMPORTS_FROM`, and other relationship types receive different weight values to reflect coupling strength.

The resolution parameter scales inversely with the logarithm of the node count (line 100). This dynamic scaling produces coarser communities for very large repositories while maintaining granularity for smaller codebases.

### Deterministic Execution with Fixed Iterations

To ensure reproducible results across runs, the implementation respects the `CRG_LEIDEN_SEED` environment variable, defaulting to `42` if unset (line 110). This seed initializes igraph's random number generator.

The actual Leiden invocation at line 116 uses specific parameters optimized for code dependency graphs:

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

```

The **fixed iteration count of 2** prevents exponential runtime blow-up on large graphs while still achieving convergence for typical code structures.

## Post-Processing and Community Refinement

### Test Node Reassignment

After the initial partition, the system executes `_reassign_test_nodes` (line 61) to handle test files. Test-only nodes move to the community containing the largest number of unique subjects they test. This heuristic places unit tests within the same logical group as their production code targets, preserving deterministic community assignments.

### Oversized Community Splitting

Communities exceeding 25% of the total node count trigger hierarchical re-clustering through `_split_oversized` (line 66). The algorithm recursively applies Leiden to the sub-graph formed by oversized community members, producing nested sub-communities that reveal internal architecture layers.

### Optimized Cohesion Calculation

Rather than scanning edges per community, the implementation uses `_compute_cohesion_batch` (line 87) to calculate internal versus external edge ratios in a single O(edges) pass. This batch processing significantly improves performance on dense graphs by avoiding nested loops.

### Final Assembly and Naming

The `_detect_leiden` function (starting at line 138) filters communities below `min_size`, computes cohesion scores (internal edges ÷ total edges), identifies dominant programming languages, and generates readable names. The `_dedupe_community_names` utility (line 332) appends distinctive keywords or numeric suffixes to resolve exact duplicates.

## Practical Implementation Example

The following example demonstrates detecting communities in an existing graph store:

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

# Load your graph (built elsewhere in the library)

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

# Detect communities – Leiden activates 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']}")

# Get architecture overview with cross-community coupling warnings

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

```

If `igraph` is missing from the environment, the same call automatically switches to the directory-based detector defined in `_detect_file_based` (line 73) without requiring code changes.

## Summary

- **Dual-path architecture**: The system attempts Leiden algorithm detection via igraph, falling back to directory-based grouping if dependencies are unavailable.
- **Deterministic results**: Fixed random seeds (`CRG_LEIDEN_SEED`) and exactly two Leiden iterations ensure reproducible community IDs across runs.
- **Intelligent scaling**: Resolution parameters adjust inversely to log(node count), and communities exceeding 25% of nodes undergo recursive splitting.
- **Test-aware grouping**: The `_reassign_test_nodes` function co-locates test files with the production code they exercise most frequently.
- **Performance optimization**: `_compute_cohesion_batch` processes all communities in O(edges) time rather than O(nodes × edges).

## Frequently Asked Questions

### What happens if igraph is not installed?

If the `igraph` import fails, `detect_communities` automatically routes to `_detect_file_based` in [`code_review_graph/communities.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/communities.py). This fallback groups nodes by directory depth and applies the same cohesion and naming logic, ensuring the tool remains functional without external C dependencies.

### Why does the Leiden algorithm use only two iterations?

The implementation hardcodes `n_iterations=2` in the `g.community_leiden` call at line 116. According to the source comments, this count provides sufficient convergence for code-dependency graphs while preventing exponential runtime growth on large repositories. The trade-off prioritizes speed over marginal modularity gains.

### How does the system handle monolithic communities?

When a community contains more than 25% of total nodes, `_split_oversized` recursively applies the Leiden algorithm to that sub-graph. This hierarchical splitting reveals internal structure within large application layers or monolithic modules.

### What environment variables control the detection behavior?

Set `CRG_LEIDEN_SEED` to override the default random seed of `42`, ensuring deterministic results across different execution environments. No other environment variables modify the algorithm parameters; resolution and iteration counts are computed automatically based on graph topology.