Partition Space Maps for Community Detection: Visualizing Algorithmic Behaviour and Guiding Search

• The partition space P grows with the Bell number B_n and is combinatorial, discrete, and non-Euclidean, complicating its characterization through classical optimization.Source: §1 · p. 1
• Most methods seek a partition maximizing modularity Q, but typically provide little information about the broader solution space.Source: §1 · p. 1
• Near-optimal partitions, their distribution, and modularity degeneracy often remain unexplored when algorithms focus on a single solution.Source: §1 · pp. 1–2
• The modularity resolution limit and evidence for exponentially many near-degenerate high-modularity partitions motivate examining more than a single solution.Source: §1 · p. 2
• The paper combines Restricted Growth Sequence labels for exact, permutation-invariant partition identification with a (Γ, Q) map and deviation-matrix bounds as diagnostic tools, not a new detection method.Source: §1 · p. 2

2.1 Graphs, Communities, and Partitions

• A graph is represented with indexed vertices and a symmetric weight matrix, while a partition assigns every vertex to exactly one nonempty, disjoint community.The vertex indexing is a computational convention, not a structural assumption.Source: §2.1 · p. 2
• Communities have greater internal than external connectivity, and the seven-node benchmark has two communities and an ambiguous node.Its small size permits exhaustive enumeration of all partitions and exact modularity values.Source: §2.1 · pp. 2–3, Figure 1 · p. 3

2.2 Modularity

• Modularity Q is the normalized sum of deviation-matrix entries selected by the partition indicator matrix, representing within-community deviations from the null-model expectation.The deviation matrix records whether observed weights exceed or fall below the null-model expectation.Source: §2.2 · p. 3
• Sorting off-diagonal deviation-matrix entries in descending or ascending order gives tight upper and lower modularity envelopes that bound realizable partitions in the (Γ, Q) plane.Every partition includes the same diagonal contribution, while each included off-diagonal pair contributes twice its matrix entry.Source: §2.2 · pp. 3–5

2.3 Granularity

• Granularity Γ counts ones in the partition indicator matrix, equivalently the sum of squared community sizes; attainable values are discrete between n and n².Only sums of squares corresponding to integer compositions of n are attainable, so the gaps are intrinsic to the partition space.Source: §2.3 · p. 5
• The Partition Space Map projects feasible partitions onto (Γ, Q), with the all-singleton endpoint having negative Q and the all-in-one endpoint having Q = 0.The all-in-one endpoint is the only topology-invariant reference point in any PSM.Source: §2.3 · p. 5

2.4 Canonical labelling via Restricted Growth Sequences

• Restricted Growth Sequences give each partition a unique, permutation-invariant label, enabling direct identity checks and reducing comparison from O(n log n) to O(n).Figure 5 uses RGS ordering to display modularity values and clarify modularity plateaus.Source: §2.4 · p. 7, Figure 5 · p. 7

3.1 Exact Characterisation of a Minimal Benchmark

• Among 877 partitions, two structurally distinct partitions share the global maximum Q = 0.3672, while all partitions occupy only 13 distinct Γ values and 50 distinct Q values.The modularity envelopes mark the feasible region, whose limits arise from the deviation matrix.Source: §3.1 · p. 8

3.2 PSM as a tool to visualise algorithm behaviour

• Across nine resolution values, higher Louvain resolution shifts outputs toward smaller Γ, while lower values favour coarser structures with higher Γ.The planted ground truth lies centrally among these solutions, and some resolution values diverge from it in modularity and granularity.Source: §3.2 · p. 9
• Louvain and Infomap form compact clusters near ground truth, Label Propagation spans a wider Γ–Q region, and Walktrap occupies a narrow band.The map distinguishes algorithm outputs that may have similar Q but different structural organisation.Source: §3.2 · pp. 9–10, Figure 7 · p. 10
• The PSM can represent progressive aggregation or splitting as trajectories, with Louvain runs starting from the singleton partition at Γ = n.Aggregation increases Γ while modularity typically improves.Source: §3.2 · p. 11
• On the ring of cliques, Louvain runs converge to the same final partition; on the random graph, they end at distinct local optima with different granularities.The trajectories show stability on the clear-structure benchmark and multiple competing solutions on the graph without clear modular structure.Source: §3.2 · p. 11, Figure 8 · p. 11

