Most community detection on large, noisy graphs runs one optimizer, usually Louvain or Leiden, over every node at once. Louvain and Leiden are greedy methods that move nodes between groups to raise modularity, a score for how much denser the links inside groups are than chance would predict. On graphs built from noisy measurements, such as nearest-neighbor graphs of single cells, a large fraction of nodes sit at the fuzzy edges of groups. These edge nodes link several groups at once. They can lead the optimizer to merge two small or sparse groups, or to split a group along arbitrary lines. This proposal takes the opposite approach. First, find the nodes that are clearly central within their own group, even when that group is sparse. Cluster only those nodes. Then attach every remaining node to the groups the core has already fixed, in a single deterministic pass ordered by centrality. The core nodes can no longer change labels, so the noisy periphery cannot merge or reshape groups.
The ingredient that makes this possible is recent. Balanced Ranking with Relative Centrality showed that PageRank, degree and Katz scores fall into a "density trap": their top-ranked nodes come almost entirely from the densest community, so sparse communities vanish from the top of the ranking. The paper's fix is relative centrality, which scores each node against its higher-ranked neighbors instead of against the whole graph. Running Louvain on the top 20% of nodes ranked this way gave purity similar to or better than full-graph clustering, with all cell types still represented. The paper leaves the other 80% of nodes unassigned and says explicitly that it does not know how to map them back without reintroducing noise. This proposal fills that gap and makes the resulting pipeline work on graphs far larger than the 54,000-node datasets that paper tested.
Core Claim
The claim is specific and can be falsified. Fix the core with relative centrality, cluster it with Leiden, then assign the periphery by label propagation in which core labels cannot change. On noisy graphs whose communities differ in density, this pipeline should recover full-graph partitions that match ground truth better than Leiden run on the whole graph. The gain should come mostly from recovering small and sparse communities that whole-graph optimization merges away. The gain should also grow with two things: how unequal the community densities are, and how many edges cross between communities. On clean graphs with few cross-community edges the gain should disappear. If we see no gain on noisy, density-imbalanced graphs, or if a plain degree-ranked core does just as well, the claim fails.
The scalability argument follows from the structure of the pipeline. Relative centrality in its one-hop form (N-Rank) uses only a base score and the node's neighbors, so it costs time linear in the number of edges. Leiden then runs on a fraction $\alpha$ of the nodes. The periphery pass touches each edge a constant number of times. Because the core labels are fixed, the core also serves as a stable index. Nodes that arrive later can be assigned by the same propagation rule without re-clustering. That gives a natural incremental mode for growing graphs.
Research Program
The method has three stages. Stage one computes relative centrality on the whole graph and keeps the top $\alpha$ fraction as the core. We use N-Rank as the default and multi-hop M-Rank as a variant.
Stage two runs Leiden on the subgraph induced by the core nodes. If that subgraph breaks into many small pieces, we add back edges along short paths through the periphery, with weights proportional to path strength.
Stage three handles the periphery. It visits non-core nodes in descending order of relative centrality. Each node takes the label with the largest weighted vote among its neighbors that already have labels. Ties go to the label of the highest-ranked neighbor. Nodes with no labeled neighbor are deferred to a later sweep. A small number of refinement sweeps then let periphery nodes, and only periphery nodes, change labels.
Each node also gets a vote margin, meaning the gap between its winning and runner-up labels. A small margin marks the node as an uncertain assignment. This is useful in its own right on biological data, where some cells genuinely sit between types.
The periphery stage deliberately reuses the deterministic, importance-ordered propagation of LPA-MNI. That method ranks nodes by degree, breaks label conflicts toward the most central neighbor, and runs in $O(m + n\log n)$ time, where $m$ is the number of edges and $n$ the number of nodes. We differ from it in two ways. We replace degree with relative centrality, which addresses LPA-MNI's own stated limitation that it relies only on degree. And we freeze a clustered core, whereas LPA-MNI uses a modularity-based initialization that every node may later overwrite.
Two analyses accompany the method. The first chooses $\alpha$ automatically, which is the hyperparameter-automation gap that Mukherjee et al. leave open. We sweep $\alpha$ and pick the smallest value at which the core partition stops changing, measured by the agreement between partitions at neighboring $\alpha$ values.
The second is a small theoretical argument in a planted model. In the multi-core-periphery block model of Mukherjee et al., a periphery node attached by majority vote over core neighbors is misassigned with probability that falls exponentially in the number of its core neighbors. This follows from a standard concentration bound on the vote. The argument tells us which graphs should make the method fail: those whose periphery nodes have few core neighbors. We will check that prediction directly.
Baselines
The naive reference point is Leiden on the full graph at its default resolution. Practitioners use it for exactly this task, and Zhang et al. treat Louvain and Leiden as the standard partitioners for single-cell graphs. The strongest version of this baseline is Leiden with a tuned resolution parameter. The resolution parameter controls how large communities tend to be, and lowering the scale is the standard remedy for small communities being merged away. To keep the comparison fair, the resolution is tuned on the same held-out graphs with the same number of trials as our $\alpha$ sweep, and all methods run on identical nearest-neighbor graphs with identical seeds and hardware. Our method beats this baseline if it achieves higher adjusted Rand index, a chance-corrected measure of agreement between two partitions, and higher recall on the smallest quartile of ground-truth communities. This must hold across the single-cell datasets and must not depend on a single dataset. We found no reported purity or adjusted-Rand figure on Lacuna for full-graph Leiden on these single-cell datasets, so we will produce the baseline numbers ourselves.
The strongest existing method that touches the periphery problem is LPA-MNI, which we run with its modularity initialization and degree ordering. The paper reports NMI = 1.0 and AMI = 1.0 on Zachary's Karate Club. That graph has 34 nodes and is too small to be informative here, so the comparison that matters is on the larger graphs.
We also run the partial pipeline of Mukherjee et al., which is relative centrality followed by Louvain on the top 20%. It is scored on the core only and also with naive nearest-centroid assignment of the remaining nodes. That paper reports purity only qualitatively ("similar or better" than traditional methods), so no numeric target exists on Lacuna for it either.
The key ablation keeps the whole pipeline fixed and swaps the core selector. The alternatives are degree, PageRank, and $k$-core membership, where a $k$-core is the largest subgraph in which every node has at least $k$ neighbors; Tixier et al. used $k$-cores to isolate cohesive centers in text graphs. This ablation shows whether density balancing in the core is the source of the gain, or whether any core-then-assign scheme would work.
Why not just…?
Why not just tune Leiden's resolution parameter? This is the most serious threat. A lower resolution scale can recover small communities without any core selection. A single resolution value, however, applies one community size to the whole graph, while density imbalance means different communities need different scales. The fixed core sidesteps that because it never asks one parameter to fit every community. If tuned-resolution Leiden matches us on small-community recall in the density-imbalanced synthetic sweep, the central claim is wrong and we will say so. We expect our advantage to appear specifically as density imbalance grows while total community count stays fixed.
Why not just run Leiden first and then take the top-ranked nodes by degree within each community? Taking a fixed share per community also removes the density trap, and it needs no new ranking. Its weakness is that it inherits the first partition. If the noisy whole-graph run has already merged two sparse groups, taking a share from the merged group cannot split them. This baseline runs inside the ablation suite. The settling experiment is the high-noise regime, where we will count how many ground-truth communities each method recovers at all.
Why not use a community-aware centrality such as map equation centrality to pick the core? Map equation centrality scores each node by how many bits it saves in the description of a random walk over the network's communities. It finds bridge nodes well, but it requires a finished Infomap partition first, so using it to choose the core would be circular. Its preference for bridges is also the opposite of what a core should contain. We include it as an extra core selector and expect it to do poorly, which would itself be informative.
Why not just use plain label propagation, which is already linear time? Plain label propagation breaks ties at random, so the same input can produce very different partitions across runs, as LPA-MNI documents. We will report run-to-run variability across 20 seeds for every method. Ours should be deterministic given the graph.
Proposed Experiments
The primary testbed is the 11 single-cell RNA-seq graphs used by Mukherjee et al., which range from 1,400 to 54,000 cells and include Baron Human and Mouse and a T-cell cancer dataset. Annotated cell types serve as ground truth. On the T-cell data, PageRank was reported to miss several communities entirely, which makes it the sharpest test of sparse-community recovery. Metrics are adjusted Rand index, NMI (normalized mutual information, another partition-agreement score), recall on the smallest-quartile communities, and the number of ground-truth communities recovered with matched F1 above 0.5. We also check the calibration of the vote margin by asking whether low-margin cells are more often misassigned.
The decisive mechanistic experiment uses synthetic data. We take LFR benchmark graphs, which have planted communities, and multi-core-periphery block-model graphs. We vary two factors independently: the density ratio between communities and the fraction of edges that cross communities. The prediction is that our gain over tuned Leiden is near zero when crossing edges are rare and grows along both axes. If gains appear even with very few crossing edges, they come from something other than the hypothesized mechanism, and we will investigate before claiming anything.
For scale, we generate LFR graphs from $10^5$ up to $10^7$ nodes and report wall-clock time and peak memory for each stage against full-graph Leiden. Mukherjee et al. report under 10 seconds for relative centrality at about 50,000 nodes, which gives a reference point for stage one. We also run on LiveJournal1 and amazon0312, two graphs used by FENNEL. Neither has ground-truth communities in our material, so there we report modularity and conductance (the fraction of a community's edge weight that leaves it). We present these as checks that the method runs at scale, not as evidence that it is more accurate.
For growing graphs, we use the snapshot benchmarks DBLP and AS-733 from Adapting to Evolving Graphs. New nodes are assigned through the frozen core, and the core is re-clustered only when the share of low-margin new nodes exceeds a threshold. We compare against full re-clustering at every snapshot, measuring agreement with the from-scratch partition and the speedup. That paper reports 10–20× speedups while keeping 98–99% of downstream classifier accuracy for its coarsening scheme, which is a different task. We use those figures only as a reference scale and do not claim a head-to-head comparison.
References
- Balanced Ranking with Relative Centrality: A multi-core periphery perspective
- LPA-MNI: An Improved Label Propagation Algorithm Based on Modularity and Node Importance for Community Detection
- Review of single-cell RNA-seq data clustering for cell-type identification and characterization
- GoWvis: A Web Application for Graph-of-Words-based Text Visualization and Summarization
- Map equation centrality: community-aware centrality based on the map equation
- FENNEL: streaming graph partitioning for massive scale graphs
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening