Title:

Random key graphs and the pre-distribution scheme of Eschenauer and Gligor

Armand M. Makowski
Department of Electrical and Computer Engineering and the
Institute for Systems Research University of Maryland at
College Park College Park, Maryland 20742
armand@isr.umd.edu

Abstract:

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.

BIOGRAPHY:

Armand M. Makowski received the Licence en Sciences Math\'ematiques from the Universit\'e 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 College Park, where he is Professor of Electrical and Computer Engineering. He has held a joint appointment with the Institute for Systems Research since its establishment in 1985.

Armand Makowski was a C.R.B. Fellow of the Belgian-American Educational Foundation (BAEF) for the academic year 1975-76; he is also a 1984 recipient of the NSF Presidential Young Investigator Award and became an IEEE Fellow in 2006.

His research interests lie in applying advanced methods from the theory of stochastic processes to the modeling, design and performance evaluation of engineering systems, with particular emphasis on communication systems and networks.