Percolation in the k-nearest neighbor graph
Percolation in the k-nearest neighbor graph
复制标题
k 最近邻图中的渗滤
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
B. Bollobás
中科院分区：
文献类型：
--
作者：
P. Balister;B. Bollobás
设P是R2中强度为1的Poisson过程，对固定的整数k，将P中的每一点连接到它的k个近邻，生成一个有向随机几何图Gk(R2).对于不同的“分支”定义，我们证明了在Gk(R2)中几乎必然产生无限连通分支的k值的界。我们还给出了所需k的精确值的高置信度结果。特别地，对于Gk(R2)的基础(无向)图上的渗流，我们证明了k=11是充分的，并且高置信度地证明了k=3是渗流的实际门限。
Let P be a Poisson process of intensity one in R 2. For a fixed integer k, join every point of P to its k nearest neighbors, creating a directed random geometric graph G k (R 2). We prove bounds on the values of k that, almost surely, result in an infinite connected component in G k (R 2) for various definitions of " component ". We also give high confidence results for the exact values of k needed. In particular, for percolation on the underlying (undirected) graph of G k (R 2), we prove that k = 11 is sufficient, and show with high confidence that k = 3 is the actual threshold for percolation.