How Does Community Detection Work in code-review-graph Using the Leiden Algorithm?

The code‑review‑graph tool partitions code‑knowledge graphs into tightly‑coupled communities using the Leiden algorithm via igraph, featuring dynamic resolution scaling, deterministic seeding, and post‑processing steps that reassign test nodes and split oversized clusters.

Code‑review‑graph analyzes repository structure to build a knowledge graph of code elements, then groups related nodes into "communities" representing cohesive software modules. When the optional igraph library is available, the system employs the Leiden algorithm for community detection; otherwise it falls back to a directory‑based heuristic. This article explains the complete implementation pipeline as found in the tirth8205/code-review-graph repository.

Prerequisites and Algorithm Availability

The community detection subsystem determines its execution path at runtime based on dependency availability.

Optional igraph import

The system attempts to import igraph at module load time in code_review_graph/communities.py. If the import succeeds, the Leiden‑based detector becomes available. If igraph is absent, the code automatically routes to a pure‑Python file‑based detector that groups nodes by directory depth.

# From code_review_graph/communities.py line 33

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

The public entry point detect_communities(store, min_size=2) abstracts this choice, requiring no changes to calling code when switching between environments.

Graph Preparation and Mapping

Before invoking the Leiden algorithm, the system translates the internal graph representation into igraph‑compatible indices and weighted edges.

Node indexing

The algorithm builds bidirectional lookup dictionaries to map between qualified node names and integer vertex indices. The qn_to_idx dictionary maps each GraphNode qualified name to a contiguous integer, while idx_to_node provides the reverse mapping. This construction occurs around line 68 in code_review_graph/communities.py.

Edge construction and weighting

The system traverses all GraphEdge objects to build the edge list. It converts each edge to (src_idx, tgt_idx) pairs, deduplicates undirected edges, and assigns numerical weights based on edge semantics. CALLS, IMPORTS_FROM, and other relationship types receive distinct weight values to reflect coupling strength. This assembly happens near line 84 in the same file.

Configuring the Leiden Algorithm

The implementation tunes several Leiden parameters specifically for code‑dependency graphs rather than using generic defaults.

Dynamic resolution scaling

The resolution parameter γ is computed as inversely proportional to the logarithm of the node count around line 100. This scaling yields coarser communities for very large repositories, preventing fragmentation that would obscure high‑level architectural patterns.

# Resolution computation (simplified from source)

import math
resolution = 1.0 / math.log10(max(num_nodes, 10))

Deterministic seeding

To ensure reproducible community IDs across repeated runs, the system reads the environment variable CRG_LEIDEN_SEED (defaulting to 42) and initializes igraph's random number generator. This configuration appears near line 110 in code_review_graph/communities.py.

Fixed iteration count

The call to g.community_leiden specifies objective_function="modularity", the computed edge weights and resolution, and a fixed iteration count of 2. This limit prevents exponential runtime blow‑up on dense dependency graphs while still achieving convergence for typical code structures. The invocation occurs at line 116.

Community Post-Processing

Raw Leiden partitions undergo several refinement steps to produce meaningful software architecture clusters.

Test node reassignment

The _reassign_test_nodes method (line 61) moves test‑only nodes after initial partitioning. Each test node is reassigned to the community containing the largest number of unique subjects it tests, preserving deterministic ordering and keeping tests aligned with their production code.

Cohesion calculation

Rather than scanning edges per‑community, the _compute_cohesion_batch function (line 87) performs a single‑pass O(edges) routine that tallies internal versus external edges for all communities simultaneously. The resulting cohesion score equals internal edges divided by total edges, indicating how tightly knit each cluster is.

Oversized community splitting

Communities exceeding 25% of the total node count trigger recursive re‑clustering via _split_oversized (line 66). The algorithm extracts the sub‑graph for the oversized community and reruns Leiden on it, creating a hierarchy of sub‑communities that reveal internal structure within monolithic modules.

Name deduplication

Finally, _dedupe_community_names (line 332) disambiguates exact duplicate names by appending distinctive keywords or numeric suffixes, ensuring each community has a unique identifier for storage and display.

Implementation Example

The following example demonstrates loading a graph store and running community detection with automatic Leiden selection:

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

# Retrieve high-level architecture overview with coupling warnings

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

If igraph is missing, the identical call transparently switches to the directory‑based detector.

Key Source Files

Understanding the full workflow requires familiarity with these modules:

File	Responsibility
code_review_graph/communities.py	Core Leiden detection, test reassignment, cohesion calculation, oversized splitting, and fallback logic.
code_review_graph/graph.py	Defines GraphNode, GraphEdge, and GraphStore data structures consumed by the detector.
code_review_graph/analysis.py	Provides get_architecture_overview and other utilities that consume community data.
tests/test_communities.py	Test suite validating both Leiden and file‑based detection paths.

Summary

• Leiden algorithm integration occurs through igraph in code_review_graph/communities.py, with automatic fallback to directory‑based grouping when unavailable.
• Dynamic resolution scales inversely with log(node count) to maintain appropriate granularity across repository sizes.
• Deterministic execution is guaranteed via the CRG_LEIDEN_SEED environment variable defaulting to 42.
• Post‑processing includes moving test nodes to production communities, computing batch cohesion scores, recursively splitting oversized clusters, and deduplicating names.
• Performance optimizations include a fixed iteration count of 2 and O(edges) cohesion calculation to handle large codebases efficiently.

Frequently Asked Questions

What is the Leiden algorithm?

The Leiden algorithm is a community detection method for graphs that optimizes modularity (or other objective functions) through iterative local node moves and refinement phases. According to the code‑review‑graph source, it is preferred over alternatives because it converges quickly and produces well‑connected communities suited for code dependency analysis.

Why does the algorithm use a fixed iteration count of 2?

The implementation passes n_iterations=2 to g.community_leiden because empirical testing showed this sufficient for code‑dependency graphs while avoiding exponential runtime blow‑up on dense graphs. As implemented in code_review_graph/communities.py line 116, this limit balances clustering quality with performance on large repositories.

How does the system handle repositories without igraph?

When igraph is not installed, the detect_communities function automatically routes to _detect_file_based, which groups nodes by directory depth and applies identical cohesion and naming logic. This fallback requires no code changes from the caller and ensures the tool functions in minimal Python environments.

What is the purpose of the cohesion score?

The cohesion score quantifies community quality by calculating the ratio of internal edges to total edges (internal + external) for each cluster. Computed via _compute_cohesion_batch in O(edges) time, this metric helps identify well‑encapsulated modules versus communities that may need splitting or reorganization.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}