Stochasticity in Community Detection

Why Repeated Runs Can Differ

A community-detection result is often treated as if it were a single, inevitable summary of a cell-neighborhood graph. For a randomized algorithm, that can be misleading: even when the graph and analysis settings are held fixed, different runs may return different assignments of cells to communities. This is algorithmic variability. It is not, by itself, evidence that the graph changed or that the cell data were resampled.

Randomized community-detection methods use random choices during their search. Those choices can affect which candidate assignments are considered and the path taken through possible partitions. Because methods such as Louvain and Leiden use heuristic optimization, a run may stop at a locally strong solution rather than establish that one uniquely best partition exists. Distinct partitions can also have equal or nearly equal objective scores. The important diagnostic question is therefore not merely whether the score changes, but whether the cell groupings change and how those changes relate to score differences.

A partition groups vertices into non-overlapping communities. Community labels themselves are arbitrary: the assignments \((1,1,2,2)\) and \((7,7,3,3)\) describe the same partition. Comparisons should therefore be based on which vertices are grouped together, not on the numerical names assigned to communities.

Separate Partitions From Objective Scores

An objective score summarizes a partition according to a specified criterion. For example, modularity evaluates how much more edge weight falls within communities than would be expected under its degree-based null model. For an undirected graph with nonnegative edge weights \(A_{ij}\), define \(k_i=\sum_j A_{ij}\) and \(m=\frac{1}{2}\sum_{i,j}A_{ij}\). A partition \(P\), with community label \(c_i\) for vertex \(i\), has resolution-\(\gamma\) modularity

where \(I(c_i=c_j)\) equals 1 when vertices \(i\) and \(j\) are in the same community and 0 otherwise. This expression is given here to make clear what a score comparison means; the earlier material on modularity develops the objective itself. A score is interpretable only in relation to its objective, graph, and settings. Scores from different objectives, different graphs, or different resolution parameters should not be treated as if they were on one directly comparable scale.

Repeated runs can show substantial partition variation but almost identical scores. This happens when distinct partitions are nearly tied under the chosen objective. The reverse pattern is also possible: most assignments may be similar, while a few changes involving high-weight edges noticeably change the score. Thus, report evidence about both the partitions and the objective values.

Comparing Assignments Without Depending on Labels

One direct summary of repeated assignments is the co-assignment proportion. For two vertices \(i\) and \(j\), it is the fraction of runs in which they share a community. It is 1 if they are grouped together in every run and 0 if they are separated in every run. Intermediate proportions identify pairs whose relationship varies across runs. This summary does not require community labels to match between runs.

For \(R\) runs, let \(I_r(i,j)\) equal 1 if \(i\) and \(j\) are assigned to the same community in run \(r\), and 0 otherwise. Their empirical co-assignment proportion is

A collection of these proportions forms a co-assignment matrix. It can reveal stable blocks of cells and uncertain boundaries. It is a descriptive summary of the runs, not a guarantee that the groups with high co-assignment are biologically meaningful.

What Repeated Runs Estimate

The repeated-run summaries describe a conditional distribution: the distribution of outputs produced by the selected algorithm and settings on the fixed graph. They do not measure all uncertainty in a single-cell analysis. In particular, they do not include changes that might arise from a different graph, a different set of cells, or a different analysis configuration.

If repeated runs are independent and use the same graph and settings, the frequency of a particular partition estimates its probability of appearing in a run under that procedure. To see why, define \(Z_r=1\) if run \(r\) returns that partition and \(Z_r=0\) otherwise. If its run probability is \(\pi\), then \(Z_r\) is a Bernoulli random variable with mean \(\pi\) and variance \(\pi(1-\pi)\). The observed frequency is \(\hat{\pi}=R^{-1}\sum_r Z_r\). Independence gives

Thus, the frequency is an estimate, not a known long-run probability, and a small number of runs can give an unstable estimate. This reasoning applies to the frequency of an exactly specified partition; it does not say that different partitions are equally important or that run frequency is a measure of biological plausibility.

A Practical Diagnostic Workflow

A useful repeated-run comparison keeps the graph, objective, algorithm, and all other analysis settings fixed. Otherwise, observed differences mix algorithmic variability with changes in the analysis. Record each run's partition and objective score, then inspect the frequency of recurring partitions, score summaries, and co-assignment patterns. When many distinct partitions occur, exact partition frequencies may be less informative than pairwise co-assignment, since a small local change can create a new complete partition.

Assumptions, Comparisons, and Failure Modes

The interpretation above depends on a controlled comparison. Runs must use the same graph and settings for their differences to be attributed to the randomized procedure. If a graph is directed, weighted, or processed differently between runs, the objective and its interpretation must match those features. If the graph or objective changes, score variation no longer isolates run-to-run stochasticity.

A single run is cheaper and may be adequate when the procedure is known to be reproducible for the task, but it cannot reveal output variation. Repeated runs expose that variation, at additional computational cost. Choosing the run with the largest objective score is a different strategy: it selects the best observed score among the runs, but does not show that the selected partition is unique, stable, or biologically valid. A deterministic method can avoid variation conditional on fixed inputs, but determinism alone does not establish that its result is better.

Repeated runs also differ from comparing different algorithms. For example, Louvain and Leiden need not optimize or implement precisely the same procedure; comparing their outputs changes more than the random run. And a score from one objective should not be used to declare a partition from another objective superior. Objective scores answer a criterion-specific question, not a general question of biological truth.

• Do not equate a high score with stable assignments. Several partitions can have similar objective values while assigning boundary cells differently.
• Do not equate repeated agreement with validity. An algorithm can consistently return a partition that is poorly matched to the scientific question.
• Do not compare incompatible scores. Graph, objective, resolution, and other score-defining settings must be aligned for a direct score comparison.
• Do not overinterpret small run counts. Observed frequencies and score summaries can change materially when only a few runs are performed.

The main limitation is scope: repeated runs assess variability of the algorithm conditional on the graph and settings. They do not assess sensitivity to graph construction, cell sampling, or biological interpretation. Those are distinct questions. The practical conclusion should therefore be calibrated: describe what was stable across the runs, where assignments varied, and whether that variation coincided with changes in the objective score.