拉姆齐社群数作为一种重整化群交叉现象

《Physica A: Statistical Mechanics and its Applications》：The Ramsey community number as a renormalization-group crossing

　　●网络必须达到一定的最小规模，其社区结构才能被检测到。●在自相似格子上，这个规模是可以精确计算得出的，而不是从曲线上读取的。●每次增长都会使得社区之间的边界变薄，因此检测效果会提高。●对于K个社区，每条边的证据量会稳定在ln K。无论使用哪种格子，情况都是如此。●最佳的分区是一个既增长又稳定的热力学相。

引言
网络需要增长到多大规模，其社区结构才能成为客观存在的事实？社区——即节点之间相互连接的密度高于与网络其他部分的节点——是网络中研究最多的介观组织形式[1]、[2]。困难在于，任何足够灵活的算法都可以在一个无结构的图中划分出社区，因此算法返回的分区并不能证明网络确实存在这样的社区。标准的解决办法是贝叶斯模型比较[3]、[4]、[5]。将两个模型应用于同一个网络。第一个是随机块模型：节点被分成不同的块，边的存在概率仅取决于其端点所属的块，因此该模型可以表达“这些群体存在”这一观点。第二个是空模型，其中所有节点在统计上都是等价的，因此它完全无法表达这一观点。一旦参数被积分出来，每个模型都会为观察到的网络分配一个概率；这两个概率的比值?=???(network∣block model)???(network∣null model)表示用群体结构描述网络比不用群体结构要好多少。在整个过程中，我们将块模型假设称为“分割”。在没有优先选择任何模型的情况下，分割的后验概率为???(split)=?1+?，并且在预设的置信度??（例如??=0.99）下，当???(split)≥??时，我们宣布分割已被检测到。等价地，log??必须达到决策阈值ln?[??/(1???)]。在稀疏的随机图中，这种竞争会产生一个真正的可检测性相变[6]。

对于按照固定局部规则增长的确定性网络族，同样的决策规则可以定义一个临界规模。在较小的网络中检测失败，在较大的网络中检测成功，Ramsey社区数[7]是指检测成功的最小规模，即?????(??)=min?{??:???(split)≥??}，这符合Ramsey理论的精神——一旦系统足够大，结构就会显现出来。一个简单的环永远不会破碎（????=∞），而具有次级邻居连接的环在????≈35时破碎[8]；在Dorogovtsev、Goltsev和Mendes[9]提出的无标度伪分形网络中，简单情况的值是10^95，校正后的值是42[4]、[10]。然而，在迄今为止报告的所有情况中，????和证据量的渐近增长率log??～?????都是通过数值方法获得的：证据量是封闭形式的，但阈值和斜率是从曲线上读取的。

在这项工作中，我们展示了在分层格子上，????根本不需要从曲线上读取：它是一个精确的重整化群（RG）表述。我们使用了Migdal和Kadanoff[11]、[12]提出的钻石分层格子，这是标准设置，在这种设置中，实空间缩减是精确的，且自旋模型通过迭代递归来解决[13]、[14]、[15]。得到了三个结果。首先，两个模型所依赖的量——块内和块间边的数量以及块度数之和（这些是块模型的充分统计量）——通过一代增长后，通过一个精确的线性映射发生变换，该映射的两个特征值是一个体积特征值?????（用于乘积体积）和一个缝合特征值??（用于乘积社区边界），其中??表示基本单元中的并行分支数量，??表示每个分支上的边数。其次，证据量比（这些统计量的固定非线性函数）在这种流动下被带到一个社区固定点，在该点上每条边的证据量等于ln???，这里的??是社区的数量——一个与格子无关的值，也是检测问题的固定点自由能密度。第三，????是累积证据量首次超过决策阈值的那一代，我们精确地计算了这一代，并为整个（??,??）家族给出了封闭形式的表达式，同时给出了封闭形式成立的条件。

这些检测结果在同一格子上也有热力学对应物。因为线性映射是一个实空间RG递归，我们可以问社区分区不仅是可以检测到的，而且还是热力学有序的。将Reichardt–Bornholdt社区哈密顿量[16]（其基态本身就是分区）放置在钻石格子上，并通过相同的缩减方法求解，我们发现了一个随着n→∞而持续存在的精确社区有序相。允许每个嵌套子社区有自己的标签，模数最优的描述是一个在格子深度一半处切割的分层结构，因此最佳社区数量随着格子的增长而增加；而且这种分层结构在临界温度以下保持热力学刚性，这个临界温度随社区数量的对数线性增长。

以下是两个澄清。首先，这是对一个可精确求解模型的研究，而不是一个检测算法。所测试的分区是由格子的构造预先确定的，不需要进行任何分区搜索；目的是在一个所有量都是精确的设置中，揭示社区的检测性在物理上意味着什么。其次，符号??仅表示方程（3）中的检测置信度；社区的数量，以及第10节“分层社区结构和不断增长的状态数量”和第11节“分层的有限温度有序性”中的状态数量，始终是??。

