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.
