Buscador de Clique Máximo

Pseudocódigo

Bron-Kerbosch explora con tres conjuntos: R es el clique construido hasta ahora, P contiene los candidatos que aún podrían extenderlo, y X contiene los vértices ya probados. Un clique es maximal exactamente cuando P y X están ambos vacíos.

BronKerbosch(R, P, X):
    si P y X están ambos vacíos:
        informar de R como clique maximal
        devolver

    para cada vértice v en P:
        BronKerbosch(R + {v},
                     P intersección vecinos(v),
                     X intersección vecinos(v))
        P = P - {v}
        X = X + {v}

// Con pivote: elegir un pivote u de P unión X y ramificar
// solo sobre los v de P que NO sean vecinos de u

X es la parte que la gente omite, y sin ella el algoritmo informa de cliques que no son maximales. Cuando un vértice ya ha sido explorado en este nivel pasa a X, de modo que cualquier clique que pudiera haberlo incluido se rechaza por no ser maximal. El refinamiento del pivote reduce después el factor de ramificación de forma drástica: todo clique maximal debe contener al pivote o a alguno de sus no vecinos, así que ramificar sobre el resto es trabajo desperdiciado.

Ejemplo resuelto, paso a paso

Enumera todos los cliques maximales de un grafo de seis aristas que contiene dos triángulos solapados y una arista colgante.

Grafo de ejemplo: Aristas no dirigidas A-B, A-C, B-C, B-D, C-D y D-E.

1. Empezar. R está vacío, P contiene los cinco vértices y X está vacío. Ramifica primero sobre A.
2. Ramificar sobre A. R pasa a ser {A}. P se reduce a los vecinos de A, que son B y C. Ramificando sobre B y luego sobre C se construye {A, B} y después {A, B, C}. En ese punto P y X están ambos vacíos, ya que D no es adyacente a A, así que {A, B, C} se informa como maximal.
3. Ramificar sobre B, con A ya en X. R pasa a ser {B}. P se reduce a C y D, ya que A se ha movido a X. Extendiendo se obtiene {B, C} y después {B, C, D}, porque C y D son adyacentes. Allí P y X están vacíos, así que {B, C, D} es maximal.
4. Por qué {B, C} no se informa. Cuando R es {B, C}, D sigue en P, así que la prueba de vacuidad falla y no se informa de ningún clique. Este es todo el propósito de esa prueba: {B, C} es un clique pero no maximal, porque queda dentro de {A, B, C} y de {B, C, D}.
5. La arista colgante. Ramificando hasta D con A, B y C ya agotados queda E como único candidato, dando {D, E}. E no tiene más vecinos, así que es maximal pese a tener solo dos vértices.

Los cliques maximales son {A, B, C}, {B, C, D} y {D, E}. El clique máximo, es decir el mayor, tiene tamaño 3 y hay dos de ellos. Fíjate en que maximal y máximo son distintos: {D, E} es maximal porque nada puede extenderlo, pero está lejos de ser máximo. Fíjate también en que B y C aparecen cada uno en dos cliques maximales, lo cual es normal y explica que el número de cliques maximales pueda superar con mucho al número de vértices.

Complejidad y de dónde sale

Tiempo: O(3^(V/3)) · Espacio: O(V^2)

La cota procede del teorema de Moon-Moser: un grafo de V vértices puede tener a lo sumo 3 elevado a V/3 cliques maximales, y esa cota es ajustada, alcanzada por un grafo multipartito completo de V/3 triángulos. Dado que el algoritmo debe como mínimo imprimir cada uno de ellos, ningún algoritmo de enumeración puede superarla en el peor caso, y Bron-Kerbosch con pivote la iguala. Merece la pena interiorizarlo: el algoritmo es óptimo, pero el problema en sí es exponencial. Hallar solo el clique más grande es NP-difícil, e incluso aproximarlo dentro de cualquier factor razonable resulta difícil. En la práctica, el pivote y una ordenación por degeneración hacen tratables los grafos dispersos reales de decenas de miles de vértices, porque los grafos dispersos tienen muchos menos cliques maximales que el peor caso.

Cuándo usar Cliques Maximales y cuándo no

Decide primero si quieres todos los cliques maximales o solo el mayor, porque son problemas distintos con herramientas distintas.

Errores frecuentes

• Prescindir del conjunto X. Sin X, el algoritmo informa de todos los cliques en lugar de solo los maximales, así que {B, C} aparecería junto a {A, B, C}. La salida se dispara y es incorrecta. X es lo que recuerda que una rama ya ha sido cubierta.
• Confundir maximal con máximo. Un clique maximal no puede extenderse; un clique máximo es el mayor del grafo. {D, E} en el ejemplo es maximal y tiene tamaño 2, mientras que el tamaño máximo es 3. Pedir el clique maximal es ambiguo y normalmente se refiere al máximo.
• Omitir el pivote en grafos densos. Bron-Kerbosch sin pivote explora enormemente más ramas. En grafos densos el pivote no es una optimización sino la diferencia entre terminar y no terminar.
• Esperar comportamiento polinómico. El número de cliques maximales puede ser exponencial en el número de vértices, así que ningún truco de implementación hace rápido el caso general. Si un grafo es denso y grande, enumera con un tope o reformula la pregunta.
• Tratar bucles propios o direcciones como significativos. Los cliques están definidos sobre grafos simples no dirigidos. Las aristas dirigidas deben simetrizarse primero, y hay que decidir si una arista de un solo sentido cuenta como adyacencia, porque esa elección cambia la respuesta.

Preguntas frecuentes

¿Qué es un clique maximal?

Un clique es un conjunto de vértices adyacentes entre sí dos a dos. Un clique es maximal cuando no puede añadirse ningún vértice más conservando esa propiedad. Esto es distinto de un clique máximo, que es el mayor del grafo: todo clique máximo es maximal, pero un clique maximal pequeño puede coexistir con otros mucho mayores.

¿Cómo funciona el algoritmo de Bron-Kerbosch?

Recurre sobre tres conjuntos: R, el clique construido hasta ahora, P, los candidatos que aún pueden extenderlo, y X, los vértices ya explorados en ese nivel. En cada paso mueve un candidato de P a R y restringe P y X a los vecinos de ese vértice. Cuando P y X están ambos vacíos, R es un clique maximal. Elegir un pivote y ramificar solo sobre sus no vecinos poda la mayor parte de la búsqueda.

¿Cuál es la diferencia entre clique maximal y máximo?

Maximal significa localmente inextensible: no puedes añadirle ningún vértice. Máximo significa globalmente el mayor: ningún clique del grafo tiene más vértices. Un grafo puede tener muchos cliques maximales de tamaños distintos, y hallarlos todos es un problema diferente de hallar el mayor.

¿Cuál es la complejidad temporal de hallar todos los cliques maximales?

O(3 elevado a V/3) en el peor caso, que es óptimo. Por el teorema de Moon-Moser un grafo puede contener esa cantidad de cliques maximales, así que cualquier algoritmo que los liste todos debe tardar al menos eso. En grafos dispersos, una ordenación por degeneración da una cota práctica mucho mejor.

¿Para qué se usan los cliques?

Para detección de comunidades en redes sociales, para hallar grupos de genes coexpresados en bioinformática, para identificar conjuntos de elementos mutuamente compatibles en planificación y recomendación, para detectar redes de fraude donde todas las partes operan entre sí, y para problemas de emparejamiento donde un clique representa un conjunto de elecciones plenamente consistente.