Overview

PRISM (Pareto Resolution-Invariant Swarm for Modularity) is the discrete multi-objective PSO backend in pymocd. Given a graph G = (V, E), PRISM explores a population (swarm) of candidate partitions and evolves them through velocity-driven relabelling, yielding a Pareto front of resolution-diverse community structures in one run.

Why PSO for community detection? link

Classical swarm intelligence works in continuous space, but partitions are nominal: there is no meaningful “distance” between community labels. PRISM adapts PSO to the discrete setting by reinterpreting the per-node velocity as the probability of relabelling that node this generation. The discrete move itself is a neighbour-majority vote biased toward the personal-best and leader partitions, so topology is never violated (PRISM never injects a label absent from a node’s neighbourhood).

Multi-resolution Pareto objective link

PRISM’s default objective is the multi-resolution weighted modularity

  Q_γ(P) = Σ_c [ L_c / m_w  −  γ · (vol_c / 2·m_w)² ]
  

evaluated at three resolutions, γ ∈ {0.5, 1.0, 2.0}, all minimized as [-Q_0.5, -Q_1.0, -Q_2.0]. The three γ values correspond to fine, standard, and coarse partition granularities: the Pareto front therefore sweeps across resolutions in a single run. Choosing γ ≠ 1 classical modularity lets PRISM escape the well-known resolution limit of Q.

Edge weights are derived automatically from topology (TOM/Jaccard reweighting): intra-community edges with many shared triangles receive higher weight, noise edges crossing communities receive near-zero weight. This keeps the objective informative even at high mixing μ, where raw edge counts become uninformative.

Algorithm layers link

Stacked on the discrete-PSO base:

1. LPA-seeded swarm — most particles start from a Label Propagation seed with increasing perturbation; the remainder are uniform random. A collapse guard reverts to 100% random if LPA yields a degenerate (single-community) seed.
2. EM-momentum velocity + adaptive Clerc–Kennedy constriction — per-node velocities are smoothed by an exponentially-weighted momentum; the constriction coefficient χ ramps with generation (more exploration early, more exploitation late) and tightens if the archive collapses.
3. Neighbour-majority relabel with swarm bias — each node is relabelled to the argmax of neighbour-label frequencies, with a small additive bias toward the pbest and archive-leader labels only when those labels are already present in the neighbourhood.
4. External non-dominated archive with crowding distance — cached at capacity; leader for each particle is a binary-tournament pick favouring higher crowding distance.
5. Memetic Louvain refinement — every few generations, the top Pareto particles get a short Louvain-style ΔQ climb; a final polish runs on the best member returned by .run().

Solution representation link

Each particle holds a dense partition (a Vec<CommunityId> indexed by node), a per-node velocity vector, an EM-momentum vector, and its personal-best partition. Internally the graph is stored as a CSR-packed dense adjacency plus an AoS edge list, and each particle owns a per-run scratch buffer so the hot paths never touch a hash map.

When to choose PRISM link

• You want a single run to span multiple resolutions of community structure.
• The graph has high mixing (μ ≥ 0.4 in LFR terms) where single-scale modularity struggles.
• You want Pareto-style exploration with a modularity-family objective (not intra/inter density as in HP-MOCD).

For a head-to-head API reference against HP-MOCD, see HP-MOCD.