Tools reveal structure of community detection solutions in networks
Partition Space Maps for Community Detection: Visualizing Algorithmic Behaviour and Guiding Search
Social and Information Networks
Summary
Finding groups in networks is hard because there are many ways to split a network into communities. The authors introduce tools to label and map all possible ways to divide a network, making it easier to see how community detection methods behave. They show these tools on small networks to reveal patterns and limitations in these divisions. This helps evaluate and guide algorithms that find communities in larger networks.
What this means in practice
- •For network analysts: Use the partition space map to better understand the range of possible community structures and improve interpretation of detected communities.
- •For algorithm developers: Guide the design and evaluation of community detection algorithms by providing an exact overview of partition space and algorithmic behaviour.
- •For social network platform engineers: Enhance community detection features by applying geometry-aware exploration tools to optimize network segmentation.$Commercial implications: Supports improved community detection software with better segmentation insights, valuable for social network platforms offering targeted content or advertising.
Authors
Fabio Morea
Abstract
Community-detection methods search over possible partitions of a network, but the structure of this partition space is rarely examined directly. This paper introduces two complementary tools that make~$\mathcal{P}$ analytically and visually accessible. First, a canonical labelling scheme based on the Restricted Growth Sequence~(RGS) is adopted, assigning each partition a unique, permutation-invariant identifier and eliminating the need for pairwise similarity measures such as the Normalized Mutual Information. Second, granularity~$Γ$ is defined and combined with modularity~$Q$ to produce a two-dimensional projection: the Partition Space Map~(PSM). Within the $(Γ,Q)$ plane, only a discrete set of integer values of~$Γ$ is attainable, and upper and lower bounds on~$Q$ are derived directly from the deviation matrix. These tools are demonstrated through complete enumeration of~$\mathcal{P}$ for small benchmark graphs, revealing the fine structure of modularity degeneracy and the combinatorial constraints that shape the feasible region. The framework provides an exact, assumption-free reference for evaluating heuristic community detection algorithms and lays the groundwork for geometry-aware exploration of partition space in larger networks.