CONNECTIVITY OF SOFT RANDOM GEOMETRIC GRAPHS
CONNECTIVITY OF SOFT RANDOM GEOMETRIC GRAPHS
复制标题
DOI：
10.1214/15-aap1110
复制
发表时间：
2016-04-01
影响因子：
1.8
通讯作者：
Penrose, Mathew D.
中科院分区：
文献类型：
--
作者：
Penrose, Mathew D.
考虑在单位正方形中有n个均匀随机点的图，如果点间距离不超过r，则每对都由一条概率为p的边连接。我们证明，当n ->无穷大时，完全连通性的概率由没有孤立顶点的概率决定，其本身由孤立顶点数的泊松近似决定，均匀地覆盖所有p， r的选择。我们确定所有(p(n)，R (n)服从于R (n) = 0 （n(-)）一些。我们将第一个结果推广到更高的维度和更大的连接概率函数类。
Consider a graph on n uniform random points in the unit square, each pair being connected by an edge with probability p if the inter-point distance is at most r. We show that as n -> infinity the probability of full connectivity is governed by that of having no isolated vertices, itself governed by a Poisson approximation for the number of isolated vertices, uniformly over all choices of p, r. We determine the asymptotic probability of connectivity for all (p(n), r(n)) subject to r(n) = o(n(-epsilon)), some epsilon > 0. We generalize the first result to higher dimensions and to a larger class of connection probability functions.