The q-composite key predistribution scheme [1] is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Prior work [2]-[4] explores topological properties of WSNs employing the q-composite scheme for q = 1 with unreliable communication links modeled as independent on off channels. In this paper, we investigate topological properties related to the node degree in WSNs operating under the q-composite scheme and the on off channel model. Our results apply to general q and are stronger than those reported for the node degree in prior work even for the case of q being 1. Specifically, we show that the number of nodes with certain degree asymptotically converges in distribution to a Poisson random variable, present the asymptotic probability distribution for the minimum degree of the network, and establish the asymptotically exact probability for the property that the minimum degree is at least an arbitrary value. Numerical experiments confirm the validity of our analytical findings.
When @math , for graph @math (also referred to as a random key graph @cite_16 @cite_31 @cite_13 or a uniform random intersection graph @cite_24 @cite_26 ) and some of its variants, a number of properties have been extensively studied in the literature including component evolution @cite_40 , connectivity @cite_24 @cite_31 @cite_26 , @math -connectivity @cite_36 @cite_48 , node degree distribution @cite_51 @cite_47 @cite_49 @cite_38 and independent sets @cite_3 @cite_54 .
@cite_38 @cite_47 @cite_26 @cite_36 @cite_48 @cite_54 @cite_3 @cite_24 @cite_40 @cite_49 @cite_51 @cite_31 @cite_16 @cite_13
2107866581 2963768473 1966248090 1890866918
Random key graphs form a class of random intersection graphs that are naturally induced by the random key predistribution scheme of Eschenauer and Gligor for securing wireless sensor network (WSN) communications. Random key graphs have received much attention recently, owing in part to their wide applicability in various domains, including recommender systems, social networks, secure sensor networks, clustering and classification analysis, and cryptanalysis to name a few. In this paper, we study connectivity properties of random key graphs in the presence of unreliable links. Unreliability of graph links is captured by independent Bernoulli random variables, rendering them to be on or off independently from each other. The resulting model is an intersection of a random key graph and an Erdős–Renyi graph, and is expected to be useful in capturing various real-world networks; e.g., with secure WSN applications in mind, link unreliability can be attributed to harsh environmental conditions severely impairing transmissions. We present conditions on how to scale this model’s parameters so that: 1) the minimum node degree in the graph is at least @math and 2) the graph is @math -connected, both with high probability as the number of nodes becomes large. The results are given in the form of zero-one laws with critical thresholds identified and shown to coincide for both graph properties. These findings improve the previous results by Rybarczyk on @math -connectivity of random key graphs (with reliable links), as well as the zero-one laws by Yagan on one-connectivity of random key graphs with unreliable links. Random s-intersection graphs have recently received much interest in a wide range of application areas. Broadly speaking, a random s-intersection graph is constructed by first assigning each vertex a set of items in some random manner, and then putting an undirected edge between all pairs of vertices that share at least s items (the graph is called a random intersection graph when s = 1). A special case of particular interest is a uniform random s-intersection graph, where each vertex independently selects the same number of items uniformly at random from a common item pool. Another important case is a binomial random s-intersection graph, where each item from a pool is independently assigned to each vertex with the same probability. Both models have found numerous applications thus far including cryptanalysis, and modeling recommender systems, secure sensor networks, online social networks, trust networks and small-world networks (uniform random s-intersection graphs), as well as clustering analysis, classification, and the design of integrated circuits (binomial random s-intersection graphs). In this paper, for binomial uniform random s-intersection graphs, we present results related to k-connectivity and minimum vertex degree. Specifically, we derive the asymptotically exact probabilities and zero--one laws for the following three properties: (i) k-vertex-connectivity, (ii) k-edge-connectivity and (iii) the property of minimum vertex degree being at least k. We study isolated vertices and connectivity in the random intersection graph 𝐺(𝑛,𝑚,𝑝). A Poisson convergence for the number of isolated vertices is determined at the threshold for absence of isolated vertices, which is equivalent to the threshold for connectivity. When 𝑚=⌊𝑛𝛼⌋ and 𝛼>6, we give the asymptotic probability of connectivity at the threshold for connectivity. Analogous results are well known in Erdős-Renyi random graphs. Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min 1, x(i)x(j) n (1 + a n(1 3)) . We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2 3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3 EX s. In particular, we conclude that the size of the largest connected component is of order n(2 3). (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486-539, 2013 (Less)