Function leiden_refine

src/store/store.c:6913–6985

Refinement phase: within each move-phase community, merge singleton nodes * into the best connected sub-community (positive modularity gain, edge must * exist). This re-derives communities bottom-up so each one is guaranteed * internally connected — the defect single-level Louvain suffers from, which * fragments the graph into hundreds of tiny noisy clusters. Writes * sub-community labels int

 * fragments the graph into hundreds of tiny noisy clusters. Writes
 * sub-community labels into refined[] and returns their count. */
static int leiden_refine(const cbm_lg_t *g, const int *comm, double gamma, double twom,
                         int *refined) {
    int n = g->n;
    double *stot = calloc((size_t)n, sizeof(double));
    double *acc = calloc((size_t)n, sizeof(double));
    int *rsize = malloc((size_t)n * sizeof(int));
    int *dirty = malloc((size_t)n * sizeof(int));
    if (!stot || !acc || !rsize || !dirty) {
        free(stot);
        free(acc);
        free(rsize);
        free(dirty);
        for (int i = 0; i < n; i++) {
            refined[i] = i;
        }
        return leiden_relabel(refined, n);
    }
    for (int i = 0; i < n; i++) {
        refined[i] = i;
        stot[i] = g->k[i];
        rsize[i] = 1;
    }
    for (int v = 0; v < n; v++) {
        if (rsize[refined[v]] != 1) {
            continue; /* only singletons merge, per the refinement rule */
        }
        int cv = comm[v];
        int ndirty = 0;
        for (int e = g->off[v]; e < g->off[v + 1]; e++) {
            int u = g->nbr[e];
            if (u == v || comm[u] != cv) {
                continue; /* stay within the move-phase community */
            }
            int ru = refined[u];
            if (acc[ru] == 0.0) {
                dirty[ndirty++] = ru;
            }
            acc[ru] += g->w[e];
        }
        int rv = refined[v];
        double kv = g->k[v];
        stot[rv] -= kv;
        int best_r = rv;
        double best_gain = 0.0;
        for (int d = 0; d < ndirty; d++) {
            int r = dirty[d];
            if (r == rv) {
                continue;
            }
            double gain = acc[r] - gamma * kv * stot[r] / twom;
            if (gain > best_gain) {
                best_gain = gain;
                best_r = r;
            }
        }
        if (best_r != rv) {
            refined[v] = best_r;
            stot[best_r] += kv;