Allerton 2015 Paper Abstract


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 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Sensor Networks, Social Networks, Sensor Networks in Communications


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.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  09:14:45 PST  Terms of use