Algorithme de Bron-Kerbosch

L'ensemble {1, 2, 5} est une clique maximale.

En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de sommets est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale). L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néerlandais Coenraad Bron (en) et Joep Kerbosch qui en ont publié la description en 1973^[1].

Bien que d'autres algorithmes aient en théorie de meilleures complexités pour résoudre le problème de la clique maximale sur des entrées qui ont un petit nombre d'ensembles indépendants, l'algorithme de Bron–Kerbosch (et ses améliorations) se révèlent souvent plus efficaces en pratique^[2]. C'est une des raisons qui font que cet algorithme est très populaire dans des domaines d'application tels que la chimie numérique^[3].

Un algorithme contemporain d'Akkoyunlu^[4] peut être considéré comme identique à l'algorithme de Bron–Kerbosch, quoique formulé différemment, car il génère le même arbre de recherche^[5].

Version sans pivot

Dans sa forme élémentaire, l'algorithme de Bron–Kerbosch est un algorithme de retour sur trace récursif qui cherche toutes les cliques maximales dans un graphe G. Plus précisément, étant donnés trois ensembles de sommets disjoints R, P et X, il cherche toutes les cliques maximales contenant tous les sommets de R, certains de P, mais aucun de X. Précisément :

L'ensemble R est un sous-ensemble des sommets de la potentielle clique.
L'ensemble P est l'ensemble des sommets candidats pour être ajoutés à la potentielle clique.
L'ensemble X contient des sommets déjà traités ou appartenant déjà à une clique maximale.

À chaque appel de l'algorithme, P et X sont des ensembles disjoints dont l'union forme des cliques lorsqu'on les ajoute à R. Autrement dit, P ⋃ X est l'ensemble des sommets qui sont connectés à tous les éléments de R. Quand P et X sont tous les deux vides, on ne peut plus ajouter d'éléments à R, qui est donc une clique maximale que l'algorithme retourne.

Au début, les ensembles R et X sont initialisés à l'ensemble vide alors que P est l'ensemble V des sommets du graphe. À chaque appel récursif, l'algorithme examine les sommets de P l'un après l'autre ; si P est vide, soit X est vide et R est renvoyé en tant que clique maximale, soit l'algorithme retourne sur ses traces. Pour chaque sommet v de P, l'algorithme fait un appel récursif dans lequel v est ajouté à R, et P et X sont restreints à l'ensemble des voisins N(v) de v ; cet appel renvoie toutes les extensions de cliques de R qui contiennent v. Puis v est déplacé de P à X pour que ce sommet ne soit plus pris en considération dans les futures cliques.

Voici le pseudo-code de l'algorithme :

algorithme BronKerbosch1(R, P, X)
    si P et X sont vides alors
        déclarer que R est une clique maximale
    pour tout sommet v dans P faire
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

BronKerbosch1(∅, V, ∅) //appel initial

Exemple

Un graphe comprenant 5 cliques maximales : 5 liens et le triangle 1-2-5.

Exécutons l'algorithme sur le graphe ci-contre.

BronKerbosch1(Ø, {1,2,3,4,5,6}, Ø)
         BronKerbosch1({1}, {2,5}, Ø)
               BronKerbosch1({1,2}, {5}, Ø) 
                         BronKerbosch1({1,2,5}, Ø, Ø) : sortie {1,2,5}
               P := {5}
               X := {2}
               BronKerbosch1({1,5}, Ø, {2})
         P := {2, 3, 4, 5, 6}
         X := {1}
         BronKerbosch1({2}, {3,5}, {1})
               BronKerbosch1({2,3},  Ø,  Ø) : sortie : {2,3}
               P := {3,5}
               X := {1,2}
               BronKerbosch1({2,5},  Ø,  Ø) : sortie : {2,5}
         P := {3, 4, 5, 6}
         X := {1, 2}
         BronKerbosch1({3}, {4}, Ø)
                  BronKerbosch1({3,4}, Ø, Ø) : sortie {3,4}
         P := {4, 5, 6}
         X := {1, 2, 3}
         BronKerbosch1({4}, {5,6}, {3})
                  BronKerbosch1({4,5}, Ø, Ø) : sortie {4,5}
                  BronKerbosch1({4,6}, Ø, Ø) : sortie {4,6}
         P := {5, 6}
         X := {1, 2, 3, 4}
         BronKerbosch1({5}, Ø, {2,4})
         P := {6}
         X := {1, 2, 3, 4, 5}
         BronKerbosch1({6}, Ø, {4})