论文的结构如下。第2节定义了格子及其可检测性的自相似二分，并以封闭形式给出了其块统计量。第3节推导出这些统计量所遵循的精确线性RG映射，并确定了其体积和缝合特征值。第4节构建了贝叶斯证据，明确了每个模型使用的先验约定，并表明在这种格子上，简单比较和校正后的比较仅在节点标记先验上有所不同。第5节展示了证据密度如何流向ln???，并量化了达到该值的过程。第6节定义了????作为精确的阈值 crossing，给出了 Crossing 代的渐近估计，并确定了估计何时是精确的。第7节证明了整个（??,??）家族的基础引理、映射和密度，并给出了封闭形式的?????(??,??;??)。第8节列出了与临界现象相关的字典。第9节将Reichardt–Bornholdt哈密顿量放置在格子上并精确求解，确定了有序的分区。第10节找到了模数最优的嵌套分层结构，第11节确定了其有限温度下的刚性。第12节总结了全文。

附录详细收集了计算方法，足以重现每一个数字。

**钻石格子和束分区**
本节的目的是定义格子，定义本文其余部分分析的可检测性的二分，并以封闭形式给出两个模型所依赖的少量计数。

（??,??）钻石格子通过边替换来生长。从两个极点??和??之间的单一边开始，每一代都会将每条边替换为??条边的??条并行路径；每条路径的???1个内部节点是新的（图1）。我们介绍标准的钻石格子，其中??=??=2。

**重整化群映射**
本节确立了所有其他内容所基于的结构事实：生长作用于方程（5）中的块统计量，作为一个精确的线性映射，该映射的两个特征值将体积增长与社区边界的增长分开。

**收集统计量**
将统计量收集在向量??=(??11,??22,??12,??1,??2)?中。一代生长遵循精确的线性映射，???(??+1)=??????(??)，其中??=?? ? ? ? ? ? ? ? ? ? ? ??40000042000020000?24000204?? ? ? ? ? ? ? ? ? ? ??。其条目具有直接的物理意义。每个块内的边被替换为四条边。

**贝叶斯证据**
本节的目的是将方程（1）中进入的证据比的两个表达式作为方程（5）中统计量的显式函数写下来，并且——因为只有当两个模型被同等对待时比较才有意义——明确指出每个模型使用的先验约定。

**固定点证据密度**
本节展示了第3节中的流动将证据带到一个固定点，在该点上每条边的证据量是一个纯数字ln???，并量化了达到该值的速度。由于??在??下的流动具有主导率?????，而log??dc是??的固定函数，因此证据被流动所携带，其主导行为是透明的。对于大的计数，ln????(??+??)?(??+??)?ln?(??+??)=???ln?(??/??)???+???(ln???)，并且由于∑??≤?????????=??，???项相互抵消。最终剩下的是……

**Ramsey社区数**
本节的目的是将????定义在这个格子上作为一个精确的阈值 crossing，给出从方程（15）得出的 Crossing 代的渐近估计，并明确说明两者之间的差异。

**一般的（??,??）家族**
本节的目的是为整个（??,??）家族证明第2-6节为标准钻石格子所建立的内容：束结构、线性映射及其谱、固定点密度ln???=ln???，以及具有有限尺寸校正的 Crossing 代的封闭形式。在第t代时，有????=2+???(???1)?[(?????)???1]/(??????1)个节点，方程（17）在??=??时的渐近封闭形式为?????(??,??;??)=2+???(???1)??????1?[(?????)????1]，其中???=?log??????(ln???1???/?ln???)?，受有效性条件的约束。

**与临界现象的联系**
这一简短部分列出了本文其余部分所利用的对应关系。这些格子[11]、[12]、[13]、[14]、[15]上的临界现象与这些量的对应关系是直接的：充分统计量是耦合常数，??是递归过程，体积和缝合特征值是体积和界面缩放因子，可检测性是??≥2时流动的一个相关方向，而ln???是固定点自由能密度。这种对应关系不仅仅是形式上的：在同一格子上，可以……

**热力学有序相**
本节的目的是证明社区分区是这个格子上一个真实自旋模型的基态，确定那个分区是什么，并通过精确解证明它支持一个随着n→∞而持续存在的热力学有序相。自然哈密顿量是Reichardt和Bornholdt[16]提出的，其最小化就是社区检测，并且在单位分辨率下简化为模数，即?=?∑??≠??(?????????????????)????(????,????)，其中???????是邻接矩阵，????∈{1,…,??}是……

**分层社区结构和不断增长的状态数量**
本节的目的是证明两个社区的切割只是一个自相似树的顶部，并找到树应该切割到多深——也就是说，多少个社区最好地描述了格子。因为钻石是通过递归构建的，所以支持分割整个格子的论点也同样支持再次分割每个束，而且Reichardt–Bornholdt泛函随着分区的细化而不断改进——前提是每个嵌套子社区都有自己的标签。

**分层的有限温度有序性**
本节的目的是询问第10节中的嵌套分层是否在热力学上得以存活，就像第9节中的两块排序一样，并确定其排序温度如何依赖于社区数量。

**结论**
我们计算了钻石分层格子上的Ramsey社区数????，其中涉及的每个量都是精确的。结果如下：束分区的块统计量遵循一个精确的线性映射??，该映射具有体积特征值?????和缝合特征值??（第3节）。证据密度通过这种流动被带到每个社区的ln???（第5节），而????是累积证据量首次超过检测阈值的那一代（第6节）。

**利益冲突声明**
作者声明他们没有已知的竞争财务利益或个人关系可能会影响本文的报告。Nodes & Links Ltd为Aleksei Vazquez提供了薪资支持，但没有参与研究的概念化、分析、发表决策或手稿的准备。

**致谢**
本手稿的计算、计算机脚本和文本是在Claude Opus 4.8/5（Anthropic）的帮助下生成的。