Title: Counting triangles, tunable clustering and the small-world property in random key graphs (Extended version),
Abstract: Random key graphs were introduced to study various properties of the
Eschenauer-Gligor key predistribution scheme for wireless sensor networks
(WSNs). Recently this class of random graphs has received much attention in
contexts as diverse as recommender systems, social network modeling, and
clustering and classification analysis. This paper is devoted to analyzing
various properties of random key graphs. In particular, we establish a zero-one
law for the the existence of triangles in random key graphs, and identify the
corresponding critical scaling. This zero-one law exhibits significant
differences with the corresponding result in Erdos-Renyi (ER) graphs. We also
compute the clustering coefficient of random key graphs, and compare it to that
of ER graphs in the many node regime when their expected average degrees are
asymptotically equivalent. For the parameter range of practical relevance in
both wireless sensor network and social network applications, random key graphs
are shown to be much more clustered than the corresponding ER graphs. We also
explore the suitability of random key graphs as small world models in the sense
of Watts and Strogatz.