Zero-One Law for Connectivity in Superposition of Random Key Graphs on Random Geometric Graphs

Abstract

We study connectivity property in the superposition of random key graph on random geometric graph. For this class of random graphs, we establish a new version of a conjectured zero-one law for graph connectivity as the number of nodes becomes unboundedly large. The results reported here strengthen recent work by the Krishnan et al.

Academic Editor:Filippo Cacace

College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China

Received 24 June 2015; Revised 11 October 2015; Accepted 18 October 2015; 16 November 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Random key graph (RKG), also known as uniform random intersection graph, is a random graph defined below. Consider a set with [figure omitted; refer to PDF] nodes and another key pool with [figure omitted; refer to PDF] keys; we assume each node randomly chooses [figure omitted; refer to PDF] distinct keys for its key ring; two nodes can establish a secure link between them if they share at least one common key in their key rings.

The random key graph is naturally associated with the random key predistribution scheme of Eschenauer and Gligor [1] for wireless sensor networks (WSNs). A WSN is a collection of distributed sensor devices that are able to communicated wirelessly and supports wide range of applications such as health and environment monitoring, imaging, tracking, and biomedical research; see [2]. These applications require all nodes in the network to be within communication range and to be connected with high probability.

Some partial results concerning the connectivity of RKGs were given in [3-5]. In [6], Rybarczyk gave asymptotic tight bounds for the thresholds of the connectivity, phase transition, and diameter of the largest connected component in RKGs for all ranges of [figure omitted; refer to PDF] .

With the advent of ad hoc sensor networks, an interesting class of random graphs, namely, random geometric graphs (RGGs), has gained new importance and its properties have been the subject of much study. Here the nodes are randomly distributed in a finite Euclidean space and there is an edge between two nodes if the Euclidean distance between them is below a specified threshold. Much work has been done on graph theoretic properties of such graph, comprehensively summarized in the monograph of [7].

Recently, there is interest in random graphs in which an edge is determined by more than one random property, that is, superposition of different random graphs. The superposition of ER random graphs over RGGs has been of interest for quite some time now. Recent work on such random graphs is in [8, 9] where connectivity properties and the distribution of isolated nodes are analyzed. And the superposition of ER random graphs on RKGs is considered in [10]. Such a graph is constructed as follows: a RKG is first formed based on the key distribution and each edge in this graph is deleted with a specified probability.

