Community structure of the pseudofractal web

Abstract

The Ramsey community number $ r_{\kappa} $ is the smallest network size at which a graph is better described by a partition into communities than by no partition, under a prescribed detection rule and at certainty $ q $. On a scale-free graph this question is confounded: a block model can split a network on its degree distribution alone, separating hubs from leaves that are no community at all. I compute $ r_{\kappa} $  analytically for the deterministic pseudofractal scale-free web of Dorogovtsev, Goltsev, and Mendes, separating genuine community structure from degree heterogeneity with two closed-form detection rules. Under a plain Bernoulli stochastic block model, the web’s natural recursive bipartition is unpreferred while small and breaks at $ \boldsymbol{r_{\kappa} = 1095} $ nodes, with a log-evidence growing as $ \boldsymbol{(\ln 3-\tfrac{2}{3}\ln 2)n} $. Under a degree-corrected model tested against the configuration-model null, the same partition survives, breaking far earlier at $ \boldsymbol{r_{\kappa} = 123} $, with a log-evidence growing as $ \boldsymbol{(2\ln 3-\tfrac{4}{3}\ln 2)n} $—exactly twice the plain slope, and independent of the prior. Both figures are quoted at the default certainty $ \boldsymbol{q = 0.99} $; the transitions are sharp and the web exists only at discrete sizes, so of the values tabulated only $ \boldsymbol{q=\tfrac{1}{2}} $ changes an answer, lowering the degree-corrected one to 42. Degree correction reverses the ordering of the candidate cuts, demoting the hub–leaf split and elevating the recursive one. Because the web is self-similar, the best description is not two communities but a nested hierarchy: the degree-corrected evidence keeps rising as the partition is refined, and is maximized at of order $ \sqrt{n} $ communities of $ \boldsymbol{\sim\sqrt{n}} $ nodes. A purely local recursive rule thus builds true hierarchical community structure, over and above the scale-free degree sequence it also produces, in an exactly solvable setting. The appendices give every derivation.