Algorytm Brona-Kerboscha

W informatyce algorytm Brona-Kerboscha jest algorytmem wyliczania służącym do znajdowania wszystkich maksymalnych klik w grafie nieskierowanym . Oznacza to, że wymienia wszystkie podzbiory wierzchołków z dwiema właściwościami, że każda para wierzchołków w jednym z wymienionych podzbiorów jest połączona krawędzią, a żaden z wymienionych podzbiorów nie może mieć dodanych dodatkowych wierzchołków przy zachowaniu pełnej łączności . Algorytm Brona-Kerboscha został zaprojektowany przez holenderskich naukowców Coenraada Brona i Joepa Kerboscha, którzy opublikowali jego opis w 1973 roku.

Chociaż inne algorytmy rozwiązywania problemu kliki mają teoretycznie lepsze czasy działania na danych wejściowych, które mają kilka maksymalnych niezależnych zestawów, algorytm Brona-Kerboscha i późniejsze jego ulepszenia są często zgłaszane jako bardziej wydajne w praktyce niż alternatywy. Jest dobrze znany i szeroko stosowany w obszarach zastosowań algorytmów grafowych , takich jak chemia obliczeniowa .

Współczesny algorytm Akkoyunlu (1973) , chociaż przedstawiony w innych terminach, może być postrzegany jako taki sam jak algorytm Brona-Kerboscha, ponieważ generuje to samo drzewo wyszukiwania.

Bez obracania

Podstawową formą algorytmu Brona-Kerboscha jest rekurencyjny algorytm śledzenia wstecznego , który wyszukuje wszystkie maksymalne kliki w danym grafie G . Mówiąc bardziej ogólnie, mając trzy rozłączne zbiory wierzchołków R , P i X , znajduje maksymalne kliki, które obejmują wszystkie wierzchołki w R , niektóre wierzchołki w P i żaden z wierzchołków w X . W każdym wywołaniu algorytmu P i X są zbiorami rozłącznymi, których suma składa się z tych wierzchołków, które po dodaniu do R tworzą kliki . Innymi słowy, P ∪ X jest zbiorem wierzchołków, które są połączone z każdym elementem R . Kiedy P , jak i X są puste, nie ma dalszych elementów, które można dodać do R , więc R jest maksymalną kliką, a algorytm zwraca R.

Rekurencja jest inicjowana przez ustawienie R i X na zbiór pusty , a P na zbiór wierzchołków grafu. W ramach każdego wywołania rekurencyjnego algorytm uwzględnia po kolei wierzchołki w P ; jeśli nie ma takich wierzchołków, albo zgłasza R jako maksymalną klikę (jeśli X jest pusty), albo cofa się. Dla każdego wierzchołka v wybranego z P wykonuje wywołanie rekurencyjne, w którym v jest dodawane do R i w którym P i X są ograniczone do sąsiedniego zbioru N(v) z v , który znajduje i zgłasza wszystkie rozszerzenia kliki R zawierające w . Następnie przesuwa v z P do X , aby wykluczyć go z rozważań w przyszłych klikach i kontynuuje z następnym wierzchołkiem w P .

Oznacza to, że w pseudokodzie algorytm wykonuje następujące kroki:

           algorytm  BronKerbosch1(R, P, X)  polega na tym  , że jeśli oba   P  i  X  są puste  , to  podaj  R  jako maksymalną klikę  dla każdego  wierzchołka  v  w  P  do  BronKerbosch1(  R  ⋃ {  v  },  P  ⋂  N  (  v  ),  X  ⋂  N  (  v  ))  P  :=  P  \ {  v  }  X  :=  X  ⋃ {  v  }

Z obracaniem

