The largest component in an inhomogeneous random intersection graph with clustering

2010/02/24 by Mindaugas Bloznelis, Bloznelis, Mindaugas
Mathematics · #05C80 #60J80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:60J80

paper · pdf · doi:10.48550/arxiv.1002.4649

14 pages

arxiv created 2010/02/24 · arxiv updated 2010/02/26

Abstract

Given b>0, integers n, m=bn and a probability measure Q on 0, 1,..., m, consider the random intersection graph on the vertex set [n]=1, ..., n, where i and j are declared adjacent whenever S(i) and S(j) intersect. Here S(1), ..., S(n) denote iid random subsets of [m] such that P(|S(i)|=k)=Q(k). For sparse random intersection graphs we establish a first order asymptotic for the order of the largest connected component N=n(1-Q(0))g+o(n) in probability. Here g is an average of nonextinction probabilities of a related multi-type Poisson branching process.

Related

• Random bipartite graphs with i.i.d. weights and applications to inhomogeneous random intersection graphs
• Critical scaling limits of the random intersection graph
• Large random intersection graphs inside the critical window and triangle counts
• The phase transition in inhomogeneous random intersection graphs
• An elementary approach to component sizes in critical random graphs