Version avec pivot

La forme élémentaire de l'algorithme décrite ci-dessus est inefficace pour les graphes qui contiennent beaucoup de cliques non maximales car on effectue un appel récursif par clique, maximale ou non. Pour économiser du temps, Bron et Kerbosch ont introduit une version dite avec pivot. L'objectif est que l'algorithme retourne sur traces plus rapidement lorsqu'il parcourt des branches qui ne contiennent pas de cliques maximales.

Cette version utilise un « nœud pivot » u, choisi dans P ou plus généralement dans P ⋃ X, comme remarqué dans des travaux postérieurs^[6]. Toute clique maximale doit inclure soit u, soit un nœud non voisin de u, sans quoi la clique pourrait être agrandie en y ajoutant u^[pas clair]. Par conséquent, il n'est nécessaire de tester que u et l'ensemble des nœuds de P qui ne sont pas voisins de u en tant que nœud v qu'on tente d'ajouter à R à chaque appel récursif de l'algorithme.

Voici le pseudo-code correspondant :

algorithme BronKerbosch2(R, P, X)
    si P et X sont vides alors
        déclarer que R est une clique maximale
    choisir un sommet pivot u dans P ⋃ X
    pour tout sommet v dans P \ N(u) faire
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

Si le pivot est choisi de manière à minimiser le nombre d'appels récursifs réalisés par l'algorithme, les économies de temps de calcul par rapport à la version sans pivot peuvent être considérables^[7].

Version avec ordonnancement des nœuds

Une méthode alternative pour améliorer la forme élémentaire de l'algorithme de Bron–Kerbosch consiste à renoncer au pivot dans le niveau externe de la récursion, et choisir à la place d'ordonner les appels récursifs de manière à minimiser la taille des ensembles $P$ de sommets candidats dans chaque appel récursif.