3.3 How partition space varies with network density

• As density increases from a ring of cliques toward a complete graph, the feasible partition space systematically collapses and Louvain solutions move toward larger communities.Solutions begin at Γ = 500, corresponding to five communities; increasing density weakens structure and makes detection more difficult.Source: §3.3 · pp. 12–13, Figure 9 · p. 13

4 Area Between the Curves

• Normalizing granularity maps its attainable range to ˜Γ ∈ [0, 1], making the area measure dimensionless and comparable across network sizes.The normalized granularity coordinate is used when expressing the modularity bounds.Source: §4 · p. 14
• Small ABC indicates a narrow feasible region with modularity strongly constrained across granularity, whereas larger ABC indicates broader attainable modularity and more competing partitions.ABC is presented as a coarse measure of partition-space structural complexity.Source: §4 · p. 14
• ABC summarizes the size of the feasible PSM region as the area between the upper and lower modularity envelopes across the granularity range.The region can be estimated numerically from sampled partitions or empirical approximations of the bounding envelopes.Source: Figure 10 · p. 14, §4 · p. 14

Procedure

• The two-phase procedure runs a stochastic modularity optimizer repeatedly without constraints, then restarts it with locked groups to search the compatible residual region.Phase 1 explores broadly; phase 2 focuses on partitions consistent with the stable structure found in the best phase 1 solutions.Source: §5 · p. 15

Locking groups

• High co-occurrence among nodes in selected high-quality phase 1 runs identifies locked groups; nodes outside non-trivial groups remain free singletons.The example uses a threshold of τ = 0.8 to identify stable groups.Source: §5 · p. 15, Figure 11 · p. 16

Constrained search region

• The constrained search begins at Γlocked, the left boundary of the region available to phase 2.Locked groups force some node pairs to remain together, so the search cannot begin at the all-singleton value Γ = n.Source: §5 · pp. 15–16
• The outer constrained envelope allows locked groups to merge, while the inner envelope represents phase 2, where groups remain intact and free singletons may change assignment.These envelopes distinguish the residual space compatible with consensus from the smaller region actually explored.Source: §5 · pp. 16–17, Figure 12 · p. 17

Example: modularity improvement in the second phase

• Phase 2 improves the best modularity over phase 1, with typically small displacement in Γ but a non-negligible increase in Q.The comparison is made for the same retained seeds; one relatively weak phase 1 solution also receives one of the largest upward corrections.Source: §5 · pp. 17–18, Figure 13 · p. 18

Interpretation

• The procedure is a PSM-guided wrapper around existing heuristics, especially suited to networks with a stable community backbone and a small set of unresolved nodes.It uses repeated exploratory runs to estimate the relevant region, then concentrates the search there.Source: §5 · pp. 15, 18

Partition Space Map

• The PSM places algorithmic outputs in the (Γ, Q) plane, showing whether solutions differ toward finer or coarser granularity and higher or lower modularity.Repeated runs can expose sensitivity to initialization through their scatter in the map.Source: §6 · pp. 18–19

Modularity bounds

• Bounding curves derived from sorted deviation-matrix entries give the feasible region’s shape and size, including for networks without known ground truth.They provide an absolute reference for positioning candidate partitions.Source: §6 · p. 19

Limitation and complementarity

• Partitions with different structures but identical (Γ, Q) coordinates collapse to one point, leaving modularity plateaus invisible in the PSM.The RGS provides unique canonical labels for exact comparison and enumeration within such plateaus.Source: §6 · p. 19

Complementary tools

• The bounding curves frame the feasible region, the PSM shows solution distributions within it, and the RGS distinguishes partitions compressed by the map.Together, the tools support diagnostics, parameter selection, and characterization of solution spaces.Source: §6 · p. 19

Future directions

• Future work includes validating the framework on real-world networks and exploring quality functions or distance measures beyond the (Γ, Q) projection.The paper notes that other projections may reveal aspects of partition-space structure that this plane leaves hidden.Source: §6 · p. 19