On $k$-connectivity and minimum vertex degree in random $s$-intersection graphs

Abstract

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 the modeling of 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$.

This paper appears in ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2015, a conference co-located with ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015

References in corpus (9)

• Zero-one laws for connectivity in random key graphs
• Epidemics on random intersection graphs
• Assortativity and clustering of sparse random intersection graphs
• Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
• Component Evolution in General Random Intersection Graphs
• Sharp threshold functions for the random intersection graph via coupling method?
• The phase transition in inhomogeneous random intersection graphs
• Hyperbolicity, degeneracy, and expansion of random intersection graphs
• Exact Analysis of k-Connectivity in Secure Sensor Networks with Unreliable Links

Cited by in corpus (6)

• Topological properties of secure wireless sensor networks under the q-composite key predistribution scheme with unreliable links
• Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
• Probabilistic key predistribution in mobile networks resilient to node-capture attacks
• Threshold Functions in Random s-Intersection Graphs
• Secure Connectivity of Wireless Sensor Networks Under Key Predistribution with on/off Channels
• On the Strength of Connectivity of Inhomogeneous Random K-out Graphs