Towards $k$-connectivity in Heterogeneous Sensor Networks under Pairwise Key Predistribution

Mansi Sood; Osman Ya\u{g}an

arxiv: 1907.08049 · v1 · pith:FRHTI7YJnew · submitted 2019-07-18 · 💻 cs.IT · math.CO· math.IT· math.PR

Towards k-connectivity in Heterogeneous Sensor Networks under Pairwise Key Predistribution

Mansi Sood , Osman Ya\u{g}an This is my paper

Pith reviewed 2026-05-24 19:33 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.ITmath.PR

keywords heterogeneous sensor networkspairwise key predistributionminimum node degreezero-one lawinhomogeneous random graphsk-connectivitywireless sensor networks

0 comments

The pith

The paper establishes critical conditions on n, μ, and Kn so that heterogeneous sensor networks under pairwise key predistribution have minimum node degree at least k with high probability as n grows large.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors derive a zero-one law for the minimum node degree in the inhomogeneous random K-out graph that models a heterogeneous pairwise key predistribution scheme. In this scheme, a fraction μ of nodes each pick one partner while the rest each pick Kn partners, all uniformly at random, and each pair receives a unique key. The result identifies the precise scaling of Kn with n under which every node ends up with degree at least k, with probability tending to one. A sympathetic reader cares because this threshold supplies a concrete design rule for choosing how many keys each node type should store to keep the network reliably connected even after some failures. The work is presented as an intermediate step toward a full zero-one law for k-connectivity of the same graph.

Core claim

We establish critical conditions on n, μ, and Kn such that the resulting network has minimum node degree of at least k with high probability in the limit of large network size. Our result constitutes a zero-one law for the minimum node degree of the recently introduced inhomogeneous random K-out graph model. This constitutes a crucial step towards establishing a similar zero-one law for the k-connectivity of the graph.

What carries the argument

The inhomogeneous random K-out graph model, in which type-1 nodes each select exactly one partner and type-2 nodes each select exactly Kn partners uniformly at random, with all selections independent.

If this is right

When the stated scaling holds, every node has at least k neighbors with high probability, so there are no isolated low-degree nodes.
The same threshold conditions are expected to be necessary and sufficient for the stronger property of k-connectivity once that law is proved.
Numerical checks for finite n show that the asymptotic thresholds remain useful for selecting Kn in practical deployments.
Designers can allocate fewer keys to the more numerous or less capable node type while still meeting the minimum-degree target.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The min-degree law supplies a sufficient condition for the network to remain connected after any single node or link failure when k equals 2.
The same modeling approach could be used to study resilience when nodes are captured and their keys are revealed to an adversary.
Extending the two-type heterogeneity to a continuous distribution of node capabilities would test whether the zero-one law survives more general inhomogeneity.

Load-bearing premise

The model assumes every selection of partners is made independently and uniformly at random among all other nodes, and the analysis is performed in the limit as total nodes n tends to infinity.

What would settle it

Generate many independent realizations of the graph for large but finite n, compute the empirical probability that minimum degree is below k, and check whether this probability jumps from near 1 to near 0 exactly when Kn crosses the threshold predicted by the zero-one law.

Figures

Figures reproduced from arXiv: 1907.08049 by Mansi Sood, Osman Ya\u{g}an.

**Figure 1.** Figure 1: A WSN comprising 5 nodes secured by the heterogeneous random pairwise key predistribution scheme. Each type-1 (resp. type2) node randomly picks 1 (resp. K = 2) nodes and a unique pairwise key is given to node pairs per selection; in this example, node A is type-2 and others are type-1. Two nodes can communicate if they have at least one pairwise key in common. This induces a graph with edges corresponding… view at source ↗

**Figure 3.** Figure 3: Empirical probability (computed by averaging 1000 independent experiments for each data point) of k-connectivity and minimum node degree being no less than k as a function of Kn for n = 500, µ = 0.5 and k = 2, 3, 4. IV. SKETCH OF THE PROOF OF THEOREM 1 In this section, we provide a brief outline for the proof of Theorem 1; all details can be found in the Appendix. Our proof employs the method of first and… view at source ↗

