On the Intersection of Random Graphs with an Application to Random Key Pre-Distribution

Given two graphs on the same set of vertices, we define their intersection as the graph on this set of vertices whose edge set is the intersection of the edge sets of the component graphs. In this talk the component graphs are taken to be random graphs, e.g., Bernoulli random graphs, geometric random graphs or random key graphs.

We are interested in how the structural properties of random graphs obtained by intersection are determined by those of their component random graphs. Particular attention will be given to the existence of zero-one laws for graph connectivity and for the property that there are no isolated nodes, and the form of the associated critical scalings. These issues will be explored in the context of the Eschenauer-Gligor random key pre-distribution for wireless sensor networks under partial visibility.

This is joint work with former Ph.D. students N. Prasanth Anthapadmanabhan (Bell Laboratories, Alcatel-Lucent) and Osman Yagan (CMU) and was supported by NSF Grant CCF-1217997.

Speaker Bio: Armand 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.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.