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

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, 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.

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

# 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")

# 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, 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, 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.

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