**Figure 4.** Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

**Figure 5.** Figure 5: From a pool of n − c nodes, α − r nodes draw an edge to node v1 but not node v2, β − r nodes draw an outgoing edge to node v2 but not node v1, r nodes draw an outgoing edge to both node v1 and node v2 and the remaining n − c − α − β + r nodes draw an edge to neither node v1 nor node v2. Recall that our goal is to show that lim sup n→∞ P[deg(v1) = deg(v2) = k − 1|t1 = t2 = 1] (P[deg(v1) = k − 1 | t1 = 1])2 … view at source ↗

read the original abstract

We study the secure and reliable connectivity of wireless sensor networks under the heterogeneous pairwise key predistribution scheme. This scheme was recently introduced as an extension of the random pairwise key predistribution scheme of Chan et al. to accommodate networks where the constituent sensors have different capabilities or requirements for security and connectivity. For simplicity, we consider a heterogeneous network where each of the $n$ sensors is classified as type-1 (respectively, type-2) with probability $\mu$ (respectively, $1-\mu)$ where $0<\mu<1$. Each type-1 (respectively, type-2) node selects 1 (respectively, $K_n$) other nodes uniformly at random to be paired with; according to the pairwise scheme each pair is then assigned a unique pairwise key so that they can securely communicate with each other. We establish critical conditions on $n, \mu$, and $K_n$ such that the resulting network has minimum node degree of at least $k$ with high probability in the limit of large network size. Our result constitutes a zero-one law for the minimum node degree of the recently introduced inhomogeneous random K-out graph model. This constitutes a crucial step towards establishing a similar zero-one law for the $k$-connectivity of the graph; i.e., for the property that the network remains connected despite the failure of any $k-1$ nodes or links. We present numerical results that indicate the usefulness of our results in selecting the parameters of the scheme in practical settings with finite number of sensors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper establishes a zero-one law for the minimum node degree in the inhomogeneous random K-out graph with heterogeneous node types.

read the letter

The main thing here is a zero-one law for minimum node degree at least k in the inhomogeneous random K-out graph. The authors show critical conditions on the parameters so that this holds with high probability as the network size grows. What they do is extend the random pairwise key predistribution to heterogeneous sensors, where a fraction mu are type-1 with out-degree 1 and the rest type-2 with out-degree Kn. The graph is the undirected version from these random pairings. They derive the threshold for Kn that makes the min degree k or more whp. This is new because prior zero-one laws were for the homogeneous case. They also run some simulations to illustrate how the thresholds perform for practical finite sizes. The setup is clean. The selections are independent and uniform, the property is standard, and they don't claim more than the min-degree result. The paper is upfront that this is a step toward k-connectivity, which is the property that matters more for reliability against failures. The soft spots are limited. The analysis is asymptotic, so for real deployments the numerics are key, and those are only a few examples. The model uses exactly two types with fixed degrees, which is a reasonable starting point but not the most general heterogeneity. No obvious gaps in the claim from the description. This paper is for people in the intersection of random graphs and wireless sensor network security. A reader interested in threshold phenomena for connectivity in key predistribution schemes will get a concrete new result. It is worth sending to peer review so that experts can check the proof details.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes a zero-one law for the minimum node degree being at least k (with high probability as n→∞) in the inhomogeneous random K-out graph model induced by a heterogeneous pairwise key predistribution scheme. Nodes are of two types with probabilities μ and 1-μ; type-1 nodes select exactly one partner and type-2 nodes select exactly K_n partners uniformly at random, with the underlying undirected graph formed by the resulting pairs. Critical conditions on n, μ, and the scaling of K_n are derived that guarantee the min-degree property.

