Finding a Planted Clique

Planted Clique Model

The planted clique model is a variant of this model where we assume that there is a hidden clique of size $k$ that is present in the graph. More precisely, a graph $G\sim G(n,p,k)$ is generated as follows:

1. We first sample $G$ from $G(n,p)$.
2. Then, we select a subset $S\subseteq V(G)$ of $k$ vertices uniformly at random.
3. Finally, we add all the missing edges between the vertices in $S$, ensuring that $S$ forms a clique in the graph.

We can think of this as a more general two-step process: first, we generate a random graph, and then we “plant” a clique of size $k$ in it.

Finding a Planted Clique on Dense Random Graphs

Case $k=\Omega (\sqrt{n\log n})$

Theorem

Let $G\sim G(n,1/2,k)$ be a random graph with a planted clique $S$ of size $k=c\sqrt{n\log n}$. Each node $v\in S$ receive at least $\frac{1}{3}k$ of new incident edges by adding the planted clique to the underlying Erdos-Renyi random graph $G(n,1/2)$ (i.e., after step 3 ), with (high) probability at least $1-e^{-\Omega (|S|)}$.

Proof

For every $v\in S$, let $X_v$ be the random variable denoting the number of neighbours of $v$ in $S$ considering only the edges of the unerlying random graph $G(n,1/2)$, with expectation $\mathbb{E}{X}_v=\frac{k}{2}$. By using Chernoff’s bound

$$\begin{array}{rl}\mathrm{Pr}\left\{X_v\ge \frac{2}{3}k\right\}& =\mathrm{Pr}\left\{X_v\ge \frac{k}{6}+\mathbb{E}{X}_v\right\}\\ & \le \exp \left(-\frac{2}{k}{\left(\frac{k}{6}\right)}^2\right)\\ & =\exp \left(-k/18\right)\end{array}$$

Since the number neighborhood of $v$ in $S$ before step 3 is at most $2k/3$ with high probability, the number of new edges incident to $S$ after step 3 must be at least $k/3$ with high probability.

Since we know that, with high probability, the degree of any vertex outside the planted clique $S$ is

$$\tilde{\delta }=\frac{n-1}{2}\pm (1+o(1))\sqrt{n\log n},$$

for sufficiently large value of $c$ the vertices of the planted clique $S$ are those with maximum degrees.

Indeed, by choosing $c\ge 6$ we have that the degree of each vertex $v\in S$ is, with high probability, at least

$${\delta }_v\ge \tilde{\delta }+\frac{c}{3}\sqrt{n\log n}=\frac{n-1}{2}+(2+o(1))\sqrt{n\log n}$$

Case $k=\Omega (\sqrt{n})$

🚧TODO🚧