Random intersection graphs have received much attention for nearly two decades, and currently have a wide range of applications ranging from key predistribution in wireless sensor networks to modeling social networks. In this paper, we investigate the strengths of connectivity and robustness in a general random intersection graph model. Specifically, we establish sharp asymptotic zero-one laws for k-connectivity and k-robustness, as well as the asymptotically exact probability of k-connectivity, for any positive integer k. The k-connectivity property quantifies how resilient is the connectivity of a graph against node or edge failures. On the other hand, k-robustness measures the effectiveness of local diffusion strategies (that do not use global graph topology information) in spreading information over the graph in the presence of misbehaving nodes. In addition to presenting the results under the general random intersection graph model, we consider two special cases of the general model, a binomial random intersection graph and a uniform random intersection graph, which both have numerous applications as well. For these two specialized graphs, our results on asymptotically exact probabilities of k-connectivity and asymptotic zero-one laws for k-robustness are also novel in the literature.
For random intersection graphs in this paper, two nodes have an edge in between if their object sets share at least one object. A natural variant is to define graphs with edges only between nodes which have at least @math objects in common (instead of just @math ) for some positive integer @math . Zhao @cite_5 @cite_25 @cite_11 consider @math -connectivity in graphs under this definition. In addition, ( @math )-connectivity of other random graphs have also been investigated in the literature @cite_4 @cite_34 .
@cite_4 @cite_5 @cite_34 @cite_25 @cite_11
2005079131 2079098913 2052426738 104125573 2963768473
In this paper, we consider a wireless network with unreliable links and investigate its minimum node degree and k- connectivity. In such network, n nodes are uniformly distributed in a region, and edges are established for any two nodes within a certain distance and with a probabilistically active link in between. On a torus topology, we present a zero-one law for the property of minimum degree being at least k, leading to a zero-law for k-connectivity and an intermediate result towards a one-law. On a square with boundary effect, we establish a one- law for minimum degree. Our results are derived from rigorous analysis and also confirmed by the simulation, and they provide guidelines for the design of wireless networks. Index Terms—Connectivity, Erdos-Renyi graph, geometric graph, graph intersection, minimum node degree, random graph, unreliable link, wireless network, zero-one law. 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. To be considered for an IEEE Jack Keil Wolf ISIT Student Paper Award. We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent on off channels. Modeling the network by an intersection of a random K-out graph and an Erdős-Renyi graph, we present scaling conditions (on the number of nodes, the scheme parameter K, and the probability of a wireless channel being on) such that the resulting graph contains no nodes with degree less than k with high probability, when the number of nodes gets large. Results are given in the form of zero-one laws and are shown to improve the previous results by Yagan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of k-connectivity; i.e., the property that graph remains connected despite the deletion of any k − 1 nodes or edges. The seminal q-composite key predistribution scheme [3] (IEEE S&P 2003) is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Yagan [12] (IEEE IT 2012) and we [15] (IEEE ISIT 2013) explore topological properties of WSNs employing the q-composite scheme in the case of q = 1 with unreliable communication links modeled as independent on off channels. However, it is challenging to derive results for general q under such on off channel model. In this paper, we resolve such challenge and investigate topological properties related to node degree in WSNs operating under the q-composite scheme and the on off channel model. Our results apply to general q, yet there has not been any work in the literature reporting the corresponding results even for q = 1, which are stronger than those about node degree in [12], [15]. Specifically, we show that the number of nodes with an arbitrary degree asymptotically converges to a Poisson distribution, present the asymptotic probability distribution for the minimum node degree of the network, and establish the asymptotically exact probability for the property that the minimum node degree is at least an arbitrary value. Numerical experiments confirm the validity our analytical findings. Random s-intersection graphs have recently received much interest in a wide range of application areas. Broadly speaking, a random s-intersection graph is constructed by first assigning each vertex a set of items in some random manner, and then putting an undirected edge between all pairs of vertices that share at least s items (the graph is called a random intersection graph when s = 1). A special case of particular interest is a uniform random s-intersection graph, where each vertex independently selects the same number of items uniformly at random from a common item pool. Another important case is a binomial random s-intersection graph, where each item from a pool is independently assigned to each vertex with the same probability. Both models have found numerous applications thus far including cryptanalysis, and modeling recommender systems, secure sensor networks, online social networks, trust networks and small-world networks (uniform random s-intersection graphs), as well as clustering analysis, classification, and the design of integrated circuits (binomial random s-intersection graphs). In this paper, for binomial uniform random s-intersection graphs, we present results related to k-connectivity and minimum vertex degree. Specifically, we derive the asymptotically exact probabilities and zero--one laws for the following three properties: (i) k-vertex-connectivity, (ii) k-edge-connectivity and (iii) the property of minimum vertex degree being at least k.