A large deviation principle for block models
A large deviation principle for block models
复制标题
块模型的大偏差原理
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Sen
中科院分区：
文献类型：
--
作者：
C. Borgs;J. Chayes;Julia Gaudio;Samantha Petti;S. Sen
我们开始研究密集区块模型随机图的大偏差。继Chatterjee-Varadhan（2011）之后，我们建立了密集块模型的LDP，将其视为随机图。作为我们研究结果的一个应用，我们研究了正则图同态密度的上尾大偏差。我们确定了一个“对称”阶段的存在，在这个阶段中，以罕见事件为条件的图看起来像一个与生成图具有相同块大小的块模型。在特定的例子中，我们还确定了“对称破缺”制度的存在，其中条件结构不是具有兼容维度的块模型。这确定了这个问题的“可重入相变”现象——类似于Erdos-Renyi随机图(Chatterjee-Dey（2010), Chatterjee-Varadhan(2011)）。最后，在Lubetzky-Zhao（2015）的基础上，我们确定了正则图同态密度的对称性和对称性破缺区与Erdos-Renyi二部图的算子范数之间的精确边界。
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric" phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking" regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition" phenomenon for this problem---analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs.
关于随机超图的上尾问题
影响因子：
1
作者：
Liu, Yang P.;Zhao, Yufei
通讯作者：
Zhao, Yufei
影响因子：
1
作者：
Šileikis, Matas;Warnke, Lutz
通讯作者：
Warnke, Lutz