Opisana powyżej podstawowa postać algorytmu jest nieefektywna w przypadku grafów z wieloma niemaksymalnymi klikami: wykonuje wywołanie rekurencyjne dla każdej kliki, maksymalnej lub nie. Aby zaoszczędzić czas i umożliwić algorytmowi szybsze wycofywanie się w gałęziach wyszukiwania, które nie zawierają maksymalnych klik, Bron i Kerbosch wprowadzili wariant algorytmu obejmujący „wierzchołek obrotowy” u, wybrany z P (lub bardziej ogólnie , jak późniejsi badacze zrealizowane, z P ⋃ X ). Każda maksymalna klika musi zawierać albo u , albo jednego z jej nie-sąsiadów, w przeciwnym razie klikę można by powiększyć, dodając do niej u . Dlatego tylko u i jego nie-sąsiedzi muszą być testowane jako wybory dla wierzchołka v , który jest dodawany do R w każdym rekurencyjnym wywołaniu algorytmu. W pseudokodzie: 

     
       algorytm  BronKerbosch2(R, P, X)  jest  taki, że jeśli oba   P  i  X  są puste  , to  podaj  R  jako maksymalną klikę wybierz wierzchołek osi  u  w  P  ⋃  X  dla każdego  wierzchołka  v  w  P  \ N(  u  )  do  BronKerbosch2(  R  ⋃ {  v  },  P  ⋂ N(  v  ), X ⋂ N (  v  ))  P  :=  P  \ {  v  }  X  :=  X  ⋃ {  v  }

Jeśli zostanie wybrany obrót, aby zminimalizować liczbę wywołań rekurencyjnych wykonywanych przez algorytm, oszczędności czasu działania w porównaniu z wersją algorytmu nieobracającą się mogą być znaczne.

Z porządkowaniem wierzchołków

Alternatywna metoda ulepszenia podstawowej postaci algorytmu Brona-Kerboscha polega na rezygnacji z obracania na najbardziej zewnętrznym poziomie rekurencji i zamiast tego na ostrożnym wybraniu kolejności wywołań rekurencyjnych w celu zminimalizowania rozmiarów zbiorów P kandydujących wierzchołków w każdym rekurencyjnym dzwonić.

Degeneracją grafu G jest najmniejsza liczba d taka, że ​​każdy podgraf G ma wierzchołek o stopniu d lub mniejszym . Każdy graf ma uporządkowanie degeneracyjne , takie uporządkowanie wierzchołków, że każdy wierzchołek ma d lub mniej sąsiadów , którzy pojawiają się później w kolejności; uporządkowanie degeneracji można znaleźć w czasie liniowym , wybierając wielokrotnie wierzchołek o minimalnym stopniu spośród pozostałych wierzchołków. Jeśli kolejność wierzchołków v , przez którą przechodzi algorytm Brona-Kerboscha, jest porządkiem degeneracyjnym, to zbiór P kandydujących wierzchołków w każdym wywołaniu (sąsiedzi v , którzy są później w kolejności) będzie miał co najwyżej rozmiar re . Zbiór X wykluczonych wierzchołków będzie się składał ze wszystkich wcześniejszych sąsiadów v i może być znacznie większy niż d . W rekurencyjnych wywołaniach algorytmu poniżej najwyższego poziomu rekurencji nadal można używać wersji przestawnej.

W pseudokodzie algorytm wykonuje następujące kroki:

      algorytm  BronKerbosch3(G)  to  P  = V(  G  )  R  = X = pusty  dla każdego  wierzchołka  v  w uporządkowaniu degeneracyjnym  G  do  BronKerbosch2({  v  },  P  ⋂ N(  v  ), X ⋂ N(  v  ))  P  : =  P.  \ {  v  }  X  :=  X  ⋃ {  v  }

Można udowodnić, że ten wariant algorytmu jest skuteczny w przypadku grafów o małej degeneracji, a eksperymenty pokazują, że sprawdza się on również w praktyce w przypadku dużych, rzadkich sieci społecznościowych i innych grafów w świecie rzeczywistym.

Przykład

Wykres z pięcioma maksymalnymi klikami: czterema krawędziami i trójkątem

