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 general random intersection graph @math , Godehardt and Jaworski @cite_7 investigate its degree distribution and Bloznelis @cite_14 explore its component evolution, but provides neither a zero--one law nor the exact probability of its @math -connectivity property reported in our work.
@cite_14 @cite_7
2060271434 2963768473 2086721908 2020272293
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. 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. Random Intersection Graphs, G"n","m","p, is a class of random graphs introduced in Karonski (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that [email protected]?n^@[email protected]?, for any real @a different than one, we establish here, for the first time, a sharp threshold for the graph property ''Contains a Hamilton cycle''. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model. 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.