Recognition: 2 theorem links
· Lean TheoremMotif enrichment as a driver of scale-free behavior in rewired random regular graphs
Pith reviewed 2026-05-12 02:21 UTC · model grok-4.3
The pith
Rewired random regular graphs develop a scale-free subnetwork with exponent near 2 above a critical triangle fugacity.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the mixed ensemble of random regular graphs with fixed N and k but variable triangles controlled by fugacity λ, a transition occurs at λ_cr estimated by entropy-energy comparison. Above λ_cr the graph becomes a two-phase system of dense clusters joined by a sparse scale-free sub-network with degree distribution P(d) ∼ d^{-γ} where γ ≈ 2, independent of N and k. The scale-free character stems from emergent preferential attachment induced by triangle motifs, derived via mean-field theory. Most inter-cluster triangles are isosceles, with the base inside a cluster and the apex in the connecting network.
What carries the argument
The emergent preferential attachment induced by triangle motifs in the triangle-rich phase of the rewired random regular graph ensemble.
If this is right
- The degree exponent γ stays close to 2 regardless of graph size or original degree.
- Inter-cluster connections are dominated by isosceles triangles with bases inside clusters.
- The scale-free sub-network remains sparse while clusters are dense.
- Possible links exist to Efimov states in conformally invariant potentials.
Where Pith is reading between the lines
- This motif-driven mechanism could apply to the emergence of scale-free topologies in real-world networks like the internet or protein interactions when triangle-like motifs are enriched.
- Future simulations could vary the rewiring process to test if other motifs produce different exponents.
- The mean-field derivation of γ ≈ 2 might be checked against exact enumerations for small graphs to quantify corrections.
Load-bearing premise
The mean-field treatment of the emergent preferential attachment from triangle motifs holds without large corrections from fluctuations or higher-order interactions.
What would settle it
Numerical simulations of large rewired graphs at λ > λ_cr that fail to show a degree distribution with exponent near 2 or lack a clear separation into dense clusters and sparse connectors would falsify the claim.
Figures
read the original abstract
We study the statistics of rewired random regular graphs (RRGs) in a mixed ensemble, where the average number of triangles is controlled by the fugacity $\lambda$, while the number of vertices and the vertex degree are fixed. This model exhibits a phase transition at critical fugacity $\lambda_{cr}$ from a triangle-poor phase (TPP), in which the number of triangles is independent of the system size, to a triangle-rich phase (TRP), in which the number of triangles scales linearly with the system size. We estimate $\lambda_{cr}$ by comparing the entropy of TPP with the energy of TRP. Above $\lambda_{cr}$, the RRG becomes a two-phase system in which dense clusters are connected by a sparse scale-free sub-network characterized by a degree distribution, $P(d) \sim d^{-\gamma}$, with $\gamma \approx 2$, independent of the size of the whole graph and its degree. We attribute this behavior to an "emergent preferential attachment" induced by triangle motifs, describe the mechanism underlying its formation, and derive the exponent $\gamma$ within a mean-field approach. We show that most inter-cluster triangles are isosceles, with the base lying inside one cluster and the apex belonging to the inter-cluster network. Finally, we speculate on a possible connection between these triangles and Efimov states in a conformally invariant potential.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies rewired random regular graphs (RRGs) in a mixed ensemble with fugacity λ controlling the average number of triangles while keeping N and vertex degree k fixed. It reports a phase transition at λ_cr (estimated by equating TPP entropy to TRP energy) separating a triangle-poor phase from a triangle-rich phase. Above λ_cr the graph separates into dense clusters linked by a sparse inter-cluster sub-network whose degree distribution follows P(d) ∼ d^{-γ} with γ ≈ 2 independent of N and k; this is attributed to emergent preferential attachment generated by triangle motifs and is derived via a mean-field rate equation. The manuscript further states that most inter-cluster triangles are isosceles (base inside a cluster, apex in the backbone) and speculates on a possible link to Efimov states.
Significance. If the mean-field derivation is robust and the claimed parameter independence of γ survives finite-size and higher-order corrections, the result would be significant for the statistical mechanics of constrained networks: it supplies a concrete, motif-driven mechanism that generates scale-free tails without an explicit global preferential-attachment rule. The phase-transition analysis and the geometric characterization of inter-cluster triangles add to the literature on clustered random graphs and could inform models of real networks that combine high clustering with heavy-tailed degrees.
major comments (4)
- [mean-field approach] § on mean-field derivation: the rate equation for emergent preferential attachment must be written explicitly (including the functional form of the attachment kernel) and shown to close at γ = 2 without corrections from overlapping triangles or multiple attachments per vertex; the skeptic concern that non-linear kernels could appear when several triangles share a vertex is load-bearing for the exact exponent claim.
- [numerical results] Results section / figures on degree distributions: numerical evidence that P(d) ∼ d^{-2} is independent of N and k must include finite-size scaling collapses and explicit checks that the effective cutoff does not scale with cluster size or system size; without these the thermodynamic-limit statement cannot be verified.
- [phase transition analysis] § on λ_cr estimation: the entropy of the TPP and the energy of the TRP must be given with explicit formulas and error estimates; the comparison method is presented as independent of fitting, yet its accuracy directly controls the location of the two-phase regime where the scale-free backbone appears.
- [two-phase structure] § defining the inter-cluster sub-network: a precise algorithmic or topological definition of which edges belong to the sparse backbone versus the dense clusters is required, together with a demonstration that this partition remains well-defined and sparse in the N → ∞ limit.
minor comments (3)
- [abstract] Abstract: the phrase 'independent of the size of the whole graph and its degree' is slightly ambiguous; replace 'its degree' with 'its regular degree k' for clarity.
- [throughout] Notation: ensure P(d) is used consistently for the degree distribution of the backbone and that the same symbol is not reused for the full-graph degree distribution.
- [conclusion] The Efimov-state speculation is intriguing but should be moved to a dedicated discussion paragraph with at least one relevant reference; as written it appears only in the abstract and conclusion.
Simulated Author's Rebuttal
We thank the referee for their thorough review and valuable feedback on our manuscript. We have carefully considered each comment and will revise the paper accordingly to address the concerns raised. Our point-by-point responses are as follows.
read point-by-point responses
-
Referee: [mean-field approach] § on mean-field derivation: the rate equation for emergent preferential attachment must be written explicitly (including the functional form of the attachment kernel) and shown to close at γ = 2 without corrections from overlapping triangles or multiple attachments per vertex; the skeptic concern that non-linear kernels could appear when several triangles share a vertex is load-bearing for the exact exponent claim.
Authors: We agree that an explicit presentation of the rate equation is necessary for clarity. In the revised manuscript, we will write out the mean-field rate equation for the probability P(d) of a vertex having degree d in the backbone, with the attachment kernel explicitly given as proportional to d (arising from the number of ways to attach via a triangle motif). We demonstrate that this linear kernel leads to the stationary solution with γ = 2, and argue that in the large-N limit, the probability of overlapping triangles sharing a vertex in a way that would nonlinearize the kernel is suppressed by the fugacity control and the separation of scales between clusters and backbone. While we cannot rule out all higher-order corrections without a more advanced analysis, the mean-field closure at γ=2 is robust within the approximations stated in the paper, and we will add a discussion of this point. revision: yes
-
Referee: [numerical results] Results section / figures on degree distributions: numerical evidence that P(d) ∼ d^{-2} is independent of N and k must include finite-size scaling collapses and explicit checks that the effective cutoff does not scale with cluster size or system size; without these the thermodynamic-limit statement cannot be verified.
Authors: We will incorporate finite-size scaling analysis in the revised version. Specifically, we will present data collapses for P(d) d^2 as a function of d / N^β for appropriate β, across multiple system sizes N, to confirm the scaling form and independence from N. We will also examine the cutoff behavior and show that it scales consistently with the backbone size rather than cluster size, and provide comparisons for different fixed degrees k to support the claimed independence. revision: yes
-
Referee: [phase transition analysis] § on λ_cr estimation: the entropy of the TPP and the energy of the TRP must be given with explicit formulas and error estimates; the comparison method is presented as independent of fitting, yet its accuracy directly controls the location of the two-phase regime where the scale-free backbone appears.
Authors: In the revision, we will include the explicit expressions for the entropy of the triangle-poor phase (TPP) and the energy of the triangle-rich phase (TRP) used in estimating λ_cr. We will also provide error estimates based on the statistical sampling in our calculations and clarify the method of equating them, including any assumptions made. This will make the estimation procedure fully transparent and allow readers to assess its accuracy. revision: yes
-
Referee: [two-phase structure] § defining the inter-cluster sub-network: a precise algorithmic or topological definition of which edges belong to the sparse backbone versus the dense clusters is required, together with a demonstration that this partition remains well-defined and sparse in the N → ∞ limit.
Authors: We will add a precise definition in the revised manuscript: the dense clusters are identified as the connected components in the subgraph induced by edges that participate in at least one triangle, and the inter-cluster sub-network (backbone) consists of the remaining edges that connect these components. We will demonstrate through extensive simulations for increasing N that the number of backbone edges scales sublinearly with N, remaining sparse, and that the partition is stable with the fraction of inter-cluster edges approaching a constant less than 1. While a rigorous proof of the limit behavior is challenging, the numerical evidence strongly supports the two-phase structure persisting in the thermodynamic limit. revision: partial
Circularity Check
No significant circularity; mean-field derivation of γ and λ_cr estimate are independent of target observables
full rationale
The paper defines the mixed ensemble via fixed N, k and fugacity λ controlling triangle number. It estimates λ_cr by equating entropy of the triangle-poor phase to energy of the triangle-rich phase, an independent thermodynamic comparison. Above λ_cr it identifies dense clusters linked by an inter-cluster subnetwork and attributes the observed P(d)∼d^{-γ} to emergent preferential attachment from isosceles triangles; the exponent γ≈2 is then obtained from a separate mean-field rate equation for attachment probabilities. No equation reduces the output distribution to a fitted parameter by construction, no self-citation is load-bearing for the central claim, and the derivation begins from the model Hamiltonian and standard mean-field closure without importing the target exponent or phase boundary as an input. The result is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
free parameters (1)
- λ_cr
axioms (1)
- domain assumption Mean-field theory suffices to derive the degree exponent from emergent preferential attachment induced by triangles
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We attribute this behavior to an 'emergent preferential attachment' induced by triangle motifs... derive the exponent γ within a mean-field approach... P(K)∝(K+A)^{-2} This yields the scale-free exponent γ=2.
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
the rate equation becomes: dKj/dτ = (Kj + A)/τ ... Solving yields Kj(τ) + A ∝ τ/τsat ... P(K)∝(K+A)^{-2}
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
among triads of different types. In addition, we show that the critical behavior of the rewired RRG ensemble is sensitive to the number of triangles in the initial state. In particular, initial configurations with a large number of triangles undergo the transition between the two phases at a lower value ofλthan initial configurations with a small number o...
-
[2]
Graphs in this phase have no apparent clusters and are visually indistinguishable from typical RRG
In TPP (λis small), the number of triangles slowly increases with the fugacity, fully consistent with the mean-field estimates based on the law of mass actions for elemen- tary chemical reactions [14] which is adapted to RRGs in Section IIIA. Graphs in this phase have no apparent clusters and are visually indistinguishable from typical RRG. The Ollivier-R...
-
[3]
In TRP, (λis large), the number of triangles fluctuates near the maximal value inde- pendent ofλ. Graphs in this phase are loosely connected clusters with a positive ORC as shown in Fig. 1b, while the inter-cluster connected subgraph has a negative ORC. The number of clusters in this phase is aboutN/d. Fig. 2d shows that the normalized number of triangles...
-
[4]
Possible triad types in undirected graphs
[2] [3][0] Figure 4. Possible triad types in undirected graphs. Changes in the number of triad of different types follows chemical reaction
-
[5]
Thus, the number of triangles, introduced earlier, is△= N 3 c3
+ 3[2]↔[3] + 3[1].(4) We denote the concentrations of these triads in the graph byc0, ..., c3, understood as a number of triads of a corresponding type normalized by N 3 . Thus, the number of triangles, introduced earlier, is△= N 3 c3. Edge rewiring under vertex degree conservation suggests the existence of the following invariants (valid regardless of th...
-
[6]
0.00 0.05 0.10 0.15 0.20 λ/log N 0.00 0.05 0.10 0.15 0.20 △ /△ max degree 30 50 100 Figure 5
are depleted, this chemical-reaction-based estimation ceases to valid and the transition happens. 0.00 0.05 0.10 0.15 0.20 λ/log N 0.00 0.05 0.10 0.15 0.20 △ /△ max degree 30 50 100 Figure 5. Normalized number of triangles in TPP atN= 1000andd= 30,50,100. The solid lines are taken from the leading order term of Eq.(11). 9 B. Criticality of the backward re...
-
[7]
Free energy of this phaseFT RP depends solely on the number of triangles
In TRP the disconnected clique is the unique state with the maximum number of triangles and, hence, with the maximal energy. Free energy of this phaseFT RP depends solely on the number of triangles. Thus, FT RP kBT =−λ△ max =−λ d(d−1)N 6 (12)
-
[8]
emergentpreferentialattachment
In TPP we can estimate the free energy of the graph using the statistic of typical RRGs. AtN≫1the number of available configurations,N BC(N, d), can be approximated by the Bender-Canfield formula [21] valid forλ= 0: NBC(N, d)≈ √ 2e −(d2−1)/4 (dN) d/2 ed/2d! N .(13) The number of triangles in TPP is approximately△T P P ≡ d N 3 eλ, as follows from (11). How...
work page 2000
-
[9]
Scale-free graphs from hyperbolic embedding Let us remind the main steps of embedding scale-free graphs into the hyperbolic manifold suggested in the pioneering works [29–31]. Instead of the Poincare disc, we consider the Poincare upper half-planeH 2{(x, y) :y >0}of the constant negative curvature−1with the metricsds 2 defined in the standard wayds2 = 1 y...
-
[10]
Hyperbolic embedding and isosceles triangles Let us inscribe the model of scale-free graph formation due to enrichment of triangles into the generic scheme of hyperbolic embedding. A particularly striking feature of the resulting inter-cluster topology is the prevalence of "isosceles" triangles – triads where two vertices stay within a cluster and the thi...
-
[11]
Epidemic spreading in scale-free net- works.Physical Review Letters, 86(14):3200–3203, 2001
Romualdo Pastor-Satorras and Alessandro Vespignani. Epidemic spreading in scale-free net- works.Physical Review Letters, 86(14):3200–3203, 2001
work page 2001
-
[12]
M. E. J. Newman. Power laws, pareto distributions and zipf’s law.Contemporary Physics, 46:323–351, 2005
work page 2005
-
[13]
D. S. Lee. Synchronization transition in scale-free networks: Clusters of synchrony.Physical Review E, 72(2):026208, 2005. 18
work page 2005
-
[14]
Chaoming Song, Shlomo Havlin, and Hernán A. Makse. Self-similarity of complex networks. Nature, 433(7024):392–395, 2005
work page 2005
-
[15]
X. S. Chen, Y. M. Ding, J. Meng, J. F. Fan, and F. F. Ye. Statistical properties of random clique networks.Frontiers of Physics, 12(5):128909, 2017
work page 2017
-
[16]
S. Bialonski and K. Lehnertz. Unraveling spurious properties of interaction networks with tailored random networks.PLoS ONE, 6(8):e22826, 2011
work page 2011
-
[17]
On a general class of models for interaction.SIAM Review, 28(4):513–527, 1986
David Strauss. On a general class of models for interaction.SIAM Review, 28(4):513–527, 1986
work page 1986
- [18]
-
[19]
Juyong Park and M. E. J. Newman. Solution for the properties of a clustered network.Phys. Rev. E, 72:026136, Aug 2005
work page 2005
-
[20]
David Foster, Jacob Foster, Maya Paczuski, and Peter Grassberger. Communities, clustering phase transitions, and hysteresis: Pitfalls in constructing network ensembles.Phys. Rev. E, 81:046115, Apr 2010
work page 2010
-
[21]
V. Avetisov, M. Hovhannisyan, A. Gorsky, S. Nechaev, M. Tamm, and O. Valba. Eigenvalue tunneling and decay of quenched random network.Phys. Rev. E, 94:062313, Dec 2016
work page 2016
- [22]
-
[23]
V. Avetisov, A. Gorsky, S. Nechaev, and O. Valba. Many-body localization and new critical phenomena in regular random graphs and constrained erdős-renyi networks, 2016
work page 2016
-
[24]
M. V. Tamm, A. B. Shkarin, V. A. Avetisov, O. V. Valba, and S. K. Nechaev. Islands of stability in motif distributions of random networks.Phys. Rev. Lett., 113:095701, Aug 2014
work page 2014
-
[25]
Oxford University Press, 07 2018
Mark Newman.Networks. Oxford University Press, 07 2018
work page 2018
-
[26]
Yann Ollivier. Ricci curvature of markov chains on metric spaces.Journal of Functional Analysis, 256(3):810–864, 2009
work page 2009
-
[27]
Ricci curvature of graphs.Tohoku Mathematical Journal, 63(4):605–627, 2011
Yong Lin, Linyuan Lu, and Shing-Tung Yau. Ricci curvature of graphs.Tohoku Mathematical Journal, 63(4):605–627, 2011. Adapts Ollivier’s Wasserstein-based curvature to graph theory
work page 2011
-
[28]
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442, 1998
work page 1998
-
[29]
Community detection on networks with ricci flow.Scientific Reports, 9(1), 2019
Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow.Scientific Reports, 9(1), 2019
work page 2019
-
[30]
Pawat Akara-pipattana, Thiparat Chotibut, and Oleg Evnin. The birth of geometry in expo- nential random graphs.Journal of Physics A: Mathematical and Theoretical, 54(42):425001, 2021
work page 2021
-
[31]
Edward A Bender and E.Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences.Journal of Combinatorial Theory, Series A, 24(3):296–307, 1978
work page 1978
-
[32]
E.R.ColmanandG.J.Rodgers. Complexscale-freenetworkswithtunablepower-lawexponent and clustering.Physica A: Statistical Mechanics and its Applications, 392(21):5501–5510, 2013
work page 2013
-
[33]
Growing optimal scale-free networks via likelihood.Physical Review E, 91(4):042801, 2015
Michael Small, Yingying Li, Thomas Stemler, and Kevin Judd. Growing optimal scale-free networks via likelihood.Physical Review E, 91(4):042801, 2015
work page 2015
-
[34]
G. U. Yule. A mathematical theory of evolution.Philosophical Transactions of the Royal Society B, 213:21–87, 1925
work page 1925
-
[35]
H. A. Simon. On a class of skew distribution functions.Biometrika, 42:425–440, 1955
work page 1955
-
[36]
E. Ben-Naim and P. L. Krapivsky. Kinetic theory of random graphs: From paths to cycles. Physical Review E, 71(2):026129, 2005. 19
work page 2005
-
[37]
P. L. Krapivsky, S. Redner, and F. Leyvraz. Connectivity of growing random networks.Phys. Rev. Lett., 85:4629, 2000
work page 2000
-
[38]
P. L. Krapivsky and S. Redner. Organization of growing random networks.Phys. Rev. E, 63:066123, 2001
work page 2001
-
[39]
Curvature and temperature of complex networks.Physical Review E, 80(3):035101(R), 2009
Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Curvature and temperature of complex networks.Physical Review E, 80(3):035101(R), 2009
work page 2009
-
[40]
Hyperbolic geometry of complex networks.Physical Review E, 82(3):036106, 2010
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks.Physical Review E, 82(3):036106, 2010
work page 2010
-
[41]
Sustaining the internet with hyperbolic mapping.Nature Communications, 1(1):62, 2010
Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping.Nature Communications, 1(1):62, 2010
work page 2010
-
[42]
Omrie Ovdat and Eric Akkermans. The breaking of continuous scale invariance to discrete scale invariance: a universal quantum phase transition. In Uta Freiberg, Ben Hambly, Michael Hinz, and Steffen Winter, editors,Fractal Geometry and Stochastics VI, volume 76 ofProgress in Probability, pages 209–238. Birkhäuser Cham, 2021
work page 2021
-
[43]
Quantum phase transitions in holographic models of magnetism and superconductors.Phys
Nabil Iqbal, Hong Liu, Márk Mezei, and Qimiao Si. Quantum phase transitions in holographic models of magnetism and superconductors.Phys. Rev. D, 82(045002):045002, 2010
work page 2010
-
[44]
Ren Zhang, Chenwei Lv, Yangqian Yan, and Qi Zhou. Efimov-like states and quantum fun- neling effects on synthetic hyperbolic surfaces.Science Bulletin, 66(19):1967–1972, 2021
work page 1967
-
[45]
Ricci curvature of the internet topology
Chien-Chun Ni, Yu-Yao Lin, Jie Gao, Xianfeng David Gu, and Emil Saucan. Ricci curvature of the internet topology. In2015 IEEE Conference on Computer Communications (INFOCOM), pages 2758–2766, 2015
work page 2015
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.