Na pokazanym przykładowym wykresie algorytm jest początkowo wywoływany z R = Ř, P = {1,2,3,4,5,6} i X = Ř. Pivot u powinien być wybrany jako jeden z wierzchołków trzeciego stopnia, aby zminimalizować liczbę wywołań rekurencyjnych; załóżmy na przykład, że u jako wierzchołek 2. Wtedy w P \ N ( u ) pozostały trzy wierzchołki : wierzchołki 2, 4 i 6.

Iteracja wewnętrznej pętli algorytmu dla v = 2 powoduje rekurencyjne wywołanie algorytmu z R = {2}, P = {1,3,5} i X = Ø. W ramach tego wywołania rekurencyjnego jedno z 1 lub 5 zostanie wybrane jako oś obrotu, a będą dwa wywołania rekurencyjne drugiego poziomu, jedno dla wierzchołka 3, a drugie dla wierzchołka, który nie został wybrany jako oś obrotu. Te dwa wywołania ostatecznie zgłoszą dwie kliki {1,2,5} i {2,3}. Po powrocie z tych wywołań rekurencyjnych wierzchołek 2 jest dodawany do X i usuwany z P .

Iteracja wewnętrznej pętli algorytmu dla v = 4 powoduje rekurencyjne wywołanie algorytmu z R = {4}, P = {3,5,6} i X = Ø (chociaż wierzchołek 2 należy do zbioru X w zewnętrznym wywołaniu algorytmu nie jest sąsiadem v i jest wykluczony z podzbioru X przekazanego do wywołania rekurencyjnego). To wywołanie rekurencyjne zakończy się wykonaniem trzech wywołań rekurencyjnych drugiego poziomu do algorytmu, który zgłasza trzy kliki {3,4}, {4,5} i {4,6}. Następnie wierzchołek 4 jest dodawany do X i usuwany z P .

W trzeciej i ostatniej iteracji wewnętrznej pętli algorytmu, dla v = 6, następuje rekurencyjne wywołanie algorytmu z R = {6}, P = Ø i X = {4}. Ponieważ to wywołanie rekurencyjne ma P puste, a X niepuste, natychmiast cofa się bez zgłaszania więcej klik, ponieważ nie może być maksymalnej kliki, która zawiera wierzchołek 6 i wyklucza wierzchołek 4.

Drzewo wywołań algorytmu wygląda zatem następująco:

BronKerbosch2(Ř, {1,2,3,4,5,6}, Ř) BronKerbosch2({2}, {1,3,5}, Ř) BronKerbosch2({2,3}, Ř, Ř): wynik {2, 3} BronKerbosch2({2,5}, {1}, Ř) BronKerbosch2({1,2,5}, Ř, Ř): wynik {1,2,5} BronKerbosch2({4}, {3 ,5,6}, Ř) BronKerbosch2({3,4}, Ř, Ř): wynik {3,4} BronKerbosch2({4,5}, Ř, Ř): wynik {4,5} BronKerbosch2({4 ,6}, Ř, Ř): wynik {4,6} BronKerbosch2({6}, Ř, {4}): brak wyniku

Wykres w przykładzie ma degenerację 2; jeden możliwy porządek degeneracji to 6,4,3,1,2,5. Jeśli wersja algorytmu Brona-Kerboscha z porządkowaniem wierzchołków zostanie zastosowana do wierzchołków, w tej kolejności, drzewo wywołań wygląda następująco

BronKerbosch3(G) BronKerbosch2({6}, {4}, Ř) BronKerbosch2({6,4}, Ř, Ř): wyjście {6,4} BronKerbosch2({4}, {3,5}, {6} ) BronKerbosch2({4,3}, Ř, Ř): wynik {4,3} BronKerbosch2({4,5}, Ř, Ř): wynik {4,5} BronKerbosch2({3}, {2}, { 4}) BronKerbosch2({3,2}, Ř, Ř): wyjście {3,2} BronKerbosch2({1}, {2,5}, Ř) BronKerbosch2({1,2}, {5}, Ř) BronKerbosch2({1,2,5}, Ř, Ř): wynik {1,2,5} BronKerbosch2({2}, {5}, {1,3}): brak wyniku BronKerbosch2({5}, Ř, {1,2,4}): brak danych wyjściowych