Significance. If the derivation holds, the result supplies a foundational zero-one law for min-degree in this inhomogeneous model and serves as an explicit preparatory step toward a corresponding k-connectivity law. The numerical illustrations further indicate direct utility for parameter selection in finite heterogeneous sensor networks under the pairwise scheme.

minor comments (2)

[§1] §1 (Introduction): the positioning of the min-degree result as preparatory for k-connectivity is clear, but the precise scaling regime assumed for K_n (constant vs. slowly growing) should be stated explicitly when the model is first defined.
The abstract states that numerical results indicate usefulness for finite n; ensure that the plotted curves are accompanied by the exact (n, μ, K_n, k) values used so that readers can reproduce the comparison with the asymptotic thresholds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work establishing a zero-one law for the minimum node degree in the inhomogeneous random K-out graph arising from heterogeneous pairwise key predistribution. The recommendation for minor revision is noted. No specific major comments appear under the 'MAJOR COMMENTS' heading, so we have no individual points to address.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines an inhomogeneous random K-out graph model explicitly via independent uniform selections with fixed out-degrees 1 and Kn, then derives an asymptotic zero-one law for minimum node degree at least k (whp as n→∞) under scaling conditions on n, μ, and Kn. This is a standard probabilistic analysis on an independently specified random graph; no parameters are fitted to data and then relabeled as predictions, no self-definitional loops appear in the model or result, and the abstract positions the min-degree law as preparatory for k-connectivity without invoking load-bearing self-citations or imported uniqueness theorems. The derivation chain remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the explicit definition of the inhomogeneous random K-out graph together with standard tools of asymptotic random-graph analysis; no free parameters are fitted to data and no new entities are postulated.

axioms (2)

domain assumption Each type-1 node selects exactly one partner and each type-2 node selects exactly Kn partners uniformly at random, with selections independent across nodes.
This is the model definition stated in the abstract and is required for the graph to be well-defined.
standard math Standard limit theorems and concentration inequalities for random graphs apply in the n → ∞ regime.
Invoked implicitly to obtain the zero-one law.

pith-pipeline@v0.9.0 · 5816 in / 1266 out tokens · 66695 ms · 2026-05-24T19:33:41.912846+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1: … ⟨Kn⟩ = log n + (k−2) log log n + γn … lim P[min degree ≥ k] = 1 (γn→+∞) or 0 (γn→−∞)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

inhomogeneous random K-out graph H(n;μ,Kn) … type-1 selects 1, type-2 selects Kn

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

A survey on sensor networks,

I. Akyildiz, W. Su, Y . Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine , vol. 40, no. 8, pp. 102–114, Aug 2002

work page 2002
[2]

Wireless sensor network survey,

J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer networks , vol. 52, no. 12, pp. 2292–2330, 2008

work page 2008
[3]

Security in wireless sensor networks,

A. Perrig, J. Stankovic, and D. Wagner, “Security in wireless sensor networks,” Communications of the ACM , vol. 47, no. 6, pp. 53–57, 2004

work page 2004
[4]

A key-management scheme for distributed sensor networks,

L. Eschenauer and V . D. Gligor, “A key-management scheme for distributed sensor networks,” in Proc. of ACM CCS 2002 , pp. 41–47

work page 2002
[5]

A survey of security issues in wireless sensor networks,

Y . Wang, G. Attebury, and B. Ramamurthy, “A survey of security issues in wireless sensor networks,” IEEE Communications Surveys Tutorials , vol. 8, no. 2, pp. 2–23, Second 2006

work page 2006
[6]

A survey of key management schemes in wireless sensor networks,

Y . Xiao and V . K. Rayi and B. Sun and X. Du and F. Hu and M. Galloway, “A survey of key management schemes in wireless sensor networks,” Computer Communications , vol. 30, pp. 2314 – 2341, 2007, special issue on security on wireless ad hoc and sensor networks. [Online]. Available: http://www.sciencedirect.com/science/ article/pii/S0140366407001752

work page 2007
[7]

