A limit theorem for small cliques in inhomogeneous random graphs
A limit theorem for small cliques in inhomogeneous random graphs
复制标题
非齐次随机图中小团的极限定理
DOI：
--
复制
发表时间：
2019
影响因子：
0.9
通讯作者：
Matas Šileikis
中科院分区：
文献类型：
--
作者：
J. Hladký;C. Pelekis;Matas Šileikis
图子理论有一个自然的抽样过程，这导致了Erdens-Rényi随机图的一个非齐次变体，称为W-随机图。我们通过矩量法证明了这类随机图中r-团数的一个极限定理。我们证明，在稠密Erdens-Rényi随机图的情况下，涨落是nr−1阶的正态，而W-随机图的涨落可能是0阶、nr−1阶或nr−0.5阶。此外，当涨落的阶数为nr−0.5时，它们是正态的，而当涨落的阶数为nr−1时，它们表现出正态的或特定类型的卡方行为，其参数与W的谱性质有关。这些结果也可以根据投影方法从一般设置中推导出来。除了提供替代证明，我们的方法直接链接到graphons的理论。
The theory of graphons comes with a natural sampling procedure, which results in an inhomogeneous variant of the Erdős–Rényi random graph, called W ‐random graphs. We prove, via the method of moments, a limit theorem for the number of r ‐cliques in such random graphs. We show that, whereas in the case of dense Erdős–Rényi random graphs the fluctuations are normal of order nr−1 , the fluctuations in the setting of W ‐random graphs may be of order 0,nr−1 , or nr−0.5 . Furthermore, when the fluctuations are of order nr−0.5 they are normal, while when the fluctuations are of order nr−1 they exhibit either normal or a particular type of chi‐square behavior whose parameters relate to spectral properties of W . These results can also be deduced from a general setting, based on the projection method. In addition to providing alternative proofs, our approach makes direct links to the theory of graphons.