A Functional Limit Theorem for Random Graphs with Applications to Subgraph Count Statistics
A Functional Limit Theorem for Random Graphs with Applications to Subgraph Count Statistics
复制标题
随机图的函数极限定理及其在子图计数统计中的应用
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
S. Janson
中科院分区：
文献类型：
--
作者：
S. Janson
我们考虑一个随机图，通过在随机时间添加新的边（不同的边被添加在独立和相同分布的时间）。本文证明了随机图的一类统计量作为随机过程的泛函极限定理。该证明基于鞅收敛定理。演化的随机图允许我们通过将注意力固定到固定时间来研究随机图模型Kn，p，以及通过在随机时间研究模型Kn，N来研究它，它恰好包含N条边。特别地，我们得到了与给定图G同构的子图个数n ∞的渐近分布，包括Kn，p（p固定）和Kn，N（N/（n ~ 2）p）.结果是惊人的不同; 2两个模型都产生渐近正态分布，但是方差随着n的不同幂增长（对于Kn，N，方差增长较慢; n的幂通常相差1，但有时相差3）。我们还研究了一个给定类型的诱导子图的数量，并得到类似的，但更复杂的结果。在某些特殊情况下，极限分布不是正态分布。
We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model Kn, p, by fixing attention to a fixed time, and the model Kn, N, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n ∞ of the number of subgraphs isomorphic to a given graph G, both for Kn, p (p fixed) and Kn, N (N/(n2) p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for Kn, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.