Random key predistribution schemes for sensor networks,

H. Chan, A. Perrig, and D. Song, “Random key predistribution schemes for sensor networks,” in Proc. of IEEE S&P 2003

work page 2003
[8]

Connectivity of wireless sensor networks secured by the heterogeneous random pairwise key predistribution scheme,

R. Eletreby and O. Ya ˘gan, “Connectivity of wireless sensor networks secured by the heterogeneous random pairwise key predistribution scheme,” in Proc. of IEEE CDC 2018 , Dec 2018

work page 2018
[9]

Bollob ´as, Random graphs

B. Bollob ´as, Random graphs . Cambridge university press, 2001, vol. 73

work page 2001
[10]

On the connectivity of randomm- orientable graphs and digraphs,

T. I. Fenner and A. M. Frieze, “On the connectivity of randomm- orientable graphs and digraphs,” Combinatorica, vol. 2, no. 4, pp. 347– 359, Dec 1982

work page 1982
[11]

On the connectivity of sensor networks under random pairwise key predistribution,

O. Ya ˘gan and A. M. Makowski, “On the connectivity of sensor networks under random pairwise key predistribution,” IEEE Transactions on Information Theory , vol. 59, no. 9, pp. 5754–5762, Sept 2013

work page 2013
[12]

Toward k-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links,

F. Yavuz, J. Zhao, O. Ya ˘gan, and V . Gligor, “Toward k-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 11, pp. 6251–6271, 2015

work page 2015
[13]

A framework for a distributed key management scheme in heterogeneous wireless sensor networks,

K. Lu, Y . Qian, M. Guizani, and H. Chen, “A framework for a distributed key management scheme in heterogeneous wireless sensor networks,” IEEE Transactions on Wireless Communications , vol. 7, no. 2, pp. 639– 647, February 2008

work page 2008
[14]

Heterogeneous wireless sensor network deployment and topology control based on irregular sensor model,

C.-H. Wu and Y .-C. Chung, “Heterogeneous wireless sensor network deployment and topology control based on irregular sensor model,” in Advances in Grid and Pervasive Computing , 2007, pp. 78–88

work page 2007
[15]

Exploiting heterogeneity in sensor networks,

M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y . Liu, and S. Singh, “Exploiting heterogeneity in sensor networks,” in Proc. of IEEE INFOCOM 2005

work page 2005
[16]

On the strength of connectedness of random graphs,

P. Erd ˝os and A. R ´enyi, “On the strength of connectedness of random graphs,” Acta Math. Acad. Sci. Hungar , pp. 261–267, 1961

work page 1961
[17]

Dandelion++: Lightweight cryptocurrency networking with formal anonymity guarantees,

G. Fanti, S. B. Venkatakrishnan, S. Bakshi, B. Denby, S. Bhargava, A. Miller, and P. Viswanath, “Dandelion++: Lightweight cryptocurrency networking with formal anonymity guarantees,” Proc. ACM Meas. Anal. Comput. Syst. , vol. 2, no. 2, pp. 29:1–29:35, Jun. 2018

work page 2018
[18]

The bitcoin lightning network: Scalable off-chain instant payments,

J. Poon and T. Dryja, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016

work page 2016
[19]

k-connectivity in random key graphs with unreliable links,

J. Zhao, O. Yaan, and V . Gligor, “ k-connectivity in random key graphs with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 7, pp. 3810–3836, July 2015

work page 2015
[20]

M. D. Penrose, Random Geometric Graphs . Oxford University Press, Jul. 2003

work page 2003
[21]

Random graphs. 2000,

S. Janson, T. Łuczak, and A. Ruci ´nski, “Random graphs. 2000,” Wiley– Intersci. Ser . Discrete Math. Optim , 2000

work page 2000
[22]

Zero–one laws for connectivity in random key graphs,

O. Ya ˘gan and 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

work page 2012
[23]

Zero-one laws for connectivity in inhomogeneous random key graphs,

