Information Security Seminar 

08/07/2009, 16:15 — 17:15 — Room P3.10, Mathematics Building
Virgil D. Gligor, Carnegie Mellon University

Brief Encounters on a Random Key Graph

The notion of the random key graph (now, a.k.a “uniform random intersection graph”) was defined for probabilistic key pre-distribution in wireless sensor networks. Recently, these graphs have been used for a variety of applications, such as recommender systems using global filtering and clustering analysis. While random key graphs are not Erdös-Renyi random graphs (e.g., the probabilities that graph edges exist are not independent of each other), they have similar connectivity properties under the assumption of “full visibility”; i.e., they obey a similar “zero-one” law as Erdös-Renyi graphs for some scaling of their parameters, whenever each node is within communication range of other nodes. In this presentation we explore various applications of random key graphs ranging from mobile networks, to trust establishment, to social networks. This is joint work with Haowen Chan and Adrian Perrig.