Problema del Clique Implantado

Miguel Trias

Motivacion

  • Interferencia de antenas
  • Correlacion de activos de una cartera
  • Deteccion de bots en redes sociales
  • Deteccion de ataques informaticos
  • Proteinas / Genes

\(\vdots\)

Grafos

\(G(V, E)\)

\(V = \{ 1, \dots, n \}\)

\(E = \{ \{i,j\} \quad i,j \in V \}\)

Matriz de Adyacencia

\[ \begin{align} & A \in \{0,1\}^{n\times n} \\ & \\ & A_{ij} = 1 \leftrightarrow \{i,j\} \in E \\ & \\ & A = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{pmatrix} \end{align} \]

¿Que es un Clique ?

Un Subgrafo Completo Maximal

Figure 1

Clique y Matriz de Adyacencia

Clique en una posicion trivial

Motivacion (bis)

\[ A = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \]

Grafos de Erdős-Rényi

  • \( \mathcal{G}(n, p) \)
  • Tamaño \(n\)
  • Aristas \(\sim Ber(p)\) independientes
  • Grado de un nodo \(\sim Bin(n-1, p)\)

Matriz de Adyacencia de un \( \mathcal{G}(n, ½ ) \)

Figure 2

Clique en el “mundo real”

\( \mathcal{G}(200, p= ½ ) \) con clique implantado de tamaño \(k=40\)

Clique en el mundo real

\( \mathcal{G}(200, p=.5) \) con clique implantado de tamaño \(k=150\)

\( \mathcal{G}(n, ½ ) \)


Roughgarden, p16
El numero esperado de cliques de tamaño \(k\) es \(\approx n^k 2^{-k^2/2}\) (\(=1\) si \(k=2\log_2 n\))

Roughgarden, p16
El tamaño \(k_m\) del clique máximo de un grafo aleatorio es muy probablemente \(≈2\log_2{n}\)

Conclusion
Si \(k\) es chico, un clique de tamaño \(k\) sera indistinguible del ruido aleatorio.

Kucera, 1995

\( \mathcal{G}(1000, ½ ) \) con clique implantado.

Ganó Alon

Fuente: Geogebra

n
[1] 1000
# Roughgarden
2 * log2(n)
[1] 19.93157
# Kucera
sqrt(n * log10(n))
[1] 54.77226
# Alon
sqrt(n)
[1] 31.62278

Alon, 1998

Algoritmo de clustering espectral. Asegura una deteccion exacta en tiempo polinomial si \(k = \Omega(\sqrt n)\)

Sea \(A\) la matriz de adyacencia de \( \mathcal{G}(n, p= ½ ) \)

\[ E(A) = \begin{pmatrix} ½ & \dots & \dots & ½ \\ \vdots & \ddots & & \vdots \\ \vdots & & \ddots & \vdots \\ ½ & \dots & \dots & ½ \end{pmatrix} \]

Alon 1998

¿Como cambia \(E(A)\) si implanto un clique de tamaño \(k\)?

\[ E(A) = \begin{pmatrix} 1 & \dots & 1 & ½ & \dots & \dots & ½ \\ \vdots & \ddots & \vdots & \vdots & & & \vdots \\ 1 & \dots & 1 & ½ & \dots & \dots & ½ \\ ½ & \dots & ½ & ½ & \dots & \dots & ½ \\ \vdots & & \vdots & \vdots & \ddots & & ½ \\ \vdots & & \vdots & \vdots & & \ddots & ½ \\ ½ & \dots & ½ & ½ & \dots & \dots & ½ \\ \end{pmatrix} \]

Realizacion =
Señal + Perturbacion: \[A = E(A) + P\]

Espectro de \(E(A)\)


Simetrica \(\implies\)

  • \(\lambda_i \in \mathbb{R}\)
  • Autovectores Ortogonales

\(v_1\) Primer Autovector \(E(A)\)


\[\begin{align} & { \Large \mathbf{1} } = (1, \dots, 1)^\top \\ \\ & \left( E(A) \cdot { \Large \mathbf{1} } \right)_i = \sum_j E(A)_{ij} = grado(i) \approx n/2 \\ & E(A) \cdot { \Large \mathbf{1} } \approx \frac{n}{2} { \Large \mathbf{1} } \\ \\ & v_1 \approx { \Large \mathbf{1} } \qquad \lambda_1 \approx \frac{n}{2} \end{align}\]

Las sumas de todas las filas son \(\approx\) constantes.

Entonces, el vector de unos es un \(\approx\) autovector.

\(v_2\) Segundo autovector de \(E(A)\)

\[\begin{align} & v_1 \perp v_2 \\ & 0 = \langle v_1, v_2 \rangle = v_1^\top v_2 = \sum_i (v_1)_i \cdot (v_2)_i = \sum_i (v_2)_i \\ \\ &w = \left( n-k, \dots, n-k, \quad -k, \dots, \dots, \dots, -k \right) \\ &\sum_i w_i = 0 \\ &E(A)\cdot w = \left( ½ (n-k)k,\dots, ½ (n-k)k,0,\dots,0 \right) \\ &E(A) \cdot w \approx \frac{k}{2} w \\ \\ & v_2 \approx w \qquad \lambda_2 \approx \frac{k}{2} \end{align}\]

\(v_2\) asigna valores grandes a los \(k\) vertices del clique.

Algoritmo para \( \mathcal{G}(n, ½ ) \)

  1. Hallamos la matriz de adyacencia \(A\)
  2. Calculamos \(v_2\)
  3. Ordeno las coordenadas de \(v_2\) de mayor a menor
  4. Los primeros \(k\) coeficientes deberian ser los correspondientes a los vertices del clique

¿Es valido el analisis de \(E(A)\)?

Si.

\(A\) es una realizacion de \(E(A)\)

\(A = E(A) + P\)

Pero el analisis espectral vale igual

Davis-Kahan

La rotacion de los autovectores de \(E(A)\) luego de la Perturbacion \(P\) depende de la magnitud de la perturbacion y del “eigengap”

\[\sin\theta_i \leq \frac{2\|P\|}{min_{j\neq i}|\lambda_i-\lambda_j|}\]
Conclusion: La rotación de autovectores es tan pequeña que la gran mayoría de los vértices del clique se mantienen en las posiciones superiores del autovector \(v_2\)

Decaimiento Espectral

Verificacion - Ranking Espectral

¿Como puedo verificar que tengo los vertices del clique?

Verificacion - El grafico de Manuel

n=1000 k=100

¿Que pasa de acuerdo a \(k\) ?

\(n=1000\) \(\lambda_1 = n/2\) \(\lambda_2 = k/2\) Clique
\(k<20\) Indistinguible
\(k<32\) No funciona Alon
\(32<k<55\) Ruido Clique en \(v_2\) Alg. Espectral (Alon)
\(k<500\) Trivial (Kucera)
\(k>500\) Clique en \(v1\) Ruido

Referencias

Manuel H. (2021). Detección de un k-subgrafo denso en un grafo aleatorio. https://www.fcea.udelar.edu.uy/institucional/agenda/5385-seminario-del-iesta-3.html

Roughgarden, T. (2017). Cs264: Beyond worst-case analysis lectures# 9 and 10: Spectral algorithms for planted bisection and planted clique.

Alon, N., Krivelevich, M., and Sudakov, B. (1998). Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466.

Kucera, L. (1995). Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193–212.11

Lei, J., Rinaldo, A., et al. (2015). Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43(1):215–237.

Lugosi, G. (2017). Lectures on combinatorial statistics. 47th Probability Summer School, Saint-Flour, pages 1–91.