O. Ya ˘gan, “Zero-one laws for connectivity in inhomogeneous random key graphs,” IEEE Transactions on Information Theory , vol. 62, no. 8, pp. 4559–4574, Aug 2016

work page 2016
[24]

k-connectivity of inhomogeneous random key graphs with unreliable links,

R. Eletreby and O. Ya ˘gan, “k-connectivity of inhomogeneous random key graphs with unreliable links,” IEEE Transactions on Information Theory, pp. 1–1, 2019

work page 2019
[25]

k-connectivity in random key graphs with unreliable links,

J. Zhao, O. Ya ˘gan, and V . Gligor, “k-connectivity in random key graphs with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 7, pp. 3810–3836, July 2015. Appendix In this Section, we present a detailed proof of Theorem 1. We remind the readers that H(n;µ,Kn) is the inhomogeneous random K-out graph induced by the heterogeneous p...

work page 2015
[26]

In other words, we let Zd(n;µ,Kn) = ∑n i=1 1{deg(vi) = d}, where deg(vi) is the degree of node vi

Establishing the one-law in Theorem 1: Let Zd(n;µ,Kn) denote the number of nodes in H(n;µ,Kn) with degree d where d = 1,...,k − 1. In other words, we let Zd(n;µ,Kn) = ∑n i=1 1{deg(vi) = d}, where deg(vi) is the degree of node vi. Since each node makes at least one selection, no node can have degree zero. To establish the one-law, we use the method of ﬁrst...

work page
[27]

This technique is referred to as the method of ﬁrst moment

Establishing the zero-law in Theorem 1: We saw above how the one-law can be proved as a consequence of the Markov inequality applied to an integer-valued random variable counting the number of nodes with degree less than k. This technique is referred to as the method of ﬁrst moment. Next, we describe an outline for the proof of zero-law using the method o...

work page
[28]

Noting that Ψ(x) is non-negative, (A.16) gives the bound that for x∈ [0, 1), we have 1−x≤e−x

For any x∈ [0, 1), it can be veriﬁed that log(1−x) =− ∫ x 0 1 1−tdt =−x− Ψ(x), (A.16) where Ψ(x) := ∫ x 0 t 1−tdt, 0≤x< 1. Noting that Ψ(x) is non-negative, (A.16) gives the bound that for x∈ [0, 1), we have 1−x≤e−x. (A.17) Furthermore, using L’Hospital’s rule we get lim x→0 Ψ(x) x2 = 1

work page
[29]

(null)">(null)</latexit><latexit sha1_base64=

If x and y are functions of n such that x = o(1) and x2y = o(1), then (1−x)y =e−xy(1 + o(1)). (A.19) For a proof of this, see [25, Fact 3]. B. P ROOF OF PROPOSITION A.3 ( ESTABLISHING ONE -LAW IN THEOREM 1) Here, we consider the case where lim n→∞ γn = +∞. Recall that Zd(n;µ,Kn) denotes the number of nodes with degree d where d∈{ 1, 2...,k− 1}. We have E ...

work page

[1] [1]

A survey on sensor networks,

I. Akyildiz, W. Su, Y . Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine , vol. 40, no. 8, pp. 102–114, Aug 2002

work page 2002

[2] [2]

Wireless sensor network survey,

J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer networks , vol. 52, no. 12, pp. 2292–2330, 2008

work page 2008

[3] [3]

Security in wireless sensor networks,

A. Perrig, J. Stankovic, and D. Wagner, “Security in wireless sensor networks,” Communications of the ACM , vol. 47, no. 6, pp. 53–57, 2004

work page 2004

[4] [4]

A key-management scheme for distributed sensor networks,

L. Eschenauer and V . D. Gligor, “A key-management scheme for distributed sensor networks,” in Proc. of ACM CCS 2002 , pp. 41–47

work page 2002

[5] [5]

A survey of security issues in wireless sensor networks,

