Paper ThC4.1
Zhao, Jun (CMU & ASU/Princeton)
Sharp Transitions in Random Key Graphs
Scheduled for presentation during the Regular Session "Sensor Networks II" (ThC4), Thursday, October 1, 2015,
13:30−13:50, Pine
53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA
This information is tentative and subject to change. Compiled on January 18, 2020


Keywords Sensor Networks, Social Networks, Sensor Networks in Communications
Abstract
Random key graphs have received much interest and been used in diverse applications. A random key graph with $n$ nodes is constructed as follows: each node selects a set of $K_n$ different items uniformly at random from the same pool of $P_n$ distinct items, and two nodes establish an undirected edge in between if and only if they share at least one item. For such graph denoted by $G(n, K_n, P_n)$, we present the following results in this paper. First, we provide an exact analysis on the probabilities of $G(n, K_n, P_n)$ having a perfect matching and having a Hamilton cycle respectively. The analysis reveals that for both perfect matching containment and Hamilton cycle containment, $G(n, K_n, P_n)$ exhibits sharp phase transitions: for each property above, as $K_n$ increases, the limit of the probability that $G(n, K_n, P_n)$ has the property sharply increases from $0$ to $1$. Second, we compute the phase transition widths of $G(n, K_n, P_n)$ for $k$connectivity, perfect matching containment, and Hamilton cycle containment, respectively.

