Community structure of the pseudofractal web
Abstract
The Ramsey community number rκ 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. On a scale-free graph this question is confounded: a block model can split the network merely to absorb its degree distribution. I compute rκ 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 rκ=1095 nodes, with a log-evidence growing as (ln 3−2/3ln 2)n. Under a degree-corrected model tested against the configuration-model null, the same partition survives, breaking far earlier at rκ=42, with a log-evidence growing as (2ln 3−4/3ln 2)n -- exactly twice the plain slope, and independent of the prior. 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 maximised at of order √n communities of ∼√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.
Versions
Related
- When do token systems stabilize? Compatibility constraints and community structure
- First and second order firing statistics of large neuronal networks with community structure
- Dynamical analysis of a three-community model for malware transmission
- Discretization-free exact recovery in geometric community detection
- Community Detection using the Edge Laplacian Dynamics vis-a-vis Ricci Flow
BibTeX
@misc{vazquez2026community,
title = {{Community structure of the pseudofractal web}},
author = {Alexei Vazquez},
howpublished = {arXiv},
year = {2026},
month = jul,
doi = {10.48550/arxiv.2607.03010},
eprint = {2607.03010},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.03010},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Community structure of the pseudofractal web
AU - Alexei Vazquez
PY - 2026
DA - 2026/07/03
PB - arXiv
DO - 10.48550/arxiv.2607.03010
UR - https://arxiv.org/abs/2607.03010
AB - The Ramsey community number r_κ 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. On a scale-free graph this question is confounded: a block model can split the network merely to absorb its degree distribution. I compute r_κ 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 r_κ=1095 nodes, with a log-evidence growing as (ln 3−2/3ln 2)n. Under a degree-corrected model tested against the configuration-model null, the same partition survives, breaking far earlier at r_κ=42, with a log-evidence growing as (2ln 3−4/3ln 2)n -- exactly twice the plain slope, and independent of the prior. 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 maximised at of order √n communities of ∼√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.
ER -