
Mindaugas Bloznelis

Valentas Kurauskas
Keywords:
Clique, Random intersection graph, Greedy algorithm, Complex network, Powerlaw, Clustering
Abstract
An intersection graph defines an adjacency relation between subsets $S_1,\dots, S_n$ of a finite set $W=\{w_1,\dots, w_m\}$: the subsets $S_i$ and $S_j$ are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution $\mathbb{P}(S_i=A)=P(A){\binom{m}{A}}^{1}$, $A\subseteq W$, where $P$ is a probability on $\{0, 1, \dots, m\}$, we obtain the random intersection graph $G=G(n,m,P)$. We establish the asymptotic order of the clique number $\omega(G)$ of a sparse random intersection graph as $n,m\to+\infty$. For $m = \Theta(n)$ we show that the maximum clique is of size $(1\alpha/2)^{\alpha/2}n^{1\alpha/2}(\ln n)^{\alpha/2}(1+o_P(1))$ in the case where the asymptotic degree distribution of $G$ is a powerlaw with exponent $\alpha \in (1,2)$. It is of size $\frac {\ln n} {\ln \ln n}(1+o_P(1))$ if the degree distribution has bounded variance, i.e., $\alpha>2$. We construct a simple polynomialtime algorithm which finds a clique of the optimal order $\omega(G) (1o_P(1))$.