Recent Results for random key graphs: Connectivity, triangles, etc.

Random key graphs, also known as uniform random intersection graphs, appear in application areas as diverse as clustering analysis, collaborative filtering in recommender systems and key distribution in wireless sensor networks (WSNs). In this last context random key graphs are naturally associated with a random key predistribution scheme proposed by Eschenauer and Gligor.

In this talk we present some recent results concerning the structure of random key graphs. Similarities and differences with Erdos-Renyi graphs are given. We also discuss performance implications for the scheme of Eschenauer and Gligor. Highlights include:
(i) A zero-one law for graph connectivity (and its critical scaling) as the number of nodes becomes unboundedly large; (ii) A zero-one law (and its critical scaling) for the appearance of triangles; and (iii) Clustering coefficients and the "small world" property
of random key graphs.

This is joint work with Ph.D. student Osman Yagan.