Community Detection Consensus Eval

---
name: community-detection-consensus-eval
description: Evaluates the stability, uncertainty quantification, and accuracy of consensus-based community detection algorithms against ground-truth partitions on synthetic and real-world benchmark networks. Use when the user wants to benchmark on Zachary's Karate Network, LFR Benchmark, Ring of Cliques (RC) Benchmark, or asks about evaluating this task. Reports NMI.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 2408.02959
  bibtex_key: morea2024consensuscommunitydetection
  confidence: high
---

# 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

```python
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

```bibtex
@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