Zero-one laws for connectivity in random key graphs
arXiv:0908.3644 · doi:10.1109/TIT.2011.2181331
Abstract
The random key graph is a random graph naturally associated with the random key predistribution scheme of Eschenauer and Gligor for wireless sensor networks. 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 complement and strengthen recent work on this conjecture by Blackburn and Gerke. In particular, the results are given under conditions which are more realistic for applications to wireless sensor networks.
16 pages
References in corpus (2)
Cited by in corpus (36)
- Zero-one laws for connectivity in random key graphs
- Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel
- k-Connectivity in Random Key Graphs with Unreliable Links
- Assortativity and clustering of sparse random intersection graphs
- Topological properties of secure wireless sensor networks under the q-composite key predistribution scheme with unreliable links
- Modeling the pairwise key distribution scheme in the presence of unreliable links
- Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
- Zero-one laws for connectivity in inhomogeneous random key graphs
- On Connectivity and Robustness in Random Intersection Graphs
- On the strengths of connectivity and robustness in general random intersection graphs
- Consensus over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
- On Topological Properties of Wireless Sensor Networks under the q-Composite Key Predistribution Scheme with On/Off Channels
- On -connectivity and minimum vertex degree in random -intersection graphs
- Optimal Radius for Connectivity in Duty-Cycled Wireless Sensor Networks
- Probabilistic key predistribution in mobile networks resilient to node-capture attacks
- On secure communication in sensor networks under q-composite key predistribution with unreliable links
- Random intersection graphs and their applications in security, wireless communication, and social networks
- A zero-one law for the existence of triangles in random key graphs
- Counting triangles, tunable clustering and the small-world property in random key graphs (Extended version)
- Analyzing connectivity of heterogeneous secure sensor networks
- Analyzing resilience of interest-based social networks against node and link failures
- Tight Bounds for Connectivity of Random K-out Graphs
- Exact Analysis of k-Connectivity in Secure Sensor Networks with Unreliable Links
- On connectivity in a general random intersection graph
- On the gradual deployment of random pairwise key distribution schemes (Extended Version)
- The cover time of a sparse random intersection graph
- k-Connectivity of Random Key Graphs
- On the Eschenauer-Gligor key predistribution scheme under on-off communication channels: The absence of isolated nodes (Extended version)
- On Connectivity Thresholds in the Intersection of Random Key Graphs on Random Geometric Graphs
- Node isolation in large homogeneous binary multiplicative attribute graph models
- Transitional Behavior of q-Composite Random Key Graphs with Applications to Networked Control
- Threshold Functions in Random s-Intersection Graphs
- Secure Connectivity of Wireless Sensor Networks Under Key Predistribution with on/off Channels
- On the Strength of Connectivity of Inhomogeneous Random K-out Graphs
- Secure Connectivity of Heterogeneous Wireless Sensor Networks Under a Heterogeneous On-Off Channel Model
- A curious gap in one-dimensional geometric random graphs between connectivity and the absence of isolated node