Y . Wang, G. Attebury, and B. Ramamurthy, “A survey of security issues in wireless sensor networks,” IEEE Communications Surveys Tutorials , vol. 8, no. 2, pp. 2–23, Second 2006

work page 2006

[6] [6]

A survey of key management schemes in wireless sensor networks,

Y . Xiao and V . K. Rayi and B. Sun and X. Du and F. Hu and M. Galloway, “A survey of key management schemes in wireless sensor networks,” Computer Communications , vol. 30, pp. 2314 – 2341, 2007, special issue on security on wireless ad hoc and sensor networks. [Online]. Available: http://www.sciencedirect.com/science/ article/pii/S0140366407001752

work page 2007

[7] [7]

Random key predistribution schemes for sensor networks,

H. Chan, A. Perrig, and D. Song, “Random key predistribution schemes for sensor networks,” in Proc. of IEEE S&P 2003

work page 2003

[8] [8]

Connectivity of wireless sensor networks secured by the heterogeneous random pairwise key predistribution scheme,

R. Eletreby and O. Ya ˘gan, “Connectivity of wireless sensor networks secured by the heterogeneous random pairwise key predistribution scheme,” in Proc. of IEEE CDC 2018 , Dec 2018

work page 2018

[9] [9]

Bollob ´as, Random graphs

B. Bollob ´as, Random graphs . Cambridge university press, 2001, vol. 73

work page 2001

[10] [10]

On the connectivity of randomm- orientable graphs and digraphs,

T. I. Fenner and A. M. Frieze, “On the connectivity of randomm- orientable graphs and digraphs,” Combinatorica, vol. 2, no. 4, pp. 347– 359, Dec 1982

work page 1982

[11] [11]

On the connectivity of sensor networks under random pairwise key predistribution,

O. Ya ˘gan and A. M. Makowski, “On the connectivity of sensor networks under random pairwise key predistribution,” IEEE Transactions on Information Theory , vol. 59, no. 9, pp. 5754–5762, Sept 2013

work page 2013

[12] [12]

Toward k-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links,

F. Yavuz, J. Zhao, O. Ya ˘gan, and V . Gligor, “Toward k-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 11, pp. 6251–6271, 2015

work page 2015

[13] [13]

A framework for a distributed key management scheme in heterogeneous wireless sensor networks,

K. Lu, Y . Qian, M. Guizani, and H. Chen, “A framework for a distributed key management scheme in heterogeneous wireless sensor networks,” IEEE Transactions on Wireless Communications , vol. 7, no. 2, pp. 639– 647, February 2008

work page 2008

[14] [14]

Heterogeneous wireless sensor network deployment and topology control based on irregular sensor model,

C.-H. Wu and Y .-C. Chung, “Heterogeneous wireless sensor network deployment and topology control based on irregular sensor model,” in Advances in Grid and Pervasive Computing , 2007, pp. 78–88

work page 2007

[15] [15]

Exploiting heterogeneity in sensor networks,

M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y . Liu, and S. Singh, “Exploiting heterogeneity in sensor networks,” in Proc. of IEEE INFOCOM 2005

work page 2005

[16] [16]

On the strength of connectedness of random graphs,

P. Erd ˝os and A. R ´enyi, “On the strength of connectedness of random graphs,” Acta Math. Acad. Sci. Hungar , pp. 261–267, 1961

work page 1961

[17] [17]

Dandelion++: Lightweight cryptocurrency networking with formal anonymity guarantees,

G. Fanti, S. B. Venkatakrishnan, S. Bakshi, B. Denby, S. Bhargava, A. Miller, and P. Viswanath, “Dandelion++: Lightweight cryptocurrency networking with formal anonymity guarantees,” Proc. ACM Meas. Anal. Comput. Syst. , vol. 2, no. 2, pp. 29:1–29:35, Jun. 2018

work page 2018

[18] [18]

The bitcoin lightning network: Scalable off-chain instant payments,

J. Poon and T. Dryja, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016

work page 2016

