The ring wants to be broken

The Ramsey community number $r_\kappa$ is the minimum network size at which a graph's connectivity is better described by a partition into communities than by no partition, under a prescribed community-detection rule.

It was introduced through numerical simulations of networks grown by local rules, which suggested that community structure can emerge without any node heterogeneity.

Here I compute $r_\kappa$ analytically for the simplest homogeneous, locally wired graph: the circulant ring lattice $C_n(1,\dots,c)$.

Using a Bernoulli stochastic block model with symmetric $\mathrm{Beta}$ priors as the detection rule, the Bayesian evidence for a balanced two-community partition and for the unpartitioned network are both obtained in closed form, so the transition between them can be located exactly.

The result is a sharp dependence on the interaction range: the plain cycle ($c=1$) is never partitioned, its two-community posterior decaying as $n^{-(2\alpha+3)}$, so $r_\kappa=\infty$; but the next-nearest-neighbour ring ($c=2$) acquires a finite $r_\kappa\simeq 35$ nodes, above which the partition is preferred with a log-evidence growing as $(\ln 2)\,n$.

This provides an exactly solvable instance of community emergence in a network with no built-in communities, and shows that a minimal amount of local connectivity is enough to break the ring.