On Connectivity in a General Random Intersection Graph

DOI10.1137/1.9781611974324.12MaRDI QIDQ5194949zbMATH OpenOpenAlexFDO

Authors

Publication date 17 September 2019

Published in 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.03890

Mathematics Subject Classification ID

Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Random graphs (graph-theoretic aspects) (05C80)

Abstract: There has been growing interest in studies of general random intersection graphs. In this paper, we consider a general random intersection graph $mathbbG(n,overrightarrowa,overrightarrow{K}_n,P_n)$ defined on a set $mathcal{V}_n$ comprising $n$ vertices, where $overrightarrowa$ is a probability vector $(a_1,a_2,ldots,a_m)$ and $overrightarrow{K}_n$ is $(K_{1,n},K_{2,n},ldots,K_{m,n})$. This graph has been studied in the literature including a most recent work by Yau{g}an [arXiv:1508.02407]. Suppose there is a pool $mathcal{P}_n$ consisting of $P_n$ distinct objects. The $n$ vertices in $mathcal{V}_n$ are divided into $m$ groups $mathcal{A}_1,mathcal{A}_2,ldots,mathcal{A}_m$. Each vertex $v$ is independently assigned to exactly a group according to the probability distribution with $mathbbP[vinmathcal{A}_i]=a_i$, where $i=1,2,ldots,m$. Afterwards, each vertex in group $mathcal{A}_i$ independently chooses $K_{i,n}$ objects uniformly at random from the object pool $mathcal{P}_n$. Finally, an undirected edge is drawn between two vertices in $mathcal{V}_n$ that share at least one object. This graph model $mathbbG(n,overrightarrowa,overrightarrow{K}_n,P_n)$ has applications in secure sensor networks and social networks. We investigate connectivity in this general random intersection graph $mathbbG(n,overrightarrowa,overrightarrow{K}_n,P_n)$ and present a sharp zero-one law. Our result is also compared with the zero-one law established by Yau{g}an.

Cited in

(12)

• Mixed connectivity properties of random graphs and some special graphs
• Asymptotic connectedness of random interval graphs in a one dimensional data delivery problem
• Diameter, connectivity, and phase transition of the uniform random intersection graph
• On the easiest way to connect k points in the random interlacements process
• Equivalence of a random intersection graph and G (n ,p )
• Selected Combinatorial Properties of Random Intersection Graphs
• Random graphs of Internet type and the generalised allocation scheme
• On Some Combinatorial Properties of Random Intersection Graphs
• On the connectivity of graphs generated by a sum of random mappings
• On Connectivity and Robustness in Random Intersection Graphs
• The coupling method for inhomogeneous random intersection graphs.
• Selected combinatorial problems through the prism of random intersection graphs models

This page was built for publication: On Connectivity in a General Random Intersection Graph

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