The q-composite key predistribution scheme [1] is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Prior work [2]-[4] explores topological properties of WSNs employing the q-composite scheme for q = 1 with unreliable communication links modeled as independent on off channels. In this paper, we investigate topological properties related to the node degree in WSNs operating under the q-composite scheme and the on off channel model. Our results apply to general q and are stronger than those reported for the node degree in prior work even for the case of q being 1. Specifically, we show that the number of nodes with certain degree asymptotically converges in distribution to a Poisson random variable, present the asymptotic probability distribution for the minimum degree of the network, and establish the asymptotically exact probability for the property that the minimum degree is at least an arbitrary value. Numerical experiments confirm the validity of our analytical findings.
For graph @math , Bloznelis @cite_23 demonstrate that a connected component with at at least a constant fraction of @math emerges asymptotically when the edge probability @math exceeds @math . Bloznelis and uczak @cite_21 have recently considered connectivity and perfect matching. Still in @math , Bloznelis @cite_17 investigate assortativity and clustering, while for asymptotic node degree distribution, Bloznelis @cite_44 analyzes clustering coefficient and the degree distribution of a typical node. We @cite_22 compute the probability distribution for the minimum node degree. Recently, Bloznelis and Rybarczyk @cite_19 and we @cite_20 have derived the asymptotically exact probability of @math -connectivity. Several variants or generalizations of graph @math are also considered in the literature @cite_23 @cite_44 @cite_17 @cite_27 .
@cite_22 @cite_21 @cite_44 @cite_19 @cite_27 @cite_23 @cite_20 @cite_17
2020272293 2145244355 1899546701 2135291682 2150191198
Let W1,…,Wn be independent random subsets of [m]= 1,…,m . Assuming that each Wi is uniformly distributed in the class of d-subsets of [m] we study the uniform random intersection graph Gs(n,m,d) on the vertex set W1,…Wn , defined by the adjacency relation: Wi∼Wj whenever |Wi∩Wj|≧s. For even n we show that as n,m→∞ the edge density threshold for the property that Gs(n,m,d) contains a perfect matching is asymptotically the same as that for Gs(n,m,d) being connected. We establish asymptotic vertex degree distribution and examine its relation to the clustering coecient in two popular random intersection graph models of Godehardt and Jaworski (2001). For sparse graphs with positive clustering coecient, we examine statistical dependence between the (local) clustering coecient and the degree. Our results are mathematically rigorous. They are consistent with the empirical observation of (2011) that correlates negatively with degree." Moreover, they explain empirical results on k 1 scaling of the local clustering coecient of a vertex of degree k reported in Ravasz and Barab asi (2003). Random intersection graphs (RIGs) are an important random structure with algorithmic applications in social networks, epidemic networks, blog readership, and wireless sensor networks. RIGs can be interpreted as a model for large randomly formed non-metric data sets. We analyze the component evolution in general RIGs, giving conditions on the existence and uniqueness of the giant component. Our techniques generalize existing methods for analysis of component evolution: we analyze survival and extinction properties of a dependent, inhomogeneous Galton-Watson branching process on general RIGs. Our analysis relies on bounding the branching processes and inherits the fundamental concepts of the study of component evolution in Erdős-Renyi graphs. The major challenge comes from the underlying structure of RIGs, which involves both a set of nodes and a set of attributes, with different probabilities associated with each attribute. We study a connectivity property of a secure wireless network that uses random pre-distribution of keys. A network is composed of n sensors. Each sensor is assigned a collection of d different keys drawn uniformly at random from a given set of m keys. Two sensors are joined by a communication link if they share a common key. We show that for large n with high probability the connected component of size Ω(n) emerges in the network when the probability of a link exceeds the threshold 1-n. Similar component evolution is shown for networks where sensors communicate if they share at least s common keys. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009 We consider sparse random intersection graphs with the property that the clustering coefficient does not vanish as the number of nodes tends to infinity. We find explicit asymptotic expressions for the correlation coefficient of degrees of adjacent nodes (called the assortativity coefficient), the expected number of common neighbours of adjacent nodes, and the expected degree of a neighbour of a node of a given degree k. These expressions are written in terms of the asymptotic degree distribution and, alternatively, in terms of the parameters defining the underlying random graph model.