Louvain Community Detection Algorithm in Codebase Memory: Detecting Functional Modules

The Louvain community detection algorithm in codebase-memory-mcp identifies functional modules by grouping functions, methods, and classes into communities based on their call relationships, using a Leiden-enhanced implementation in the SQLite-backed store.

The codebase-memory-mcp repository implements a sophisticated graph analysis pipeline to discover functional modules within software projects. At its core lies a Leiden-enhanced Louvain community detection algorithm that processes call graphs extracted from the SQLite store. This system organizes functions, methods, and classes into cohesive communities that represent logical architectural units.

How the Leiden-Enhanced Louvain Algorithm Works

The implementation operates through a three-stage pipeline defined in src/store/store.c. Each stage transforms the raw codebase data into a partitioned community structure.

Stage 1: Graph Construction – The arch_clusters() function (lines 5317‑5742) queries the database to build the analysis graph. It collects all function-like nodes (functions, methods, and classes) and the CALLS edges linking them, storing edges in an array of cbm_louvain_edge_t structures.

Stage 2: Leiden Community Detection – The cbm_leiden() function (lines 5084‑5113) orchestrates the actual community detection. This enhanced Louvain implementation iterates through three phases until the partition stabilizes: local moving, refinement, and aggregation.

Stage 3: Result Mapping – The cbm_louvain() wrapper (lines 5184‑5187) provides a simplified interface with a fixed resolution parameter of 1.0, returning an array of cbm_louvain_result_t structures that map each node to its assigned community.

Core Data Structures

The algorithm uses lightweight structures defined in src/store/store.h to represent graph elements and results.

The edge structure uses 64-bit node identifiers:

typedef struct {
    int64_t src;
    int64_t dst;
} cbm_louvain_edge_t;          // defined in store.h lines 625-630

The result structure maps each node to its community:

typedef struct {
    int64_t node_id;   // original node id
    int     community; // assigned community number
} cbm_louvain_result_t;       // defined in store.h lines 631-637

Implementation Flow in src/store/store.c

The algorithm implementation follows a precise extraction and optimization sequence.

Node and Edge Extraction

The arch_clusters() function first queries the nodes table for all rows where label equals Function, Method, or Class (lines 5230‑5250). It then extracts all CALLS edges where both endpoints exist in the previously gathered node set (lines 5272‑5399).

Leiden Optimization Phases

The heavy lifting occurs in cbm_leiden() (lines 5084‑5113), which implements the Leiden algorithm through three recursive phases:

• Local Moving (leiden_move): Reassigns each node to the neighboring community that maximizes modularity gain.
• Refinement (leiden_refine): Ensures each community remains internally connected, merging sub-communities when necessary.
• Aggregation (leiden_aggregate): Contracts each refined community into a super-node, creating a coarser graph for the next iteration.

These phases execute in a loop until the coarse graph stops changing, at which point the optimal partition has been found.

Resolution Control

The public API cbm_louvain() hardcodes the resolution parameter to 1.0 (lines 5184‑5187), maintaining the classic Louvain granularity. Higher resolution values would produce smaller communities, while lower values merge communities into larger modules.

Practical Usage and Code Examples

Unit Test Implementation

The test suite in tests/test_store_arch.c demonstrates direct API usage with synthetic graphs:

const int64_t nodes[] = {1,2,3,4,5};
cbm_louvain_edge_t edges[] = {{1,2},{2,3},{1,3},{4,5}};
cbm_louvain_result_t *result = NULL;
int count = 0;

int rc = cbm_louvain(nodes, 5, edges, 4, &result, &count);
if (rc == CBM_STORE_OK) {
    for (int i = 0; i < count; ++i) {
        printf("Node %ld → community %d\n", 
               result[i].node_id, result[i].community);
    }
    free(result);  // caller owns the buffer
}

Client Integration

Client code typically accesses the algorithm through the architecture extraction API:

#include "codebase_memory_mcp/store.h"

void analyze_modules(const cbm_store_t *store, const char *project) {
    cbm_architecture_info_t arch = {0};
    
    if (cbm_store_arch(store, project, NULL, &arch) == CBM_STORE_OK) {
        for (int i = 0; i < arch.cluster_count; ++i) {
            const cbm_cluster_info_t *c = &arch.clusters[i];
            printf("Module %d: %d members, cohesion %.2f\n",
                   c->id, c->members, c->cohesion);
        }
        free(arch.clusters);
    }
}

The cbm_store_arch() function internally calls arch_clusters(), which triggers the full Louvain pipeline to populate the cbm_cluster_info_t structures with community identifiers, cohesion metrics, and representative packages.

Key Files and Functions

• src/store/store.h – Public API declarations for cbm_louvain, cbm_louvain_edge_t, and cbm_louvain_result_t.
• src/store/store.c (lines 5317‑5742) – arch_clusters() builds the functional module graph from SQLite data.
• src/store/store.c (lines 5084‑5113) – cbm_leiden() implements the Leiden algorithm entry point.
• src/store/store.c (lines 4970‑5070) – Core Leiden phases: leiden_move, leiden_refine, and leiden_aggregate.
• src/store/store.c (lines 5184‑5187) – cbm_louvain() provides the public wrapper with default resolution.
• tests/test_store_arch.c – Unit tests including louvain_basic, louvain_empty, and louvain_converges.

Summary

• The Louvain community detection algorithm in codebase-memory-mcp uses a Leiden-enhanced implementation to partition code into functional modules.
• Three-phase execution includes graph construction (arch_clusters), iterative optimization (cbm_leiden), and result mapping (cbm_louvain).
• Data structures cbm_louvain_edge_t and cbm_louvain_result_t handle graph edges and community assignments with 64-bit node identifiers.
• Default resolution is fixed at 1.0 in the public API, matching the classic Louvain modularity optimization.
• Memory management requires callers to free the result buffer returned by cbm_louvain(), as the library does not retain ownership.

Frequently Asked Questions

What is the difference between Louvain and Leiden in this implementation?

The codebase uses a Leiden-enhanced algorithm where cbm_leiden() adds a refinement phase to the classic Louvain method. While standard Louvain only performs local moving and aggregation, the Leiden implementation in src/store/store.c (lines 4970‑5070) includes leiden_refine() to guarantee that communities remain internally connected, preventing the fragmentation issues that can occur with basic Louvain.

How does the algorithm determine which nodes to include in the analysis?

The arch_clusters() function specifically filters for nodes with labels of Function, Method, or Class when querying the SQLite store (lines 5230‑5250). It then filters CALLS edges to include only those where both source and target exist in this filtered node set, ensuring the community detection operates exclusively on callable code elements and their direct relationships.

What happens when the algorithm reaches convergence?

When the coarse graph stops changing between iterations, cbm_leiden() exits its optimization loop (lines 5084‑5113) and returns the final community assignments. The wrapper cbm_louvain() then packages these into an array of cbm_louvain_result_t structures. The algorithm guarantees that the returned partition is locally optimal with respect to modularity at the specified resolution.

Can I adjust the granularity of the detected modules?

While the public cbm_louvain() function fixes the resolution parameter at 1.0 (lines 5184‑5187), you could theoretically call cbm_leiden() directly with different resolution values. Resolution values greater than 1.0 produce smaller, more granular communities, while values less than 1.0 merge communities into larger functional modules. However, the standard API maintains the classic Louvain setting for consistent behavior across the MCP interface.

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