Analiza najgorszego przypadku

Algorytm Brona-Kerboscha nie jest algorytmem wrażliwym na dane wyjściowe : w przeciwieństwie do niektórych innych algorytmów problemu kliki, nie działa w czasie wielomianowym na maksymalną wygenerowaną klikę. Jest jednak skuteczny w najgorszym przypadku: zgodnie z wynikiem Moona i Mosera (1965) każdy wykres n -wierzchołków ma co najwyżej 3 n / 3 maksymalne kliki, a najgorszy przypadek czasu działania Brona – Kerboscha Algorytm (ze strategią przestawną, która minimalizuje liczbę wywołań rekurencyjnych wykonywanych na każdym kroku) to O(3 n /3 ), co odpowiada tej granicy.

W przypadku grafów rzadkich możliwe są ściślejsze granice. W szczególności wersja algorytmu Brona-Kerboscha z porządkowaniem wierzchołków może działać w czasie O ( dn 3 d / 3 ) , gdzie d jest degeneracją grafu, miarą jego rzadkości. Istnieją d -zdegenerowane, dla których całkowita liczba maksymalnych klik wynosi ( n − d )3 d /3 , więc ta granica jest bliska ścisłej.

Notatki

  • Akkoyunlu, EA (1973), „Wyliczenie maksymalnych klik dużych grafów”, SIAM Journal on Computing , 2 : 1–6, doi : 10.1137/0202001 .
  •   Chen, Lingran (2004), „Podstruktura i maksymalne wspólne wyszukiwanie podstruktur”, w Bultinck, Patrick (red.), Computational Medicinal Chemistry for Drug Discovery , CRC Press, s. 483–514, ISBN 978-0-8247-4774- 9 .
  • Bron, Coen; Kerbosch, Joep (1973), „Algorytm 457: znajdowanie wszystkich klik nieskierowanego wykresu”, Communications of the ACM , 16 (9): 575–577, doi : 10,1145 / 362342,362367 .
  • Cazals, F.; Karande, C. (2008), „Uwaga na temat problemu zgłaszania maksymalnych klik”, Theoretical Computer Science , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010 .
  • Eppstein, David ; Löffler, Maarten; Strash, Darren (2010), „Lista wszystkich maksymalnych klik na rzadkich wykresach w czasie zbliżonym do optymalnego”, w: Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (red.), 21. Międzynarodowe Sympozjum Algorytmów i Obliczeń (ISAAC 2010), Jeju, Korea , Notatki z wykładów z informatyki, tom. 6506, Springer-Verlag, s. 403–414, arXiv : 1006.5440 , doi : 10.1007/978-3-642-17517-6_36 .
  • Eppstein, David ; Strash, Darren (2011), „Listing all maximal cliques in large rzadkie wykresy świata rzeczywistego”, 10th International Symposium on Experimental Algorithms , arXiv : 1103.0318 , Bibcode : 2011arXiv1103.0318E .
  • Johnston, HC (1976), „Kliki wykresu - wariacje na temat algorytmu Brona-Kerboscha”, International Journal of Parallel Programming , 5 (3): 209–238, doi : 10.1007 / BF00991836 .
  • Koch, Ina (2001), „Wyliczanie wszystkich połączonych maksymalnych wspólnych podgrafów na dwóch grafach”, Theoretical Computer Science , 250 (1–2): 1–30, doi : 10.1016 / S0304-3975 (00) 00286-3 .
  •   Księżyc, JW; Moser, L. (1965), „O klikach na wykresach”, Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 .
  • Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), „Najgorszy przypadek złożoności czasowej do generowania wszystkich maksymalnych klik i eksperymentów obliczeniowych”, Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016 / j.tcs.2006.06.015 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Bron–Kerbosch_algorithm&oldid=1110744344 ”