Exploring Random Key Graphs!

Armand M. Makowski
Department of Electrical and Computer Engineering
and the Institute for Systems Research
University of Maryland at College Park

 

Friday, November 13, 2pm
Location: BA 1210 

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 they are naturally associated with a random key predistribution scheme recently 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 presented. 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.

Bio:

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 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.