Connectivity of the uniform random intersection graph
Connectivity of the uniform random intersection graph
复制标题
DOI：
10.1016/j.disc.2009.03.042
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
S. Blackburn;S. Gerke
中科院分区：
文献类型：
--
作者：
S. Blackburn;S. Gerke
均匀随机交图G（n，m，k）是如下构造的随机图。用随机选择的k种不同颜色的集合标记n个节点中的每一个，这些颜色是从大小为m的可能颜色的有限集合中选取的。当且仅当两个节点的标签中都出现某种颜色时，节点通过边连接。这些图出现在无线传感器网络的安全性的研究中，特别是当建模的网络图的著名的密钥预分配技术，由于Schenauer和Gligor。本文在许多情况下确定了图G（n，m，k）在n→∞时的连通度阈值。例如，当k是n的函数，使得k≥2，且m=真实的实数α为某个固定的正数α时，则G（n，m，k）几乎必然连通，当且当
A uniform random intersection graphG(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks, in particular when modelling the network graph of the well-known key predistribution technique due to Eschenauer and Gligor. The paper determines the threshold for connectivity of the graph G(n,m,k) when n→∞ in many situations. For example, when k is a function of n such that k≥2 and m=⌊nα⌋ for some fixed positive real number α then G(n,m,k) is almost surely connected when and G(n,m,k) is almost surely disconnected when