La dégénérescence d'un graphe $G$ est le plus petit entier $d$ tel que tout sous-graphe de $G$ a un sommet de degré $d$ ou moins. Tout graphe de dégénérescence $d$ admet un ordre tel que chaque sommet a $d$ voisins ou moins situés après dans l'ordre. Un tel ordre, dit ordre de dégénérescence peut être trouvé en temps linéaire en sélectionnant itérativement le sommet de degré minimum parmi les sommets restants. Si l'algorithme de Bron–Kerbosch visite les sommets dans un ordre de dégénérescence, alors on peut garantir que l'ensemble $P$ des sommets candidats à chaque appel (les voisins de $v$ qui sont situés après dans l'ordre) est au plus de taille $d$ . L'ensemble $X$ des sommets exclus est constitué de tous les voisins de $v$ qui sont situés avant dans l'ordre et peut être bien plus grand que $d$ . En-dehors du niveau le plus élevé de la récursion, la version avec pivot vue précédemment peut être utilisée^[8]^,^[9].

Voici le pseudo-code correspondant :

algorithme BronKerbosch3(G)
    P = V(G)
    R = Ø
    X = Ø
    pour tout sommet v visités dans un ordre de dégénérescence de G faire
        BronKerbosch2({v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

On peut montrer que cette variante de l'algorithme est plus efficace pour les graphes de faible dégénérescence^[8] et des expériences montrent que l'algorithme est efficace en pratique pour les grands graphes peu denses issus de données réelles, tels que les graphes de réseaux sociaux^[9] .

Exemple

Un graphe comprenant 5 cliques maximales: 5 liens et un triangle.

Dans le graphe représenté, l'algorithme est appelé initialement avec R = Ø, P = {1,2,3,4,5,6}, et X = Ø. Le pivot u devrait être choisi parmi les nœuds de degré 3, pour minimiser le nombre d'appels récursifs. Supposons qu'on choisisse u comme étant le nœud 2, alors il reste 3 sommets dans P \ N(u): les nœuds 2 lui-même, 4 et 6.

L'itération de la boucle interne de l'algorithme pour v = 2 réalise un appel récursif avec R = {2}, P = {1,3,5} et X = Ø. Dans cet appel récursif, soit 1 soit 5 sera choisi comme pivot, et il y aura deux appels récursifs de second niveau, un pour le nœud 3 et un autre pour le nœud qui n'a pas été choisi comme pivot. Ces deux appels vont déclarer {1,2,5} et {2,3} comme cliques maximales. Après le retour de ces appels récursifs, 2 est ajouté à X et retiré de P.

L'itération de la boucle interne de l'algorithme pour v = 4 réalise un appel récursif avec R = {4}, P = {3,5,6} et X = Ø (on note que 2 appartient à X pour l'appel externe de l'algorithme, mais ce n'est pas un voisin de v et est exclu du sous-ensemble X passé en argument à l'appel récursif). Dans cet appel récursif, il y aura trois appels récursifs de second niveau, qui déclareront les cliques maximales {3,4}, {4,5} et {4,6}. Après le retour de ces appels récursifs, 4 est ajouté à X et retiré de P.

L'itération finale de la boucle interne de l'algorithme pour v = 6 réalise un appel récursif avec R = {6}, P = Ø et X = {4}. Comme cet appel récursif appelle sur des arguments P vide et X non-vide, il retourne immédiatement sur traces sans reporter de cliques maximales supplémentaires, puisqu'aucune clique maximale peut inclure le nœud 6 et exclure le nœud 4.

L'arbre des appels pour l'algorithme est alors :

BronKerbosch2(Ø, {1,2,3,4,5,6}, Ø)
    BronKerbosch2({2}, {1,3,5}, Ø)
        BronKerbosch2({2,3}, Ø, Ø): sortie {2, 3}
        BronKerbosch2({2,5}, {1}, Ø)
            BronKerbosch2({1,2,5}, Ø, Ø): sortie {1,2,5}
    BronKerbosch2({4}, {3,5,6}, Ø)
        BronKerbosch2({3,4}, Ø, Ø): sortie {3,4}
        BronKerbosch2({4,5}, Ø, Ø): sortie {4,5}
        BronKerbosch2({4,6}, Ø, Ø): sortie {4,6}
    BronKerbosch2({6}, Ø, {4}): pas de sortie

Le graphe de l'exemple a une dégénérescence de deux, un ordre de dégénérescence possible est 6,4,3,1,2,5. Avec un tel ordre sur les nœuds, la trace des appels pour la version correspondante de l'algorithme de Bron–Kerbosch est :

BronKerbosch3(G)
    BronKerbosch2({6}, {4}, Ø)
        BronKerbosch2({6,4}, Ø, Ø): sortie {6,4}
    BronKerbosch2({4}, {3,5}, {6})
        BronKerbosch2({4,3}, Ø, Ø): sortie {4,3}
        BronKerbosch2({4,5}, Ø, Ø): sortie {4,5}
    BronKerbosch2({3}, {2}, {4})
        BronKerbosch2({3,2}, Ø, Ø): sortie {3,2}
    BronKerbosch2({1}, {2,5}, Ø)
        BronKerbosch2({1,2}, {5}, Ø)
            BronKerbosch2({1,2,5}, Ø, Ø): sortie {1,2,5}
    BronKerbosch2({2}, {5}, {1,3}): pas de sortie
    BronKerbosch2({5}, Ø, {1,2,4}): pas de sortie

Analyse dans le pire cas

L'algorithme de Bron–Kerbosch n'est pas sensible à la taille de la sortie et contrairement à d'autres algorithmes pour résoudre le problème de la clique, sa complexité n'est pas en temps polynomial par clique maximale générée. Cependant, d'après un résultat issu de Moon et Moser 1965, il est efficace dans le pire cas, dans le sens où tout graphe à n nœuds contient au plus 3^n/3 cliques maximales et la complexité pire cas de l'algorithme de Bron–Kerbosch avec la stratégie du pivot qui minimise le nombre d'appels récursifs réalisés à chaque étape est en O(3^n/3), atteignant donc la borne^[10].

Pour les graphes peu denses, des bornes plus serrées sont possibles. En particulier, dans la version de Bron–Kerbosch utilisant l'ordre de dégénérescence, l'algorithme peut être réalisé en $O(dn 3 d /3)$ , où $d$ est la dégénérescence du graphe, que l'on peut comprendre comme une mesure de sa densité. Il existe des graphes de dégénérescence $d$ pour lesquels le nombre total de cliques maximales est $(n - d)3 d /3$ , donc cette borne peut être serrée^[8].

Notes

↑ Coen Bron et Joep Kerbosch, « Algorithm 457: finding all cliques of an undirected graph », Communications of the ACM, vol. 16, n^o 9,‎ 1^er septembre 1973, p. 575–577 (ISSN 0001-0782, DOI 10.1145/362342.362367, lire en ligne, consulté le 30 août 2023)
↑ Cazals et Karande 2008.
↑ Chen 2004.
↑ Akkoyunlu 1973.
↑ Johnston 1976.
↑ Tomita, Tanaka et Takahashi 2006; Cazals et Karande 2008.
↑ Johnston 1976; Koch 2001; Cazals et Karande 2008.
↑ ^{a b et c} Eppstein, Löffler et Strash 2010.
↑ ^{a et b} Eppstein et Strash 2011.
↑ Tomita, Tanaka et Takahashi 2006.

Références

E. A. Akkoyunlu, « The enumeration of maximal cliques of large graphs », SIAM Journal on Computing, vol. 2,‎ 1973, p. 1–6 (DOI 10.1137/0202001).
Lingran Chen (dir.), Computational Medicinal Chemistry for Drug Discovery : Substructure and maximal common substructure searching, CRC Press, 2004, 483–514 p. (ISBN 978-0-8247-4774-9).
Coenraad Bron et Joep Kerbosch, « Algorithm 457: finding all cliques of an undirected graph », Commun. ACM, ACM, vol. 16, n^o 9,‎ 1973, p. 575–577 (DOI 10.1145/362342.362367).
F. Cazals et C. Karande, « A note on the problem of reporting maximal cliques », Theoretical Computer Science, vol. 407, n^o 1,‎ 2008, p. 564–568 (DOI 10.1016/j.tcs.2008.05.010, lire en ligne).
David Eppstein (dir.), Maarten Löffler (dir.) et Darren Strash (dir.), « 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea : Listing all maximal cliques in sparse graphs in near-optimal time », Lecture Notes in Computer Science, Springer-Verlag, vol. 6506,‎ 2010, p. 403–414 (DOI 10.1007/978-3-642-17517-6_36, arXiv 1006.5440).
David Eppstein et Darren Strash, « Listing all maximal cliques in large sparse real-world graphs », Journal of Experimental Algorithmics,‎ 2013 (Bibcode 2011arXiv1103.0318E, arXiv 1103.0318).
H. C. Johnston, « Cliques of a graph—variations on the Bron–Kerbosch algorithm », International Journal of Parallel Programming, vol. 5, n^o 3,‎ 1976, p. 209–238 (DOI 10.1007/BF00991836).
Ina Koch, « Enumerating all connected maximal common subgraphs in two graphs », Theoretical Computer Science, vol. 250, n^os 1–2,‎ 2001, p. 1–30 (DOI 10.1016/S0304-3975(00)00286-3).
J. W. Moon et L. Moser, « On cliques in graphs », Israel J. Math., vol. 3,‎ 1965, p. 23–28 (DOI 10.1007/BF02760024, MR 0182577).
Etsuji Tomita, Akira Tanaka et Haruhisa Takahashi, « The worst-case time complexity for generating all maximal cliques and computational experiments », Theoretical Computer Science, vol. 363, n^o 1,‎ 2006, p. 28–42 (DOI 10.1016/j.tcs.2006.06.015).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bron-Kerbosch algorithm » (voir la liste des auteurs).

Liens externes

Review of the Bron-Kerbosch algorithm and variations par Alessio Conte.
Bron-Kerbosh algorithm implementation in Python
Bron-Kerbosh algorithm with vertex ordering implementation in Python
Bron-Kerbosh algorithm implementation in C++
C++ implementation of the algorithms presented in Eppstein, Strash (2011) par Darren Strash.
Bron-Kerbosh, algorithms implementation in PHP, library with composer install par Sergio Zambrano.

[1] Coen Bron et Joep Kerbosch, « Algorithm 457: finding all cliques of an undirected graph », Communications of the ACM, vol. 16, n^o 9,‎ 1^er septembre 1973, p. 575–577 (ISSN 0001-0782, DOI 10.1145/362342.362367, lire en ligne, consulté le 30 août 2023)

[2] Cazals et Karande 2008.

[3] Chen 2004.

[4] Akkoyunlu 1973.

[5] Johnston 1976.

[6] Tomita, Tanaka et Takahashi 2006; Cazals et Karande 2008.

[7] Johnston 1976; Koch 2001; Cazals et Karande 2008.

[els-8] {a b et c} Eppstein, Löffler et Strash 2010.

[es-9] {a et b} Eppstein et Strash 2011.

[10] Tomita, Tanaka et Takahashi 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]