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.

Armand M. Makowski received the Licence en Sciences Mathematiques from the Universite Libre de Bruxelles in 1975, the M.S. degree in Engineering-Systems Science from U.C.L.A. in 1976 and the Ph.D. degree in Applied Mathematics from the University of Kentucky in 1981. In August 1981, he joined the faculty of the Electrical Engineering Department at the University of Maryland at College Park, where he is presently Professor of Electrical and Computer Engineering. He has held a joint appointment with the Institute for Systems Research, one of the original NSF Engineering Research Centers, since its establishment in 1985, and was its Associate Director for Research during 1995-1996. He is also a co-founder of and active participant in the Center for Satellite and Hybrid Communication Networks, a NASA center for the development and commercialization of space. He has held visiting positions at the Technion (Israel), INRIA (France), IBM T.J. Watson Research Center (Hawthorne), AT&T Bell Laboratories (Murray Hill), AT&T Research Labs (Florham Park) and the Insitut Mittag-Leffler (Sweden).

Dr. Makowski's research interests broadly lie in applying advanced methods from the theory of stochastic processes to the modeling, design and performance evaluation of a variety of engineering systems, with particular emphasis on communication systems and networks. Recent activities include the asymptotic methods for the performance evaluation of switching systems, long-range traffic modeling for multimedia applications in high-speed networks, many-flow asymptotics for TCP modeling, modeling locality of reference in caching systems, applications of swarm intelligence techniques to networking, stochastic control formulation of resource allocation issues in wireless networks (e.g., handoffs and paging) and random graph modeling in wireless networks.