The superposition of RKGs on RGGs is first studied in [11]. The [figure omitted; refer to PDF] nodes are distributed in a finite Euclidean space and each node is assigned a key ring of [figure omitted; refer to PDF] distinct keys drawn randomly from a pool of [figure omitted; refer to PDF] keys. Two nodes have an edge if and only if they share at least one common key in their key rings and their Euclidean distance is at most [figure omitted; refer to PDF] . Pietro et al. [11] have shown that under the scaling [figure omitted; refer to PDF] , the one-law that this class of random graphs is connected follows if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Another notable work is due by Krzywdzinski and Rybarczyk [12], where the authors have improved these results and established the one-law for [figure omitted; refer to PDF] without any constraint on [figure omitted; refer to PDF] . Recently, Krishnan et al. [13] have shown that for large [figure omitted; refer to PDF] , this class of random graphs will be connected if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are selected such that [figure omitted; refer to PDF] for any [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . They also observed that for large [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , the probability that this class of random graphs is disconnected is at least [figure omitted; refer to PDF] if the scaling satisfies [figure omitted; refer to PDF]

The connectivity in the superposition of RKGs on RGGs is still studied in this paper. Assuming that [figure omitted; refer to PDF] , we show that given [figure omitted; refer to PDF] , this class of random graphs is disconnected if [figure omitted; refer to PDF] , and for [figure omitted; refer to PDF] , this class of random graphs is connected.

In this paper, we use standard, asymptotic notations: [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] for [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , respectively, all limits are taken as [figure omitted; refer to PDF] . The phrase "with high probability" (abbreviated whp) means with probability tending to one as [figure omitted; refer to PDF] tends to infinity.

The rest of the paper is organized as follows. Our main result is presented in Section 2. Namely, the theorem concerning zero-one law for graph connectivity is presented. Section 3 contains technical proof of Theorem 1. Finally, Section 4 discusses prospects of establishing tighter connectivity thresholds in the superposition of RKGs on RGGs.

2. Main Result

The [figure omitted; refer to PDF] nodes are uniformly and independently distributed in [figure omitted; refer to PDF] . Let [figure omitted; refer to PDF] be the location of point [figure omitted; refer to PDF] . A key pool with [figure omitted; refer to PDF] cryptographic keys is designated for the network of [figure omitted; refer to PDF] nodes. Node [figure omitted; refer to PDF] randomly chooses a subset [figure omitted; refer to PDF] of keys from the key pool with [figure omitted; refer to PDF] . Our interest is in the random graph [figure omitted; refer to PDF] with [figure omitted; refer to PDF] nodes and edges formed as follows. An edge [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , is present in [figure omitted; refer to PDF] if both of the following two conditions are satisfied: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] represents the Euclidean norm. Condition [figure omitted; refer to PDF] produces a random geometric graph with the transmission range [figure omitted; refer to PDF] . Imposing condition [figure omitted; refer to PDF] on [figure omitted; refer to PDF] retains the edges of the random geometric graph for which the two nodes share at least one common key. Thus [figure omitted; refer to PDF] is a superposition of RKG on RGG.

In the following, to avoid technicalities which obscure the main ideas, we will neglect edge effects resulting due to the fact that [figure omitted; refer to PDF] nodes are distributed uniformly and independently over a folded unit square [figure omitted; refer to PDF] with continuous boundary conditions and a node is close to the boundary of [figure omitted; refer to PDF] . Throughout the paper, we set [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] for any small [figure omitted; refer to PDF] . The following theorem gives zero-one law for the connectivity of a superposition of RKG on RGG.

Theorem 1.

Let [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Then

(i) if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , then with high probability [figure omitted; refer to PDF] is disconnected;

(ii) if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , then with high probability [figure omitted; refer to PDF] is connected.

The first part of the Theorem 1 is proved by using the second moment method, that is, considering the probability of finding at least one isolated node in the network for a random graph [figure omitted; refer to PDF] . The second part takes a slightly different approach, we assume that [figure omitted; refer to PDF] is entirely coved by circle cells of radius [figure omitted; refer to PDF] . Connectivity of [figure omitted; refer to PDF] is ensured as follows: [figure omitted; refer to PDF] every circle cell is dense; namely, every circle cell has [figure omitted; refer to PDF] nodes inside it; [figure omitted; refer to PDF] the overlapping structure of any two adjacent circle cells has at least one common node; and [figure omitted; refer to PDF] the nodes in any circle cell form a connected subgraph.

3. Proof of Theorem 1

Before proceeding, we first introduce some definitions and auxiliary lemmas. For [figure omitted; refer to PDF] , let [figure omitted; refer to PDF] if node [figure omitted; refer to PDF] is isolated in [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Then, [figure omitted; refer to PDF] is exactly the number of isolated nodes in [figure omitted; refer to PDF] . Let [figure omitted; refer to PDF] denote the cardinality of a set [figure omitted; refer to PDF] and let [figure omitted; refer to PDF] , [figure omitted; refer to PDF] denote the expectation and variance of random variable [figure omitted; refer to PDF] , respectively. As a special case of Markov's inequality the first moment method states that [figure omitted; refer to PDF] and the second moment method (special case of Tschebyscheff's inequality) states that [figure omitted; refer to PDF] If [figure omitted; refer to PDF] is a binomial distributed random variable, [figure omitted; refer to PDF] and for any [figure omitted; refer to PDF] , then we will use the following variants of Chernoff's inequality (see [14]): [figure omitted; refer to PDF]

Of course, it is easy to check that [figure omitted; refer to PDF] under the assumption that [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the probability that two nodes share at least one common key. Throughout, we make use of the standard bounds [figure omitted; refer to PDF] valid for all [figure omitted; refer to PDF] with [figure omitted; refer to PDF] . Finally, we note the equation [figure omitted; refer to PDF] holds if [figure omitted; refer to PDF] .

Proof of Statement (i) of Theorem 1.

Let [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the probability that two nodes share at least one common key in their key rings. By linearity of expectation, [figure omitted; refer to PDF] ; hence [figure omitted; refer to PDF] as [figure omitted; refer to PDF] . The second moment method now implies the result we require, provided that we can show that [figure omitted; refer to PDF] . Now [figure omitted; refer to PDF] and so it suffices to show that [figure omitted; refer to PDF] . Note that [figure omitted; refer to PDF] where 1, 2 are fixed nodes. Since [figure omitted; refer to PDF] , it therefore suffices to prove that [figure omitted; refer to PDF] Note that [figure omitted; refer to PDF] take the value 1 exactly when node 1 and node 2 are both isolated. Consider two discs of radius [figure omitted; refer to PDF] centered at [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ; let [figure omitted; refer to PDF] ; the cross term [figure omitted; refer to PDF] is shown to be given by [figure omitted; refer to PDF]

Conditional on the range of [figure omitted; refer to PDF] , we consider the following three cases. In each case, the conditional joint probability of two nodes being isolated can be obtained from [13].

[figure omitted; refer to PDF] : this case happens with the probability [figure omitted; refer to PDF] , and [figure omitted; refer to PDF]

[figure omitted; refer to PDF] [figure omitted; refer to PDF] : this case happens with the probability [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] where [figure omitted; refer to PDF]

(3) [figure omitted; refer to PDF] : this case happens with the probability [figure omitted; refer to PDF] , and [figure omitted; refer to PDF]

The upper bound on [figure omitted; refer to PDF] that nodes 1 and 2 are isolated if [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is obtained together using (16) and (17). So [figure omitted; refer to PDF] is upper-bounded as follows: [figure omitted; refer to PDF] See [13] for details.

From (14), (15), and (18), the term [figure omitted; refer to PDF] is bounded as [figure omitted; refer to PDF] The term [figure omitted; refer to PDF] also satisfies [figure omitted; refer to PDF] Since [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] , we find that [figure omitted; refer to PDF] The above two convergence formulas are true since [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . We see that (13) holds as required, which implies that [figure omitted; refer to PDF] as [figure omitted; refer to PDF] , which concludes the proof.

If [figure omitted; refer to PDF] for any [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] . Then using the first moment method, we see that the probability [figure omitted; refer to PDF] holds; this implies a.a.s. there are no isolated nodes in random graph [figure omitted; refer to PDF] . The upcoming corollary is immediate from the proof of statement (i) of Theorem 1.

Corollary 2.

In the model [figure omitted; refer to PDF] , let [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF]

(i) If [figure omitted; refer to PDF] as [figure omitted; refer to PDF] , then whp [figure omitted; refer to PDF] contains at least an isolated node.

(ii) If [figure omitted; refer to PDF] as [figure omitted; refer to PDF] , then whp [figure omitted; refer to PDF] does not contain an isolated node.

Proof of Statement (ii) of Theorem 1.

We consider the unit-area square on [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] is divided into square cells of size [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is an integer. Let the center of square cell be the center of the circle cell and let the diagonal line of the square cell be the diameter of the circle cell. In this way, [figure omitted; refer to PDF] is entirely covered by the circle cells. Also we let [figure omitted; refer to PDF] ; this means that two nodes in the same circle cell are within communicating range of each other.

Recall that [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . In order to complete the proof, we show the following two lemmas.

Lemma 3. (i) Every circle cell is dense; specifically, whp every circle cell has [figure omitted; refer to PDF] nodes in it .

(ii) The overlapping structure of any two adjacent circle cells whp has [figure omitted; refer to PDF] nodes .

Proof . (i) First, we analyze the denseness of every circle cell; let [figure omitted; refer to PDF] denote the number of nodes in circle cell [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Obviously, [figure omitted; refer to PDF] is a binomial random variable with parameters [figure omitted; refer to PDF] . Let [figure omitted; refer to PDF] denote the event that the circle cell [figure omitted; refer to PDF] is not dense, in other words, for any [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Using Chernoff's inequalities on [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] Consequently [figure omitted; refer to PDF] which implies that every circle cell is dense.

(ii) Now we consider the nodes in the overlapping structure of any two adjacent circle cells. Let [figure omitted; refer to PDF] denote the number of nodes in the overlapping structure of any two adjacent circle cells. Clearly [figure omitted; refer to PDF] is a binomial random variable with parameters [figure omitted; refer to PDF] . For any [figure omitted; refer to PDF] , we also use Chernoff's inequalities on [figure omitted; refer to PDF] : [figure omitted; refer to PDF] From the two above inequalities we may easily get [figure omitted; refer to PDF] The above expression implies that [figure omitted; refer to PDF] is very likely close to its expectation [figure omitted; refer to PDF] . So we get our result that whp the overlapping structure of any two adjacent circle cells has at least one common node.

Lemma 4. The nodes in any circle cell form a connected subgraph; that is, for any fixed [figure omitted; refer to PDF] circle cell [figure omitted; refer to PDF] contains no components of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the number of nodes in circle cell [figure omitted; refer to PDF] .

Proof. This part takes a slightly different approach; we consider the subgraph formed by the nodes in circle cell [figure omitted; refer to PDF] ; denote this subgraph by [figure omitted; refer to PDF] . We will show that for any circle cell [figure omitted; refer to PDF] there are no components of size [figure omitted; refer to PDF] in [figure omitted; refer to PDF] .

Consider any fixed circle cell [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , for any nonempty subset [figure omitted; refer to PDF] of nodes in circle cell [figure omitted; refer to PDF] ; that is, [figure omitted; refer to PDF] , with [figure omitted; refer to PDF] ; define the following events.

[figure omitted; refer to PDF] : a subgraph induced by nodes in [figure omitted; refer to PDF] is connected.

[figure omitted; refer to PDF] : [figure omitted; refer to PDF] is isolated in circle cell [figure omitted; refer to PDF] ; that is, there are no edges between the nodes in [figure omitted; refer to PDF] and the nodes in the complement [figure omitted; refer to PDF] . Consider [figure omitted; refer to PDF] Further, let [figure omitted; refer to PDF] and [figure omitted; refer to PDF] denote [figure omitted; refer to PDF] and [figure omitted; refer to PDF] with [figure omitted; refer to PDF] , respectively. Then the sufficient condition for every circle cell a.a.s. containing no components of size [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) is to have [figure omitted; refer to PDF] . Conditioned on [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] The above inequality uses bounds on the factorial, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ; from Lemma [figure omitted; refer to PDF] , we get [figure omitted; refer to PDF] ; thus we focus on showing that [figure omitted; refer to PDF] . Note that [figure omitted; refer to PDF]

We let [figure omitted; refer to PDF] denote the number of distinct keys in the component of size [figure omitted; refer to PDF] in [figure omitted; refer to PDF] . Adapting [5], for any [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] From [5], we know that [figure omitted; refer to PDF]

First we use the standard Poissonization technique [7, 15] to show the probability of having isolated nodes in any of the circle cells. Denote the circle [figure omitted; refer to PDF] by [figure omitted; refer to PDF] ; let [figure omitted; refer to PDF] be the event that node [figure omitted; refer to PDF] is isolated in [figure omitted; refer to PDF] , and let [figure omitted; refer to PDF] be the intersection of [figure omitted; refer to PDF] and the disk centered at position [figure omitted; refer to PDF] with radius [figure omitted; refer to PDF] , where node [figure omitted; refer to PDF] is at position [figure omitted; refer to PDF] . Similar to the discussion in [16], the number of nodes within [figure omitted; refer to PDF] follows a Poisson distribution with mean [figure omitted; refer to PDF] ; and to have an edge with [figure omitted; refer to PDF] , a node not only has to be within a [figure omitted; refer to PDF] but also has to share at least a key with node [figure omitted; refer to PDF] , so the number of nodes neighboring to [figure omitted; refer to PDF] follows a Poisson distribution with mean [figure omitted; refer to PDF] . Integrating [figure omitted; refer to PDF] over [figure omitted; refer to PDF] , the probability that node [figure omitted; refer to PDF] is isolated in [figure omitted; refer to PDF] is given by [figure omitted; refer to PDF] The probability that there are no isolated nodes in any of the circle cells is bounded below: [figure omitted; refer to PDF] The second step and the third step are obtained since [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. Since [figure omitted; refer to PDF] , we get [figure omitted; refer to PDF]

Next we prove that every circle cell [figure omitted; refer to PDF] contains no component of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . The sum term in (30) is evaluated in following three cases based on the size of the component [figure omitted; refer to PDF] .

Case 1 [figure omitted; refer to PDF] . In the case, fewer than [figure omitted; refer to PDF] keys are assigned to the component [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is an integer. Note that [figure omitted; refer to PDF]

First, we will give an upper bound on [figure omitted; refer to PDF] because [figure omitted; refer to PDF] Since [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] Since [figure omitted; refer to PDF] we have [figure omitted; refer to PDF] and thus for sufficiently large [figure omitted; refer to PDF] [figure omitted; refer to PDF] Then we have [figure omitted; refer to PDF] The second inequality is true since [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . The last step holds since [figure omitted; refer to PDF] satisfies [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

The following term satisfies [figure omitted; refer to PDF] Because [figure omitted; refer to PDF] , we also have [figure omitted; refer to PDF]

Since [figure omitted; refer to PDF] , we get [figure omitted; refer to PDF] . Then for sufficiently large [figure omitted; refer to PDF] , from above discussion, we have [figure omitted; refer to PDF]

Hence the probability that the subgraph [figure omitted; refer to PDF] has a component of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is [figure omitted; refer to PDF]

Case 2 [figure omitted; refer to PDF] Here [figure omitted; refer to PDF] . In this case, we assume that the component [figure omitted; refer to PDF] is assigned at most ( [figure omitted; refer to PDF] keys. The probability that the subgraph [figure omitted; refer to PDF] contains a component of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , is [figure omitted; refer to PDF] The above bound is true since the expression [figure omitted; refer to PDF] , where we are summing over all subsets of nodes of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . We wish to prove that this sum tends to 0 as [figure omitted; refer to PDF] .

Now we prove that [figure omitted; refer to PDF] as [figure omitted; refer to PDF] . Similar to the argument in the proof of case 1, we get [figure omitted; refer to PDF] The summand in this last expression may be written in the form [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Since [figure omitted; refer to PDF] has no internal maximal value, our summand is maximized at the extremes of its range. Let [figure omitted; refer to PDF] denote the maximum of the summand; here [figure omitted; refer to PDF] As [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF]

Now consider the second term in (45) [figure omitted; refer to PDF] Rewrite the above using the notation [figure omitted; refer to PDF] and then [figure omitted; refer to PDF] The last step is true since [figure omitted; refer to PDF] , so for some appropriate [figure omitted; refer to PDF] , [figure omitted; refer to PDF]

Case 3 [figure omitted; refer to PDF] : [figure omitted; refer to PDF] . In this case, the component [figure omitted; refer to PDF] of circle cell [figure omitted; refer to PDF] is assigned at most [figure omitted; refer to PDF] keys; we have that [figure omitted; refer to PDF] Now we first show [figure omitted; refer to PDF] as [figure omitted; refer to PDF] : [figure omitted; refer to PDF]

The third inequality uses [figure omitted; refer to PDF] . Since [figure omitted; refer to PDF] , the final expression tends to 0.

The term [figure omitted; refer to PDF] is bounded as follows. [figure omitted; refer to PDF] The first inequality uses [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Since [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , then for any [figure omitted; refer to PDF] , the last expression tends to 0.

Therefore the probability that the subgraph [figure omitted; refer to PDF] has a component of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] is [figure omitted; refer to PDF] From the above discussions, we have shown that for every circle cell [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , the probability for the existence of component of size [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , tends to 0 as [figure omitted; refer to PDF] tends to infinity, which concludes Lemma [figure omitted; refer to PDF] .

We have proved that the overlapping structure of two adjacent circle cells contains at least one node and every circle cell is connected. The above two conditions ensure that [figure omitted; refer to PDF] is connected. Combining Lemma [figure omitted; refer to PDF] with Lemma [figure omitted; refer to PDF] , the statement (ii) of Theorem 1 is established.

4. Conclusion and Future Work

Connectivity in [figure omitted; refer to PDF] is the core subject of our paper. We obtain the zero-one law for graph connectivity in [figure omitted; refer to PDF] under the given conditions. In order to get zero-one law for graph connectivity, we initially use the second moment method to get the 0-statement; then we show that any two adjacent circle cells share at least one common node and prove that any circle cell is connected to get the 1-statement.

We conjecture that it is possible to prove a sharper connectivity threshold for random graph [figure omitted; refer to PDF] . Indeed, we believe that the following conjecture is true.

Conjecture 5.

Let [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF]

(i) If [figure omitted; refer to PDF] , then whp [figure omitted; refer to PDF] is disconnected.

(ii) If [figure omitted; refer to PDF] , then the probability that [figure omitted; refer to PDF] is connected tends to [figure omitted; refer to PDF] .

(iii): If [figure omitted; refer to PDF] , then whp [figure omitted; refer to PDF] is connected.

The results in this paper hold under the condition that [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . It would be interesting to see whether such results could be established under the condition that [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , which remains an open research challenge.

Acknowledgments

The work was supported by National Natural Science Foundation of China (NSFC) under Grant no. 11071272 and the project sponsored by the scientific research foundation for the returned overseas scholars of the Education Ministry of China.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] L. Eschenauer, V. D. Gligor, "A key-management scheme for distributed sensor networks," in Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 41-47, ACM, November 2002.

[2] I. F. Akyildiz, T. Melodia, K. R. Chowdury, "Wireless multimedia sensor networks: a survey," IEEE Wireless Communications , vol. 14, no. 6, pp. 32-39, 2007.

[3] S. R. Blackburn, S. Gerke, "Connectivity of the uniform random intersection graph," Discrete Mathematics , vol. 309, no. 16, pp. 5130-5140, 2009.

[4] E. Godehardt, J. Jaworski, K. Rybarczyk, "Random intersection graphs and classification," Advances in Data Analysis , of Studies in Classification, Data Analysis, and Knowledge Organization, pp. 67-74, Springer, Berlin, Germany, 2007.

[5] O. Yagan, A. M. Makowski, "Zero-one laws for connectivity in random key graphs," IEEE Transactions on Information Theory , vol. 58, no. 5, pp. 2983-2999, 2012.

[6] K. Rybarczyk, "Diameter, connectivity, and phase transition of the uniform random intersection graph," Discrete Mathematics , vol. 311, no. 17, pp. 1998-2019, 2011.

[7] M. D. Penrose, "On k -connectivity for a geometric random graph," Random Structure and Algorithms , vol. 15, no. 2, pp. 145-164, 1999.

[8] G. Mao, B. D. O. Anderson, "Towards a better understanding of large-scale network models," IEEE/ACM Transactions on Networking , vol. 20, no. 2, pp. 408-421, 2012.

[9] C.-W. Yi, P.-J. Wan, X.-Y. Li, O. Frieder, "Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes," IEEE Transactions on Communications , vol. 54, no. 3, pp. 510-517, 2006.

[10] O. Yagan, "Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel," IEEE Transactions on Information Theory , vol. 58, no. 6, pp. 3821-3835, 2012.

[11] R. D. Pietro, L. V. Mancini, A. Mei, A. Panconesi, J. Radhakrishnan, "Connectivity properties of secure wireless sensor networks," in Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks Association for Computing Machinery (SASN '04), pp. 53-58, Washington, DC, USA, October 2004.

[12] K. Krzywdzinski, K. Rybarczyk, "Geometric graphs with randomly deleted edges-connectivity and routing protocols," Mathematical Foundations of Computer Science 2011 , pp. 544-555, Springer, Berlin, Germany, 2011.

[13] B. S. Krishnan, A. Ganesh, D. Manjunath, "On connectivity thresholds in superposition of random key graphs on random geometric graphs," in Proceedings of the IEEE International Symposium on Information Theory Proceedings (ISIT '13), pp. 2389-2393, IEEE, Istanbul, Turkey, July 2013.

[14] S. Janson, T. Luczak, A. Rucinski Random Graphs , Wiley, New York, NY, USA, 2000.

[15] M. D. Penrose Random Geometric Graphs , Oxford University Press, Oxford, UK, 2003.

[16] J. Zhao, O. Yagan, V. Gligor, "Connectivity in secure wireless sensor networks under transmission constraints," in Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1294-1301, Monticello, Va, USA, September 2014.