On Connectivity in a General Random Intersection Graph
Jun Zhao, Panpan Zhang · 2015
There has been growing interest in studies of general random intersection graphs.In this paper, we consider a general random intersection graph G(n, -→ a , -→ K n , P n ) defined on a set V n comprising n vertices, where -→ a is a probability vector (a 1 , a 2 , . . ., a m ) and).This graph has been studied in the literature [10,11,20,29] including a most recent work by Yagan [20].Suppose there is a pool P n consisting of P n distinct objects.The n vertices in V n are divided into m groups A 1 , A 2 , . . ., A m .Each vertex v is independently assigned to exactly a group according to the probability distribution with P[v ∈ A i ] = a i , where i = 1, 2, . . ., m. Afterwards, each vertex in group A i independently chooses K i,n objects uniformly at random from the object pool P n .Finally, an undirected edge is drawn between two vertices in V n that share at least one object.This graph model G(n, -→ a , -→ K n , P n ) has applications in secure sensor networks and social networks.We investigate connectivity in this general random intersection graph G(n, -→ a , -→ K n , P n ) and present a sharp zero-one law.Our result is also compared with the zero-one law established by Yagan [20].