{'fraction_non_alphanumeric': 0.05722538839878211, 'fraction_numerical': 0.028378483878522914, 'mean_word_length': 3.765438988095238, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A zero-one law for the existence of triangles in random key graphs

Random key graphs are random graphs induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. For this class of random graphs we show the existence of a zero-one law for the appearance of triangles, and identify the corresponding critical scaling. This is done by applying the method of first and second moments to the number of triangles in the graph.


Introduction
Random key graphs are random graphs that belong to the class of random intersection graphs [13]; in fact they are sometimes called uniform random intersection graphs by some authors [6,7]. They have appeared recently in application areas as diverse as clustering analysis [6,7], collaborative filtering in recommender systems [10] and random key predistribution for wireless sensor networks (WSNs) [4]. In this last context, random key graphs naturally occur in the study of the following random key predistribution scheme introduced by Eschenauer and Gligor [4]: Before deployment, each sensor in a WSN is independently assigned K distinct cryptographic keys which are selected at random from a pool of P keys. These K keys constitute the key ring of the node and are inserted into its memory. Two sensor nodes can then establish a secure link between them if they are within transmission range of each other and if their key rings have at least one key in common; see [4] for implementation details. If we assume full visibility, namely that nodes are all within communication range of each other, then secure communication between two nodes requires only that their key rings share at least one key. The resulting notion of adjacency defines the class of random key graphs; see Section 2 for precise definitions.
Much efforts have recently been devoted to developing zero-one laws for the property of connectivity in random key graphs. A key motivation can be found in the need to obtain conditions under which the scheme of Eschenauer and Gligor guarantees secure connectivity with high probability in large networks. An interesting feature of this work lies in the following fact: Although random key graphs are not equivalent to the classical Erdős-Rényi graphs [3], it is possible to transfer well-known zero-one laws for connectivity in Erdős-Rényi graphs to random key graphs by asymptotically matching their edge probabilities. This approach, which was initiated by Eschenauer and Gligor in their original analysis [4], has now been validated rigorously; see the papers [1,2,12,15,16] for recent developments. Furthermore, Rybarczyk [12] has shown that this transfer from Erdős-Rényi graphs also works for a number of issues related to the giant component and its diameter.
In view of these successes, it is natural to wonder whether the transfer technique can be applied to other graph properties. In particular, in the literature on random graphs there is a long standing interest [3,8,9,11,13] in the containment of certain (small) subgraphs, the simplest one being the triangle. This last case has some practical relevance since the number of triangles in a graph is closely related to its clustering properties [18]. With this in mind, we study the zero-one law for the existence of triangles in random key graphs and identify the corresponding critical scaling.
From these results we easily conclude that in the many node regime, the expected number of triangles in random key graphs is always at least as large as the corresponding quantity in asymptotically matched Erdős-Rényi graphs. For the parameter range that is of practical relevance in the context of WSNs, this expected number of triangles can be orders of magnitude larger in random key graphs than in Erdős-Rényi graphs, a fact also observed earlier via simulations in [2]. As a result, transferring results from Erdős-Rényi graphs by matching their edge probabilities is not a valid approach in general, and can be quite misleading in the context of WSNs.
The zero-one laws obtained here were announced in the conference paper [17]. The results are established by making use of the method of first and second moments to the number of triangles in the graph. As the discussion amply shows, the technical details, especially for the one-law, are quite involved, and an outline of the proofs can be found in [17]. In line with developments currently available for other classes of graphs, e.g., Erdős-Rényi graphs [8,Chap. 3] and geometric random graphs [11,Chap. 3], it would be interesting to consider the containment problem for small subgraphs other than triangles other than triangle in the context of random key graphs. Given the difficulties encountered in the case of This is likely to be a challenging problem given the difficulties encountered in the simple case of triangles.
The paper is organized as follows: In Section 2 we formally introduce the class of random key graphs while in Section 3 we present the main results of the paper given as Theorem 3.1 and Theorem 3.2. Section 4 compares these results with the corresponding zero-one law in Erdős-Rényi graphs. The zero-one laws are established by an application of the method of first and second moments, respectively [8, p. 55]. To that end, in Section 5, we compute the expected value of the number of triangles in random key graphs. Asymptotic results to be used in the proofs of several results are then collected in Section 6 for easy reference. In Section 7.1, we give a proof of the zero-law (Theorem 3.1) while an outline for the proof of the one-law (Theorem 3.2) is provided in Section 7.2. The final sections of the paper, namely Sections 8 through 12, are devoted to completing the various steps of the proof of Theorem 3.2. Additional technical derivations are given in Appendices A, B and C. A word on the notation and conventions in use: All limiting statements, including asymptotic equivalences, are understood with n going to infinity. The random variables (rvs) under consideration are all defined on the same probability triple (Ω, F, P). Probabilistic statements are made with respect to this probability measure P, and we denote the corresponding expectation operator by E. The indicator function of an event E is denoted by 1 [E]. For any discrete set S we write |S| for its cardinality.

Random key graphs
The model is parametrized by the number n of nodes, the size P of the key pool and the size K of each key ring with K ≤ P . We often group the integers P and K into the ordered pair θ ≡ (K, P ) in order to simplify the notation. Now, for each node i = 1, . . . , n, let K i (θ) denote the random set of K distinct keys assigned to node i and let P be the set of all keys. The rvs K 1 (θ), . . . , K n (θ) are assumed to be i.i.d. rvs, each of which is uniformly distributed with for any subset S of P which contains exactly K elements. This corresponds to selecting keys randomly and without replacement from the key pool. Distinct nodes i, j = 1, . . . , n are said to be adjacent if they share at least one key in their key rings, namely in which case an undirected link is assigned between nodes i and j. The resulting random graph defines the random key graph on the vertex set {1, . . . , n}, hereafter denoted K(n; θ). For distinct i, j = 1, . . . , n, it is easy to check that whence the probability of edge occurrence between any two nodes is equal to 1 − q(θ). The expression given in (4) is a simple consequence of the often used fact that The number of (unlabelled) triangles in K(n; θ) is simply given by where (ijk) denotes summation over all distinct triples ijk with 1 ≤ i < j < k ≤ n. The event T (n, θ) that there exists at least one triangle in K(n; θ) is then characterized by The main result of the paper is a zero-one law for the existence of triangles in random key graphs. To state these results we find it convenient to make use of the quantity with positive integers K and P such that K ≤ P . For simplicity of exposition we refer to any pair of functions P, K : N 0 → N 0 as a scaling provided the natural conditions K n ≤ P n , n = 2, 3, . . .
are satisfied. The zero-law is given first.
The one-law given next assumes a more involved form.
Theorem 3.2 For any scaling P, K : N 0 → N 0 for which the limit lim n→∞ q(θ n ) = q ⋆ exists, we have the one-law Theorem 3.1 and Theorem 3.2 will be established by the method of first and second moments, respectively [8, p. 55], applied to the count variables defined at (6). To facilitate comparison with Erdős-Rényi graphs, we combine Theorem 3.1 and Theorem 3.2 into a symmetric, but somewhat weaker, statement. Theorem 3.3 For any scaling P, K : N 0 → N 0 for which lim n→∞ q(θ n ) = 1, we have

Comparing with Erdős-Rényi graphs
In this section we compare Theorem 3.3 with its analog for Erdős-Rényi graphs. First some notation: For each p in [0, 1] and n = 2, 3, . . ., let G(n; p) denote the Erdős-Rényi graph on the vertex set {1, . . . , n} with edge probability p. In analogy with (6) and (7) let T n (p) denote the number of (unlabelled) triangles in G(n; p), and define T (n, p) as the event that there exists at least one triangle in G(n; p), i.e., T (n, p) = [T n (p) > 0]. we also refer to any mapping p : N 0 → [0, 1] as a scaling for Erdős-Rényi graphs.
The following zero-one law for connectivity in Erdős-Rényi graphs is well known [3].
As this result is also established by the method of first and second moments, its form is easily understood once we note that for all n = 3, 4, . . .. As mentioned earlier, random key graphs are not equivalent to Erdős-Renyi graphs even when their edge probabilities are matched, i.e., G(n; p) = st K(n; θ) with p = 1 − q(θ); see [17] for a discussion of similarities. However, in order to meaningfully compare the zero-one law of Theorem 4.1 with that contained in Theorem 3.3, we say that the scaling p : N 0 → [0, 1] (for Erdős-Rényi graphs) is asymptotically matched to the scaling P, K : N 0 → N 0 (for random key graphs) if This is equivalent to requiring that the expected average degrees are asymptotically equivalent. Under the natural condition lim n→∞ q(θ n ) = 1, the matching condition (18) amounts to by virtue of Lemma 6.1. The definitions readily yield under (19). By Proposition 6.2, this last statement is equivalent to as we make use of the expressions (17) and (30). In other words, for large n the expected number of triangles in random key graphs is always at least as large as the corresponding quantity in asymptotically matched Erdős-Rényi graphs.
In the context of WSNs, it is natural to select the parameters K n and P n of the scheme of Eschenauer and Gligor such that the induced random key graph is connected. However, there is a tradeoff between connectivity and security [2]. This requires that K 2 n Pn be kept as close as possible to the critical scaling log n n for connectivity; see the papers [1,2,12,15,16]. In the desired near boundary regime, this amounts to with c > 1 but close to one, and from (21) we see that The expected number of triangles in random key graphs is then of the same order as the corresponding quantity in asymptotically matched Erdős-Rényi graphs with E [T n (θ n )] ∼ E [T n (p n )] ∼ c 3 6 (log n) 3 . This conclusion holds regardless of the value of c in (22).
However, given the limited memory and computational power of the sensor nodes, the key ring sizes at (23) are not practical. In addition, they will lead to high node degrees and this in turn will decrease network resiliency against node capture attacks. Indeed, in [2,Thm. 5.3] it was proposed that security in WSNs be ensured by selecting K n and P n such that Kn Pn ∼ 1 n , a requirement which then leads to under (22), and (21) implies Hence, for realistic WSN scenarios the expected number of triangles in the induced random key graphs can be orders of magnitude larger than in Erdős-Rényi graphs. This provides a clear example where transferring known results for Erdős-Rényi graphs to random key graphs by asymptotically matching their edge probabilities can be misleading.

Computing the first moment
With positive integers K and P such that K ≤ P , define where we have set Direct inspection shows that Lemma 5.1 For positive integers K and P such that K ≤ P , we have To help deriving (30) we introduce the events and The event A(θ) captures the existence of edges between node 1 and the pair of nodes 2 and 3, respectively, in K(n; θ), while B(θ) is the event where the nodes 1, 2 and 3 form a triangle in K(n; θ).

Lemma 5.2
The probability of the event A(θ) is given by In the proof of Lemma 5.2 (as well as in other proofs) we omit the explicit dependence on θ when no confusion arises from doing so.
Proof. Under the enforced independence assumptions we note that as we make use of (5) with |S|=K P [K 1 = S] = 1.
In many of the forthcoming calculations we make repeated use of the fact that for any pair of events, say E and F , we have In particular, we can now conclude from Lemma 5.2 that and These facts will now be used in computing the probability of B(θ).
Proof. Repeated use of (35) yields as we recall (33), (36) and (37). By independence we get by invoking (5) (since |S ∪ T | = 2K under the constraints |S| = |T | = K and S ∩ T = ∅). Thus, and the desired result follows upon noting the relation The proof of Lemma 5.1 is now straightforward: Fix n = 3, 4, . . .. Exchangeability yields and the desired conclusion follows as we make use of Lemma 5.3.

Some useful asymptotics
In this section we collect a number of asymptotic results that prove useful in establishing some of the results derived in this paper. The first result was already obtained in [16]. if and only if and under either condition the asymptotic equivalence holds.
so that for any c > 0, we have for all n sufficiently large in N 0 (dependent on c).
The following asymptotic equivalence will be crucial to stating the results in a more explicit form.
Proposition 6.2 For any scaling P, K : N 0 → N 0 satisfying (42)-(43), we have the asymptotic equivalence Proof. From (26), we get Under the enforced assumptions Lemma 6.1 already implies It is now plain that the equivalence (48) will hold if we show that This key technical fact is established in Appendix A.
The final result of this section also relies on Lemma 6.1, and will prove useful in establishing the one-law.
The remainder of the paper is devoted to establishing Proposition 7.1. As will soon become apparent this is a bit quite more involved than expected.

Computing the second moment
A natural step towards establishing Proposition 7.1 consists in computing the second moment of the count variables (6).
Proposition 8.1 For positive integers K and P such that K ≤ P , we have where we have set A careful inspection of the definition (B.10) given for the quantities (64) yields the probabilistic interpretation (65) for each k = 0, 1, . . . , K.
Proof. Consider positive integers K and P such that K ≤ P and fix n = 3, 4, . . .. By exchangeability and by the binary nature of the rvs involved we readily conclude that Under the enforced independence assumptions the rvs χ n,123 (θ) and χ n,456 (θ) are independent and identically distributed. As a result, as we make use of the relation (30).
On the other hand, we readily check that the indicator rvs χ n,123 (θ) and χ n,145 (θ) are independent and identically distributed conditionally on K 1 (θ) with A similar statement applies to χ n,145 (θ), and the rvs χ n,123 (θ) and χ n,145 (θ) are therefore (unconditionally) independent and identically distributed so that As before this last observation yields In preparation of the proof of Proposition 7.1 we note that Proposition 8.1 readily implies for all n = 2, 3, . . . as we make use of (41). It is plain that the convergence (61) will hold if we show that In order to establish (71) under the assumptions of Proposition 7.1 we proceed as follows: Recall from Lemma 5.1 that and from (63) observe that for all n = 3, 4, . . .. Let n go to infinity in (73). Using (53) (once with a = 5 and b = 2, then with a = 2 and b = 1), we get and lim n→∞ 2 The convergence under the condition (13).
The proof of Proposition 9.1 will proceed in several steps which are presented in the next three sections.

The first reduction step
We start with an easy bound.
Lemma 10.1 With positive integers K and P such that 2K ≤ P , we have Proof. Specializing (65) with k = 1 we get and the conclusion is immediate as we identify Lemma 10.2 With positive integers K and P such that 3K ≤ P , the monotonicity property holds.
Proof. Fix k = 0, . . . , K − 1. From the expression (64) we note that and by considering each factor in this last expression we readily conclude that the ratio c k (θ) decreases monotonically with k.
for all n sufficiently large in N 0 .
Proof. Pick a scaling P, K : N 0 → N 0 satisfying (42)-(43) so that (70) eventually holds. On that range replace θ by θ n in (80) with k = 1 according to this scaling, yielding The inequality for all n sufficiently large in N 0 .
We are now in a position to take the first step towards the proof of Proposition 9.1.
for all n sufficiently large in N 0 . Letting n go to infinity in this last inequality we readily obtain (84) as an immediate consequence of Proposition 6.3, to wit (53) (with a = 5 and b = 2).

The second reduction step
It is now plain from Proposition 10.5 that the proof of Proposition 9.1 will be completed if we show the following fact.
To construct a proof of Proposition 11.1 we proceed as follows: Fix positive integers K and P such that 3K ≤ P . By direct substitution we get where we have set In this new notation Proposition 11.1 can be given a simpler, yet equivalent, form.
To establish this convergence, fix n = 2, 3, . . . and note that The bounds are straightforward, while simple calculus followed by a crude bounding rgument yields With the help of (94) we now conclude that Letting n go to infinity in this last expression yields the conclusion by virtue of (43), and this readily implies (92) via (93).
The following bound, which is established in Section 12, proves crucial for proving the convergence (90) under the assumptions of Proposition 11.1. for all n sufficiently large in N 0 .
While Lemma 11.3 is established in Section 12, the proof of Proposition 11.1 can now be completed: Pick a scaling P, K : N 0 → N 0 satisfying (42)-(43) and assume that (13) holds. By Lemma 11.3 we get for all n sufficiently large in N 0 . Invoking Proposition 6.2 we then conclude that The validity of (90) follows upon letting n go to infinity in (98) and using (99) together with the consequence (51) of (13) discussed in the proof of Proposition 6.3. The proof of Proposition 11.1 is completed with the help of Proposition 11.2.
12 Towards Lemma 11.3 We are left with proving the key Lemma 11.3. To do so we will need to exploit the structure of F (θ): Thus, fix positive integers K and P such that 3K ≤ P , and return to (88). For each k = 0, 1, . . . , 4, easy algebra shows that Next, it is plain that Reporting these facts into (88) we readily conclude By direct inspection, using (C.1) and (C.3) in Appendix C, we check that F (θ) can be written as a polynomial in P (of order 4K), namely where the coefficients are integers which depend on θ only through K. The first six coefficients can be evaluated explicitly.
Lemma 12.1 With positive integers K and P such that 3K ≤ P , we have a 0 (K) = a 1 (K) = a 2 (K) = 0 (105) and a 3 (K) = K 4 (106) whereas and a 5 (K) = − 1 120 K 10 + 1 6 K 9 + 199 12 The fact that (108) defines a polynomial expression in K with rational coefficients does not contradict the integer nature of a 5 (K). In what follows we shall find it convenient to write The proof of Lemma 12.1 is tedious and is given in Appendix C. For the remaining coefficients, we rely on the following bounds which are also derived in Appendix C.
Lemma 12.2 With positive integers K and P such that 3K ≤ P , we have for all n large enough to ensure 12K 2 n < P n , say n ≥ n ⋆ 1 for some finite integer n ⋆ 1 ; this is a simple consequence of condition (42)-(43). On that range, going back to (112), we find where L n := a 4 (K n )P n + a 5 (K n ) + 2(12) 6 K 10 n · Therefore, (112) will hold for all n sufficiently large in N 0 provided That L = −∞ can be seen as follows: We begin with the bound for all n = 1, 2, . . .. Next, condition (42)-(43) implies whence there exists some finite integer n ⋆ 2 such that Now, set n ⋆ = max (n ⋆ 1 , n ⋆ 2 ), and recall the definition (109). On the range n ≥ n ⋆ , both inequalities (114) and (118) hold, and we obtain a 4 (K n )P n + a 5 (K n ) + 2(12) 6 K 10 n · upon making use of (116). To conclude, set and note that L ⋆ is necessarily an element of [−∞, ∞), i.e., it is never the case that L ⋆ = ∞. This follows easily from the fact that the mapping R + → R + : x → a ⋆ 5 (x) is a polynomial of degree 10 whose leading coefficient (− 1 240 ) is negative. As we recall (46) under (42)-(43), it is now plain from (119) that L = −∞ by standard properties of the lim sup operation.
Careful inspection of the proof of Proposition 11.1 given at the end of Section 11 shows that the inequality (97) of Lemma 11.3 could be replaced without prejudice by the following weaker statement: For any scaling P, K : N 0 → N 0 satisfying (42)-(43), there exists some positive constant C such that for all n sufficiently large in N 0 . Now, from only the knowledge of the first four coefficients in Lemma 12.1 we can already conclude that for each K = 1, 2, . . ., so that for each ε > 0 there exists a finite integer P ⋆ (ε, K) such that Unfortunately, the threshold P ⋆ (ε, K) is not known to be uniform with respect to K, and the approach does not necessarily imply (121) (with C = 1 + ε) unless the sequence K : N 0 → N 0 is bounded. This technical difficulty is at the root of why more information on the coefficients a 4 (K) and a 5 (K) (as provided in Lemma 12.1) is needed, and paves the way for the subsequent arguments behind Lemma 11.3.

A Establishing (49)
With positive integers K, P such that 3K ≤ P , we note that and elementary bounding arguments yield Pick a scaling P, K : N 0 → N 0 satisfying the equivalent conditions (42)-(43) and consider n sufficiently large in N 0 so that (47) holds with c = 3. On that range, as we replace θ by θ n in the last chain of inequalities according to this scaling, we get A standard sandwich argument will imply the desired equivalence (49) if we show that To establish (A.2) we proceed as follows: Fix c = 1, 2 and on the appropriate range we note that

B Evaluating (63)-(64)
For notational convenience, we define for distinct i, j = 1, 2, . . . n. Moreover, for any non-empty subset S of {1, . . . , P }, we write In what follows we make repeated use of the decomposition (35). Beginning with the observation we shall compute each term in turn.
To compute the second term in (B.1) we condition on the sets K 1 and K 2 such that K 1 ∩ K 2 = ∅. Thus, as we note from (5) We now turn to the first term in (B.1). Again, upon making repeated use of (35) we find as we note that P [K c 23 , K 14 , K 24 ] = P [K c 13 , K 14 , K 24 ]. Next, we find upon using (36) in (B.4).
In a similar manner, we obtain where (B.6) follows from (37). We also get Finally consider the term P [K c 13 , K c 23 , K c 14 , K c 24 ]: By conditioning on the cardinality of the intersection K 1 ∩ K 2 , we obtain where for each k = 0, 1, . . . , K, we have set where we have used the notation (64).
As we seek to simplify this last expression, we note that Next, we observe that (B.14) Subtracting (B.14) from (B.13) gives Reporting the outcome of this last calculation into (B.12) we then get 16) and the conclusion (63) follows as we make use of the expression (26) for β(θ).
On the other hand, the expression is a product of 4K factors with leading term P 4K , and we can write it as a polynomial in P , namely for some integer coefficients β 0 (K), . . . , β 4K (K) with β 4K (K) = 1.

