Community Detection Consensus Eval

community-detection-consensus-eval

Enhancing Stability and Assessing Uncertainty in Community Detection through a Consensus-based Approach — Morea et al. (2024) (arXiv:2408.02959, 2024)

What this evaluates

Evaluates the stability, uncertainty quantification, and accuracy of consensus-based community detection algorithms against ground-truth partitions on synthetic and real-world benchmark networks.

Datasets

• Zachary's Karate Network — total ?; splits: test (-1)
• LFR Benchmark — total ?; splits: test (-1)
• Ring of Cliques (RC) Benchmark — total ?; splits: test (-1)

Metrics

• NMI (primary) — range: [0, 1]
  • Normalized Mutual Information measuring the similarity between the predicted partition and the ground-truth partition based on the contingency table of cluster assignments.
• Stability (S) — range: [0, 1]
  • Mean NMI computed across all pairs of stochastic partitions generated during the consensus procedure. Ideally yields S = 1.0.
• k/k0 — range: other
  • Ratio of the number of detected communities (k) to the true number of communities (k0). Values closer to 1 indicate better count accuracy.
• Uncertainty coefficient (γ) — range: [0, 1]
  • Per-node measure of assignment variability across stochastic runs, summarized as the fraction of nodes with γ > 0 or the median γ across the network.

Input / output format

Input: Undirected graph represented as an adjacency matrix or edge list, with optional ground-truth community labels for supervised evaluation.

Output: A partition of nodes into communities (integer labels per node), plus an optional per-node uncertainty coefficient γ ∈ [0, 1].

Scoring recipe

def compute_nmi(partition_A, partition_B):
    # Standard NMI based on contingency table of cluster assignments
    return normalized_mutual_information(partition_A, partition_B)

def compute_stability(partitions):
    nmi_scores = []
    for i in range(len(partitions)):
        for j in range(i + 1, len(partitions)):
            nmi_scores.append(compute_nmi(partitions[i], partitions[j]))
    return mean(nmi_scores)

def compute_k_ratio(predicted_k, true_k):
    return predicted_k / true_k

def compute_gamma_summary(node_uncertainties):
    return mean(node_uncertainties), sum(1 for g in node_uncertainties if g > 0) / len(node_uncertainties)

Common pitfalls

• Confusing the resolution parameter r (controls granularity in single trials) with the mixing parameter μ (controls ground-truth fuzziness in benchmarks).
• Treating the uncertainty coefficient γ as a hard classification threshold rather than a continuous measure of assignment variability across stochastic runs.
• Ignoring the computational trade-off when selecting the iteration count t, as stability plateaus vary by algorithm and network structure.

Evidence (verbatim from paper)

Performance is assessed with two indicators: NMI (similarity between the identified communities and the built-in communities), and the normalized number of communities (k / k0).

Citation

@misc{morea2024consensuscommunitydetection,
  title={Enhancing Stability and Assessing Uncertainty in Community Detection through a Consensus-based Approach},
  author={Morea et al. (2024)},
  year={2024},
  note={arXiv:2408.02959}
}

• arXiv: 2408.02959