论文标题
随机K-OUT图的连通性的紧密界限
Tight Bounds for Connectivity of Random K-out Graphs
论文作者
论文摘要
随机k-out图用于多种应用程序，包括由随机成对密钥预处理方案和支付渠道网络确保的传感器网络建模。带有$ N $节点的随机K-OUT图如下所示。每个节点都会向$ k $不同的节点进行边缘，以随机统一选择。然后忽略边缘的方向，产生一个无向图。随机K-Out图的一个有趣的属性是，对于任何$ k \ geq2 $，它们几乎肯定是在大的$ n $限制中连接的。这意味着与经典的随机图模型（包括Erdős-rényi图形（$ o（n \ log n）$）相比，它们的边缘（$ o（n）$）的属性很容易，即具有较少的边缘（$ o（n）$）。这项工作旨在揭示连接随机K-OUT图的渐近行为在多大程度上很容易扩展到数字$ n $ nodes较小的情况。当$ n $有限时，我们就可以在连接性的概率上建立上限和下限。我们的下限在现有结果上显着改善，并表明随机K-OUT图可以在比以前所知的更小的网络大小上达到给定的连接概率。我们还表明，已建立的上限和下限匹配订单。即，不可能进一步改善$ n $的订单。特别是，我们证明了所有$ k \ geq 2 $的连接概率为$ 1-θ（{1}/{n^{k^2-1}}）$。通过数值模拟，我们表明我们的边界紧密反映了经验观察到的连通性的概率。
Random K-out graphs are used in several applications including modeling by sensor networks secured by the random pairwise key predistribution scheme, and payment channel networks. The random K-out graph with $n$ nodes is constructed as follows. Each node draws an edge towards $K$ distinct nodes selected uniformly at random. The orientation of the edges is then ignored, yielding an undirected graph. An interesting property of random K-out graphs is that they are connected almost surely in the limit of large $n$ for any $K \geq2$. This means that they attain the property of being connected very easily, i.e., with far fewer edges ($O(n)$) as compared to classical random graph models including Erdős-Rényi graphs ($O(n \log n)$). This work aims to reveal to what extent the asymptotic behavior of random K-out graphs being connected easily extends to cases where the number $n$ of nodes is small. We establish upper and lower bounds on the probability of connectivity when $n$ is finite. Our lower bounds improve significantly upon the existing results, and indicate that random K-out graphs can attain a given probability of connectivity at much smaller network sizes than previously known. We also show that the established upper and lower bounds match order-wise; i.e., further improvement on the order of $n$ in the lower bound is not possible. In particular, we prove that the probability of connectivity is $1-Θ({1}/{n^{K^2-1}})$ for all $K \geq 2$. Through numerical simulations, we show that our bounds closely mirror the empirically observed probability of connectivity.