[19] [19]

k-connectivity in random key graphs with unreliable links,

J. Zhao, O. Yaan, and V . Gligor, “ k-connectivity in random key graphs with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 7, pp. 3810–3836, July 2015

work page 2015

[20] [20]

M. D. Penrose, Random Geometric Graphs . Oxford University Press, Jul. 2003

work page 2003

[21] [21]

Random graphs. 2000,

S. Janson, T. Łuczak, and A. Ruci ´nski, “Random graphs. 2000,” Wiley– Intersci. Ser . Discrete Math. Optim , 2000

work page 2000

[22] [22]

Zero–one laws for connectivity in random key graphs,

O. Ya ˘gan and 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

work page 2012

[23] [23]

Zero-one laws for connectivity in inhomogeneous random key graphs,

O. Ya ˘gan, “Zero-one laws for connectivity in inhomogeneous random key graphs,” IEEE Transactions on Information Theory , vol. 62, no. 8, pp. 4559–4574, Aug 2016

work page 2016

[24] [24]

k-connectivity of inhomogeneous random key graphs with unreliable links,

R. Eletreby and O. Ya ˘gan, “k-connectivity of inhomogeneous random key graphs with unreliable links,” IEEE Transactions on Information Theory, pp. 1–1, 2019

work page 2019

[25] [25]

k-connectivity in random key graphs with unreliable links,

J. Zhao, O. Ya ˘gan, and V . Gligor, “k-connectivity in random key graphs with unreliable links,” IEEE Transactions on Information Theory , vol. 61, no. 7, pp. 3810–3836, July 2015. Appendix In this Section, we present a detailed proof of Theorem 1. We remind the readers that H(n;µ,Kn) is the inhomogeneous random K-out graph induced by the heterogeneous p...

work page 2015

[26] [26]

In other words, we let Zd(n;µ,Kn) = ∑n i=1 1{deg(vi) = d}, where deg(vi) is the degree of node vi

Establishing the one-law in Theorem 1: Let Zd(n;µ,Kn) denote the number of nodes in H(n;µ,Kn) with degree d where d = 1,...,k − 1. In other words, we let Zd(n;µ,Kn) = ∑n i=1 1{deg(vi) = d}, where deg(vi) is the degree of node vi. Since each node makes at least one selection, no node can have degree zero. To establish the one-law, we use the method of ﬁrst...

work page

[27] [27]

This technique is referred to as the method of ﬁrst moment

Establishing the zero-law in Theorem 1: We saw above how the one-law can be proved as a consequence of the Markov inequality applied to an integer-valued random variable counting the number of nodes with degree less than k. This technique is referred to as the method of ﬁrst moment. Next, we describe an outline for the proof of zero-law using the method o...

work page

[28] [28]

Noting that Ψ(x) is non-negative, (A.16) gives the bound that for x∈ [0, 1), we have 1−x≤e−x

For any x∈ [0, 1), it can be veriﬁed that log(1−x) =− ∫ x 0 1 1−tdt =−x− Ψ(x), (A.16) where Ψ(x) := ∫ x 0 t 1−tdt, 0≤x< 1. Noting that Ψ(x) is non-negative, (A.16) gives the bound that for x∈ [0, 1), we have 1−x≤e−x. (A.17) Furthermore, using L’Hospital’s rule we get lim x→0 Ψ(x) x2 = 1

work page

[29] [29]

(null)">(null)</latexit><latexit sha1_base64=

If x and y are functions of n such that x = o(1) and x2y = o(1), then (1−x)y =e−xy(1 + o(1)). (A.19) For a proof of this, see [25, Fact 3]. B. P ROOF OF PROPOSITION A.3 ( ESTABLISHING ONE -LAW IN THEOREM 1) Here, we consider the case where lim n→∞ γn = +∞. Recall that Zd(n;µ,Kn) denotes the number of nodes with degree d where d∈{ 1, 2...,k− 1}. We have E ...

work page