  In a random intersection graph $G_{n,m,p}$, each of $n$ vertices selects a
random subset of a set of $m$ labels by including each label independently with
probability $p$ and edges are drawn between vertices that have at least one
label in common. Among other applications, such graphs have been used to model
social networks, in which individuals correspond to vertices and various
features (e.g. ideas, interests) correspond to labels; individuals sharing at
least one common feature are connected and this is abstracted by edges in
random intersection graphs. In this paper, we consider the problem of finding
maximum cliques when the input graph is $G_{n,m,p}$. Current algorithms for
this problem are successful with high probability only for relatively sparse
instances, leaving the dense case mostly unexplored. We present a spectral
algorithm for finding large cliques that processes vertices according to
respective values in the second largest eigenvector of the adjacency matrix of
induced subgraphs of the input graph corresponding to common neighbors of small
cliques. Leveraging on the Single Label Clique Theorem from [15], we were able
to construct random instances, without the need to externally plant a large
clique in the input graph. In particular, we used label choices to determine
the maximum clique and then concealed label information by just giving the
adjacency matrix of $G_{n, m, p}$ as input to the algorithm. Our experimental
evaluation showed that our spectral algorithm clearly outperforms existing
polynomial time algorithms, both with respect to the failure probability and
the approximation guarantee metrics, especially in the dense regime, thus
suggesting that spectral properties of random intersection graphs may be also
used to construct efficient algorithms for other NP-hard graph theoretical
problems as well.