Direct substitution followed by elementary manipulations gives
and it is then plain that Finally, upon comparing with (104) we get the relations for all ℓ = 0, . . . , 4K.

C.1 A proof of Lemma 12.2
We begin with some simple observations: For some positive integer M , consider the mapping R : R → R given by with scalars r 1 , . . . , r M , not necessarily distinct. Obviously, R : R → R is a polynomial (in the variable x) of degree M with all its roots located at Now we turn to the proof of Lemma 12.2: Pick positive integers K and P such that K ≥ 4 and 3K ≤ P , and fix ℓ = 4, 5, . . . , 4K -We shall give a proof only in that range for simplicity of exposition; after all the desired bounds are already implied by the exact expression for a 0 (K), . . . , a 3 (K) given as part of Lemma 12.1. On the range ℓ = 4, . . . , 4K, the bound (C.5) already implies For each k = 0, 1, . . . , 4, we note that We then apply the bound (C.8)-(C.9) to the polynomal b K,k : From (C.1) we get the values M = 4K − k and r ⋆ = 3K − (k + 1), Also, we note that β k,4K−ℓ (K) is the coefficient of P 4K−ℓ (thus of P 4K−k−(ℓ−k) ) in the polynomial b K,k (P ) of order 4K − k. Therefore, applying the bound (C.8)-(C.9) we find In a similar way, we apply the bound (C.8)-(C.9) to the polynomial b K . This time, (C.3) gives M = 4K and r ⋆ = 2K − 1, and we conclude that Collecting the bounds (C.11), (C.12) and (C.13) we see from (C.10) that It is a simple matter to check that C ℓ ≤ 2.

C.2 A proof of Lemma 12.1
The basis for the proof can be found in the expression (C.5) for the coefficients a 0 (K), . . . , a 4K (K).