Détecteur de Clique Maximale

Pseudocode

Bron-Kerbosch explore avec trois ensembles: R est la clique construite jusqu'ici, P contient les candidats susceptibles de l'étendre encore, et X contient les sommets déjà essayés. Une clique est maximale exactement lorsque P et X sont tous deux vides.

BronKerbosch(R, P, X):
    si P et X sont tous deux vides:
        signaler R comme clique maximale
        retourner

    pour chaque sommet v dans P:
        BronKerbosch(R + {v},
                     P inter voisins(v),
                     X inter voisins(v))
        P = P - {v}
        X = X + {v}

// Avec pivot: choisir un pivot u dans P union X et ne
// brancher que sur les v de P qui NE sont PAS voisins de u

X est la partie que l'on omet volontiers, et sans elle l'algorithme signale des cliques qui ne sont pas maximales. Dès qu'un sommet a été exploré à ce niveau, il passe dans X, si bien que toute clique qui aurait pu le contenir est rejetée comme non maximale. Le raffinement par pivot réduit ensuite fortement le facteur de branchement: toute clique maximale doit contenir le pivot ou l'un de ses non-voisins, brancher sur le reste est donc du travail perdu.

Exemple détaillé, étape par étape

Énumère toutes les cliques maximales d'un graphe à six arêtes contenant deux triangles qui se chevauchent et une arête pendante.

Graphe d'exemple: Arêtes non orientées A-B, A-C, B-C, B-D, C-D et D-E.

1. Départ. R est vide, P contient les cinq sommets, X est vide. Branche d'abord sur A.
2. Brancher sur A. R devient {A}. P se réduit aux voisins de A, soit B et C. Brancher sur B puis sur C construit {A, B} puis {A, B, C}. À ce point P et X sont tous deux vides, puisque D n'est pas adjacent à A, et {A, B, C} est signalée comme maximale.
3. Brancher sur B, A étant désormais dans X. R devient {B}. P se réduit à C et D, car A est passé dans X. L'extension donne {B, C} puis {B, C, D}, car C et D sont adjacents. Là, P et X sont vides, donc {B, C, D} est maximale.
4. Pourquoi {B, C} n est pas signalée. Lorsque R vaut {B, C}, D figure encore dans P, le test de vacuité échoue donc et aucune clique n'est signalée. C'est tout l'objet de ce test: {B, C} est une clique mais pas une clique maximale, puisqu'elle est incluse dans {A, B, C} et dans {B, C, D}.
5. L arête pendante. En descendant jusqu'à D alors que A, B et C sont épuisés, il ne reste que E comme candidat, ce qui donne {D, E}. E n'a aucun autre voisin, cette clique est donc maximale bien qu'elle ne compte que deux sommets.

Les cliques maximales sont {A, B, C}, {B, C, D} et {D, E}. La clique maximum, c'est-à-dire la plus grande, est de taille 3 et il en existe deux. Note que maximale et maximum diffèrent: {D, E} est maximale car rien ne peut l'étendre, mais elle est loin d'être maximum. Note aussi que B et C figurent chacun dans deux cliques maximales, ce qui est normal et explique que le nombre de cliques maximales puisse dépasser largement le nombre de sommets.

Complexité et son origine

Temps: O(3^(V/3)) · Espace: O(V^2)

La borne provient du théorème de Moon et Moser: un graphe à V sommets peut posséder au plus 3 puissance V/3 cliques maximales, et cette borne est atteinte, notamment par un graphe multiparti complet formé de V/3 triangles. Comme l'algorithme doit au minimum toutes les afficher, aucun algorithme d'énumération ne peut faire mieux au pire cas, et Bron-Kerbosch avec pivot l'égale. Cela mérite d'être intégré: l'algorithme est optimal, mais le problème lui-même est exponentiel. Trouver seulement la plus grande clique est NP-difficile, et même l'approcher à un facteur raisonnable près reste difficile. En pratique, le pivot et un ordre de dégénérescence rendent traitables les graphes creux réels de plusieurs dizaines de milliers de sommets, car les graphes creux comptent bien moins de cliques maximales que le pire cas.

Quand utiliser Clique Maximale, et quand l'éviter

Décide d'abord si tu veux toutes les cliques maximales ou seulement la plus grande, car ce sont des problèmes distincts avec des outils distincts.

Pièges fréquents

• Se passer de l ensemble X. Sans X, l'algorithme signale toutes les cliques au lieu des seules maximales, si bien que {B, C} apparaîtrait à côté de {A, B, C}. La sortie explose et devient fausse. X est ce qui garde en mémoire qu'une branche a déjà été couverte.
• Confondre maximale et maximum. Une clique maximale ne peut être étendue; une clique maximum est la plus grande du graphe. {D, E} dans l'exemple est maximale et de taille 2, alors que la taille maximum vaut 3. Demander la clique maximale est ambigu et désigne généralement la plus grande.
• Omettre le pivot sur les graphes denses. Bron-Kerbosch sans pivot explore énormément plus de branches. Sur les graphes denses, le pivot n'est pas une optimisation mais la différence entre terminer et ne pas terminer.
• Attendre un comportement polynomial. Le nombre de cliques maximales peut être exponentiel en le nombre de sommets, aucune astuce d'implémentation ne rend donc le cas général rapide. Si un graphe est dense et grand, énumère avec un plafond ou reformule la question.
• Traiter les boucles ou les orientations comme significatives. Les cliques sont définies sur des graphes simples non orientés. Les arêtes orientées doivent d'abord être symétrisées, et il faut décider si une arête à sens unique compte comme adjacence, car ce choix modifie la réponse.

Questions fréquentes

Qu'est-ce qu'une clique maximale?

Une clique est un ensemble de sommets deux à deux adjacents. Une clique est maximale lorsqu'aucun sommet supplémentaire ne peut être ajouté en conservant cette propriété. Cela diffère d'une clique maximum, la plus grande du graphe: toute clique maximum est maximale, mais une petite clique maximale peut coexister avec de bien plus grandes.

Comment fonctionne l'algorithme de Bron-Kerbosch?

Il récurre sur trois ensembles: R, la clique construite jusqu'ici, P, les candidats pouvant encore l'étendre, et X, les sommets déjà explorés à ce niveau. À chaque étape il déplace un candidat de P vers R et restreint P et X aux voisins de ce sommet. Lorsque P et X sont tous deux vides, R est une clique maximale. Choisir un pivot et ne brancher que sur ses non-voisins élague l'essentiel de la recherche.

Quelle est la différence entre clique maximale et maximum?

Maximale signifie localement non extensible: tu ne peux lui ajouter aucun sommet. Maximum signifie globalement la plus grande: aucune clique du graphe n'a plus de sommets. Un graphe peut posséder de nombreuses cliques maximales de tailles différentes, et les trouver toutes est un problème distinct de trouver la plus grande.

Quelle est la complexité temporelle pour trouver toutes les cliques maximales?

O(3 puissance V/3) au pire cas, ce qui est optimal. D'après le théorème de Moon et Moser, un graphe peut contenir autant de cliques maximales, tout algorithme qui les liste toutes doit donc prendre au moins ce temps. Sur les graphes creux, un ordre de dégénérescence fournit une borne pratique bien meilleure.

À quoi servent les cliques?

À la détection de communautés dans les réseaux sociaux, à la recherche de groupes de gènes co-exprimés en bio-informatique, à l'identification d'ensembles d'éléments mutuellement compatibles en ordonnancement et recommandation, à la détection de réseaux de fraude où toutes les parties transigent entre elles, et aux problèmes d'appariement où une clique représente un ensemble de choix pleinement cohérent.