Utilisateur:Leothaud/Bron–Kerbosch algorithm
- (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).
En informatique, l'algorithme de Bron-Kerbosch est un algorithme d'énumération de recherche de cliques maximum dans un graphe non orienté. Cet algorithme consiste à lister tous les sous-ensembles de sommets qui engendrent un graphe complet tel qu'il soit impossible d'ajouter un sommet qui conserve cette propriété. L'algorithme Bron-Kerbosch a été inventé par des scientifiques allemands, Coenradd Bron et Joep Kerbosch, qui ont publié sa description en 1973.
Bien que d'autres algorithmes résolvant le problème de la clique aient en théorie, des temps d'exécution plus court pour des entrées ayant un faible nombre d'ensemble indépendant maximaux, l'algorithme de Bron-Kerbosch et ses améliorations sont souvent signalés comme étant plus efficaces en pratique. Il est bien connu et très utilisé parmi les algorithmes sur les graphes comme en chimie numérique.
Akkoyunlu a présenté en 1973 en différents termes un algorithme qui peut être vu comme le même algorithme que Bron-Kerbosch car il génère le même arbre de recherche.
Algorithme sans pivot[modifier | modifier le code]
La forme basique de l'algorithme de Bron-Kerbosch est un algorithme récursif de backtracking qui cherche toutes les cliques maximales d'un graphe G. Plus généralement, pour trois ensembles disjoints de sommets R, P et X, l'algorithme trouve les cliques maximales contenant tous les sommets de R, des sommets de P mais aucun sommet de X. A chaque appel de l'algorithme, P et X sont des ensembles disjoints tels que leur union est l'ensemble des sommets tel que R reste une clique si on lui en ajoute un. C'est à dire P ⋃ X est l'ensemble des sommets voisins de chaque sommet de R. Si P et X sont tous les deux vides, il n'y a plus d'éléments qui peuvent être ajouté à R donc R est une clique maximale et est renvoyé par l'algorithme.
Au premier appel, R et X sont des ensembles vides et P est l'ensemble des sommets du graphe. A chaque appel récursif, l'algorithme considère tous les sommets de P chacun leur tour, s'il n'y a pas de tel sommet, il déclare R comme clique maximale (si X est vide) ou il retourne en arrière. Pour chaque sommet s choisit dans P, l'algorithme effectue un appel récursif où s est ajouté à R et où P et X sont restreint à l'ensemble V(s) des voisins de s, afin de trouver toutes les cliques maximales qui sont extension de R contenant s. Puis il déplace s de P à X pour ne plus considérer ces cliques dans les futurs itérations et continue avec le prochain sommet de P.
Ce qui donne en pseudo-code :
Algorithme Bron-Kerbosch (P,X,R) :
Si P et X sont vides:
Déclarer R comme clique maximale
Pour chaque sommet s dans P faire:
BronKerbosch1(R ⋃ {s}, P ⋂ V(s), X ⋂ V(s))
P := P \ {s}
X := X ⋃ {s}
Algorithme avec pivot[modifier | modifier le code]
La forme basique de l'algorithme, décrite plus haut, est peu efficace dans le cas de graphes avec beaucoup de cliques non maximales. En effet, l'algorithme effectue un appel récursif pour chaque clique, qu'elle soit maximale ou non. Pour gagner du temps et permettre à l'algorithme de revenir en arrière plus vite dans les branches n'ayant pas de clique maximale, Bron et Kerbosch ont introduit une variante de l'algorithme avec un "sommet pivot" u, choisit dans P (ou plus généralement dans P⋃X). Toute clique maximale doit soit contenir u ou un sommet qui n'est pas un de ses voisins, sinon la clique pourrait être agrandit en lui ajoutant u. Par conséquent, seul u et les sommets qui ne lui sont pas voisins ont besoin d'être pris comme choix de sommet s qui sera ajouté à R dans les différents appel récursif de l'algorithme.
Ce qui donne en pseudo-code :
Algorithme BronKerboschPivot(R, P, X):
Si P et X sont vides:
Déclarer R comme clique maximale
Choisir un sommet u de (P ⋃ X) comme pivot
Pour chaque somme s dans P\ V(u):
BronKerboschPivot(R ⋃{s}, P ⋂ V(s), X ⋂ V(s))
P := P \ {s}
X := X ⋃ {s}
Si le pivot est choisi de manière à minimiser le nombre d'appels récursifs, l'économie en temps d'exécution comparé à l'algorithme sans pivot peut être importante.
Algorithme avec ordonnancement des sommets[modifier | modifier le code]
Une méthode alternative pour améliorer la forme basique de l'algorithme de Bron-Kerbosch est de ne pas choisir de pivot au moment de l'appel initial de l'algorithme mais à la place de faire les différents appels récursifs dans un ordre minimisant la taille des ensembles P de sommets candidats pour chaque appel récursif.
La dégénérescence d'un graphe G est le plus petit entier k tel que tout sous-graphe de G a un sommet de degré k ou moins. Chaque graphe a un ordre de dégénérescence, un ordre sur les sommets du graphe tel que chaque sommet a au plus k voisins qui arrivent plus tard dans l'ordre. L'ordre de dégénérescence peut être trouvé en temps linéaire en choisissant à chaque fois le sommet de degré minimal parmi les sommets restant. Si l'algorithme de Bron-Kerbosch considère les sommets du graphe dans l'ordre de dégénérescence, alors les ensembles P des sommets candidats à chaque appel est garantis de cardinal au plus k. L'ensemble X des sommets exclus sera constitué des voisins étant apparut plus tôt et pourra avoir un cardinal bien plus grand que k.Pour cela dans les prochains appel récursif, la version de l'algorithme avec choit de pivot peut être utilisé.
Ce qui donne en pseudo-code :
Algorithme BronKerboschOrdre(G):
P = S(G)
R = X = Ø
Pour chaque sommet s de G choisir selon l'ordre de dégénérescence:
BronKerboschPivot({s}, P ⋂ V(s), X⋂ V(s))
P := P \ {s}
X := X ⋃ {s}
Cette variante de l'algorithme peut être très efficace pour les graphes de dégénérescence faible et les expériences montrent qu'elle est également efficace en pratique dans grands réseaux sociaux peu dense et dans d'autres graphes du monde réel.
Un exemple[modifier | modifier le code]
Dans le graphe d'exemple montré ici, l'algorithme est initialement appelé avec:
R = Ø
P = {1,2,3,4,5,6}
X = Ø
Le pivot u doit être choisit parmi les sommets de degré 3 pour minimiser le nombre d'appels récursifs. Par exemple, supposons que u est choisit parmi le sommet 2. Alors il reste trois sommets dans P \ V(u) : les sommets 2, 4 et 6.
L'itération de la boucle de l'algorithme pour s=2 fait un appel récursif avec </nowiki>R''={2}, P={1,3,5} et X=Ø. Dans cet appel récursif, les pivots possibles sont 1 et 5 et il aura un nouvel appel récursif sur le sommet 3 ou sur le sommet qui n'a pas été choisit comme pivot. Ces deux appels vont éventuellement déclarer les cliques {1,2,5} et {2,3}. Après le retour de ses appels récursifs, le sommet 2 sera ajouté à X et enlevé de P.
L'itération de la boucle pour s=4 effectue un appel récursif avec R={4}, P={3,5,6} et X=Ø (bien que le sommet 2 devra être dans l'ensemble X à l'extérieur de l'appel de l'algorithme, ce n'est pas un voisin de s et est exclue des sous-ensemble de X utilisé pour l'appel récursif). Cet appel fera trois autres appels récursifs qui déclareront les cliques maximales {3,4}, {4,5} et {4,6}. Puis, le sommet 4 sera ajouté à X et retiré de P.
Dans la dernière itération de la boucle, pour s=6, il y a un appel récursif pour R={6}, P=Ø et X={4}. Puisque P est vide mais X ne l'est pas, l'algorithme retourne immédiatement en arrière sans déclarer aucune clique. En effet, il n'y a aucune clique maximale contenant le sommet 6 mais pas le sommet 4.
L'arbre d'appel de l'algorithme ressemble donc à cela :
BronKerboschPivot(Ø, {1, 2, 3, 4, 5, 6}, Ø)
BronKerboschPivot({2}, {1, 3, 5}, Ø)
BronKerboschPivot({2, 3}, Ø, Ø) : trouve la clique maximale {2, 3}
BronKerboschPivot({2, 5}, {1}, Ø)
BronKerboschPivot({1, 2, 5}, Ø, Ø) : trouve la clique maximale {1, 2, 5}
BronKerboschPivot({4}, {3, 5, 6}, Ø)
BronKerboschPivot({3, 4}, Ø, Ø) : trouve la clique {3, 4}
BronKerboschPivot({4, 5}, Ø, Ø) : trouve la clique {4, 5}
BronKerboschPivot({4, 6}, Ø, Ø) : trouve la clique {4, 6}
BronKerboschPivot({6}, Ø, {4}) : ne trouve rien
Le graphe de cet exemple a une dégénérescence de 2. Un ordre de dégénérescence possible est 6, 4, 3, 1, 2, 5. Si l'algorithme de Bron-Kerbosch avec ordonnancement des sommet est appliqué, l'arbre d'appel ressemblera à cela :
BronKerboschOrdre(G):
BronKerboschPivot({6}, {4}, Ø)
BronKerboschPivot({4, 6}, Ø, Ø) : trouve la clique maximale {4, 6}
BronKerboschPivot({4}, {3, 5}, {6})
BronKerboschPivot({3, 4}, Ø, Ø) : trouve la clique maximale {3, 4}
BronKerboschPivot({4, 5}, Ø, Ø) : trouve la clique maximale {4, 5}
BronKerboschPivot({3}, {2}, {4})
BronKerboschPivot({2, 3}, Ø, Ø) : trouve la clique maximale {2, 3}
BronKerboschPivot({1}, {2, 5}, Ø)
BronKerboschPivot({1, 2}, {5}, Ø)
BronKerboschPivot({1, 2, 5}, Ø, Ø) : trouve la clique maximale {1, 2, 5}
BronKerboschPivot({2}, {5}, {1,3}) : ne trouve rien
BronKerboschPivot({5}, Ø, {1, 2, 4}) : ne trouve rien
Analyse du pire cas[modifier | modifier le code]
L'algorithme de Bron-Kerbosch n'est pas un algorithme géométrique adaptatif:
Contrairement à d'autres algorithmes qui gèrent le problème de la clique, il ne s'exécute pas en un temps linéaire par rapport aux cliques maximales trouvées. Pourtant il est efficace dans le pire cas: D'après un résultat de Moom et Moser (1965), n'importe quel graphe de n sommets a au plus 3n/3 cliques maximales. Le pire cas d’exécution pour l'algorithme de Bron-Kerbosch (avec un choix de pivots qui minimise le nombre d'appel récursif à chaque étape ) a une complexité en O(3n/3), ce qui correspond à cette borne.
Pour les graphes peu dense, des bornes plus fines sont possibles. En particulier, l'algorithme de Bron-Kerbosch avec ordonnancement des sommet peut s'exécuter en un temps O(kn3k/3) où k est la dégénérescence , qui mesure si le graphe est peu dense. Il existe des graphes k-dégénéré qui ont un nombre total de cliques maximales de (n-k)3k'/3. La borne semble donc finie.
Notes[modifier | modifier le code]
Références[modifier | modifier le code]
(en) E. A. Akkoyunlu, « The Enumeration of Maximal Cliques of Large Graphs », SIAM Journal on Computing, vol. 2, no 1, , p. 1–6 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/0202001, lire en ligne)