The Largest Component in an Inhomogeneous Random Intersection Graph with Clustering

Abstract

Given integers $n$ and $m=\lfloor\beta n \rfloor$ and a probability measure $Q$ on $\{0, 1,\dots, m\}$, consider the random intersection graph on the vertex set $[n]=\{1,2,\dots, n\}$ where $i,j\in [n]$ are declared adjacent whenever $S(i)\cap S(j)\neq\emptyset$. Here $S(1),\dots, S(n)$ denote the iid random subsets of $[m]$ with the distribution $\bf{P}(S(i)=A)={{m}\choose{|A|}}^{-1}Q(|A|)$, $A\subset [m]$. For sparse random intersection graphs, we establish a first-order asymptotic as $n\to \infty$ for the order of the largest connected component $N_1=n(1-Q(0))\rho+o_P(n)$. Here $\rho$ is the average of nonextinction probabilities of a related multitype Poisson branching process.