Transitional Behavior of $q$-Composite Random Key Graphs With Applications to Networked Control
Jun Zhao · IEEE Transactions on Control of Network Systems · 2017
Random key graphs have received considerable attention and been used in various applications including secure sensor networks, social networks, the study of epidemics, cryptanalysis, and recommender systems. In this paper, we investigate q-composite random key graphs, whose construction on n nodes is as follows: each node independently selects a set of Kndifferent keys uniformly at random from the same pool of Pndistinct keys, and two nodes establish an undirected edge in between if and only if they share at least q key(s). Such q-composite random key graphs allow modeling secure sensor networks employing the well-known q-composite key predistribution. For such graphs, we analyze the probabilities of having k-connectivity, k-robustness, a Hamilton cycle, and perfect matching, respectively. The derived results reveal that q-composite random key graphs exhibit a sharp transition for each property: as Knincreases, the probability of the property sharply increases. These results provide guidelines to design secure sensor networks for different control-related applications: distributed in-network parameter estimation, fault-tolerant consensus, and resilient data backup.