Random Geometric Graph Diameter in the Unit Ball
Random Geometric Graph Diameter in the Unit Ball
复制标题
单位球内的随机几何图形直径
作者：
Robert B. Ellis;Jeremy L. Martin;C. Yan
单位球随机几何图$G=G^d_p(λ,n)$的顶点有n个点独立且均匀地分布在${Bbb R}^d$的单位球上，当且仅当它们的R - p距离不大于λ时两个顶点相邻。像它的表亲Erdos-Renyi随机图一样，G有一个连通性阈值：λ的一个用n表示的渐近值，在这个值以上G是连通的，在这个值以下G是不连通的。在连接区内，我们确定了G的图直径的上界和下界。具体来说，几乎总是${
m diam}_p({f B})(1- 0 (1))/lambdaleq {
m diam}(G) leq {
m diam}_p({f B})(1+O((ln ln n/{
m ln},n)^{1/d}))/lambda$，其中${
m diam}_p({f B})$是单位球B的p直径。我们采用了概率组合学和随机几何方法的结合。
The unit ball random geometric graph $G=G^d_p(lambda,n)$ has as its vertices n points distributed independently and uniformly in the unit ball in ${Bbb R}^d$, with two vertices adjacent if and only if their ℓp-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper and lower bounds for the graph diameter of G. Specifically, almost always, ${
m diam}_p({f B})(1-o(1))/lambdaleq {
m diam}(G) leq {
m diam}_p({f B})(1+O((ln ln n/{
m ln},n)^{1/d}))/lambda$, where ${
m diam}_p({f B})$ is the ℓp-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.