Counting triangles, tunable clustering and the small-world property in random key graphs (Extended version)

arXiv1701.03758MaRDI QIDQ6281906FDOQ6281906

Authors: Osman Yaǧan, Armand M. Makowski 

Publication date: 13 January 2017

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.

This page was built for publication: Counting triangles, tunable clustering and the small-world property in random key graphs (Extended version)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281906)