标题： k-连通性随机密钥图 显示英文标题

标题： k-Connectivity of Random Key Graphs

摘要： 随机密钥图表示应用了Eschenauer-Gligor随机密钥预分配方案来确保传感器之间通信安全的无线传感器网络的拓扑结构。 这些图受到了广泛关注，并且也被用于安全传感器网络之外的多种应用领域；例如，密码分析、社交网络和推荐系统。 形式上，具有$n$个节点的随机密钥图是通过从包含$Y_n$个密钥的池中为每个节点随机分配$X_n$个密钥，然后在任意两个共享至少一个密钥的节点之间添加一条无向边来构建的。 文献中已经取得了大量进展来分析随机密钥图的连通性和 $k$-连通性，其中$k$-连通性确保在移除$k$个节点或$k$条边后仍保持连通。 然而，它仍然是在$X_n \geq 2$和$X_n = o(\sqrt{\ln n})$下随机密钥图中$k$连通性的一个开放问题（$X_n=1$的情况是平凡的）。 在本文中，我们通过提供在$X_n \geq 2$下随机密钥图中$k$连通性的精确分析来回答上述问题。 显示英文摘要

摘要： Random key graphs represent topologies of secure wireless sensor networks that apply the seminal Eschenauer-Gligor random key predistribution scheme to secure communication between sensors. These graphs have received much attention and also been used in diverse application areas beyond secure sensor networks; e.g., cryptanalysis, social networks, and recommender systems. Formally, a random key graph with $n$ nodes is constructed by assigning each node $X_n$ keys selected uniformly at random from a pool of $Y_n$ keys and then putting an undirected edge between any two nodes sharing at least one key. Considerable progress has been made in the literature to analyze connectivity and $k$-connectivity of random key graphs, where $k$-connectivity of a graph ensures connectivity even after the removal of $k$ nodes or $k$ edges. Yet, it still remains an open question for $k$-connectivity in random key graphs under $X_n \geq 2$ and $X_n = o(\sqrt{\ln n})$ (the case of $X_n=1$ is trivial). In this paper, we answer the above problem by providing an exact analysis of $k$-connectivity in random key graphs under $X_n \geq 2$.