Bron – Kerboschův algoritmus - Bron–Kerbosch algorithm

v počítačová věda, Bron – Kerboschův algoritmus je enumerační algoritmus pro nalezení všech maximálních kliky v neorientovaném graf. To znamená, že obsahuje seznam všech podmnožin vrcholů se dvěma vlastnostmi, které každá dvojice vrcholů v jedné z uvedených podmnožin spojuje hrana, a žádná uvedená podmnožina nemůže mít k sobě přidané žádné další vrcholy při zachování svého kompletní konektivita. Algoritmus Bron – Kerbosch navrhl holandský vědci Coenraad Bron a Joep Kerbosch, který jeho popis publikoval v roce 1973. Ačkoli jiné algoritmy pro řešení klika problém mají provozní časy, které jsou teoreticky lepší na vstupech, které mají několik maximálních nezávislých sad, algoritmus Bron – Kerbosch a jeho následná vylepšení jsou často uváděny jako efektivnější v praxi než alternativy.[1] Je dobře známý a široce používaný v aplikačních oblastech grafových algoritmů, jako je výpočetní chemie.[2]

Soudobý algoritmus Akkoyunlu (1973), i když jsou prezentovány různými termíny, lze je považovat za stejné jako Bron-Kerboschův algoritmus, protože generuje stejný rekurzivní vyhledávací strom.[3]

Bez otáčení

Základní formou Bron-Kerboschova algoritmu je a rekurzivní ustoupit algoritmus, který vyhledává všechny maximální kliky v daném grafu G. Obecněji řečeno, vzhledem k třem nesouvislým sadám vrcholů R, P, a X, najde maximální kliky, které zahrnují všechny vrcholy v R, některé vrcholy v Pa žádný z vrcholů v X. Při každém volání algoritmu P a X jsou disjunktní sady, jejichž sjednocení se skládá z těch vrcholů, které po přidání tvoří kliky R. Jinými slovy, P ∪ X je sada vrcholů, které jsou spojeny se všemi prvky R. Když P a X jsou prázdné, neexistují žádné další prvky, do kterých lze přidat R, takže R je maximální klika a algoritmus vydává R.

Rekurze je zahájena nastavením R a X být prázdná sada a P být vrcholovou sadou grafu. V rámci každého rekurzivního volání algoritmus bere v úvahu vrcholy P podle pořadí; pokud takové vrcholy nejsou, buď se hlásí R jako maximální klika (pokud X je prázdný), nebo ústupky. Pro každý vrchol proti vybráno z P, provede rekurzivní volání, ve kterém proti je přidán do R a ve kterém P a X jsou omezeny na sadu sousedů N (v) z proti, který vyhledá a nahlásí všechna rozšíření kliků z R které obsahují proti. Pak se to pohne proti z P na X vyloučit to z uvažování v budoucích klikách a pokračovat dalším vrcholem v P.

To znamená, že v pseudokódu provede algoritmus následující kroky:

algoritmus BronKerbosch1 (R, P, X) je    -li P a X jsou prázdné pak        zpráva R jako maximální klika pro každého vrchol proti v P dělat        BronKerbosch1 (R ⋃ {proti}, P ⋂ N(proti), X ⋂ N(proti))        P := P  {proti}        X := X ⋃ {proti}

Otočné

Základní forma algoritmu, popsaná výše, je neefektivní v případě grafů s mnoha non-maximálními klikami: provádí rekurzivní volání pro každou, maximální nebo ne. Aby ušetřili čas a umožnili algoritmu rychlejší návrat zpět ve větvích vyhledávání, které neobsahují žádné maximální kliky, představili Bron a Kerbosch variantu algoritmu zahrnující „pivotní vrchol“ u, vybráno z P (nebo obecněji, jak si pozdější vyšetřovatelé uvědomili,[4] z P ⋃ X). Každá maximální klika musí obsahovat buď u nebo jeden z jeho sousedů, protože jinak by se klika mohla rozšířit přidáním u k tomu. Proto pouze u a jeho nesousedé musí být testovány jako volby pro vrchol proti který je přidán do R v každém rekurzivním volání algoritmu. V pseudokódu:

algoritmus BronKerbosch2 (R, P, X) je    -li P a X jsou prázdné pak        zpráva R jako maximální klika vyberte vrchol pivot u v P ⋃ X    pro každého vrchol proti v P  N (u) dělat        BronKerbosch2 (R ⋃ {proti}, P ⋂ N (proti), X ⋂ N (proti))        P := P  {proti}        X := X ⋃ {proti}

Pokud je pivot zvolen tak, aby se minimalizoval počet rekurzivních volání provedených algoritmem, může být úspora v době běhu ve srovnání s neotáčivou verzí algoritmu významná.[5]

S objednáváním vrcholů

Alternativní metoda pro zlepšení základní formy algoritmu Bron – Kerbosch zahrnuje vzdání se otáčení na nejvzdálenější úrovni rekurze a místo toho pečlivou volbu uspořádání rekurzivních volání, aby se minimalizovala velikost množin P kandidátských vrcholů v rámci každého rekurzivního volání.

The zvrhlost grafu G je nejmenší číslo d takové, že každý podgraf z G má vrchol s stupeň d nebo méně. Každý graf má a objednávání degenerace, uspořádání vrcholů tak, že každý vrchol má d nebo méně sousedé které přicházejí později v objednávce; uspořádání degenerace lze nalézt v lineární čas opakovaným výběrem vrcholu minimálního stupně mezi zbývajícími vrcholy. Pokud je pořadí vrcholů proti skrz který prochází Bron-Kerboschův algoritmus, je pořadí degenerace, pak množina P kandidátských vrcholů v každém hovoru (sousedé z proti bude zaručeno, že budou mít velikost maximálněd. Sada X vyloučených vrcholů se bude skládat ze všech dřívějších sousedů protia může být mnohem větší nežd. V rekurzivních voláních algoritmu pod nejvyšší úrovní rekurze lze stále používat otočnou verzi.[6][7]

V pseudokódu provede algoritmus následující kroky:

algoritmus BronKerbosch3 (G) je    P = V (G)    R = X = prázdný pro každého vrchol proti v pořadí degenerace G dělat        BronKerbosch2 ({proti}, P ⋂ N (proti), X ⋂ N (proti))        P := P  {proti}        X := X ⋃ {proti}

Tuto variantu algoritmu lze prokázat jako efektivní pro grafy malé degenerace,[6] a experimenty ukazují, že to dobře funguje i v praxi u velkých řídkých sociální sítě a další reálné grafy.[7]

Příklad

Graf s pěti maximálními klikami: čtyřmi hranami a trojúhelníkem

V ukázkovém grafu je algoritmus zpočátku volán pomocí R = Ø, P = {1,2,3,4,5,6} a X = Ø. Otočný čep u by měl být zvolen jako jeden z vrcholů stupně tři, aby se minimalizoval počet rekurzivních hovorů; předpokládejme například, že u je zvolen jako vrchol 2. Pak jsou v něm tři zbývající vrcholy P  N(u): vrcholy 2, 4 a 6.

Iterace vnitřní smyčky algoritmu pro proti = 2 provede rekurzivní volání algoritmu pomocí R = {2}, P = {1,3,5} a X = Ø. V rámci tohoto rekurzivního volání bude jedno z 5 nebo 5 vybráno jako pivot a budou zde dvě rekurzivní volání druhé úrovně, jedno pro vrchol 3 a druhé pro libovolný vrchol, který nebyl vybrán jako pivot. Tyto dva hovory nakonec nahlásí dvě kliky {1,2,5} a {2,3}. Po návratu z těchto rekurzivních hovorů se přidá vrchol 2 X a odstraněny z P.

Iterace vnitřní smyčky algoritmu pro proti = 4 provede rekurzivní volání algoritmu s R = {4}, P = {3,5,6} a X = Ø (ačkoli vrchol 2 patří do množiny X ve vnějším volání algoritmu není sousedem proti a je vyloučen z podmnožiny X předáno rekurzivnímu volání). Toto rekurzivní volání skončí provedením tří rekurzivních volání druhé úrovně algoritmu, který hlásí tři kliky {3,4}, {4,5} a {4,6}. Poté se k vrcholu přidá vrchol 4 X a odstraněny z P.

Ve třetí a poslední iteraci vnitřní smyčky algoritmu pro proti = 6, existuje rekurzivní volání algoritmu s R = {6}, P = Ø a X = {4}. Protože toto rekurzivní volání má P prázdné a X neprázdný, okamžitě se vrátí zpět, aniž by nahlásil další kliky, protože nemůže existovat maximální klika, která zahrnuje vrchol 6 a vylučuje vrchol 4.

Strom volání algoritmu proto vypadá takto:

BronKerbosch2 (Ø, {1,2,3,4,5,6}, Ø) BronKerbosch2 ({2}, {1,3,5}, Ø) BronKerbosch2 ({2,3}, Ø, Ø): výstup {2, 3} BronKerbosch2 ({2,5}, {1}, Ø) BronKerbosch2 ({1,2,5}, Ø, Ø): výstup {1,2,5} BronKerbosch2 ({4}, {3 , 5,6}, Ø) BronKerbosch2 ({3,4}, Ø, Ø): výstup {3,4} BronKerbosch2 ({4,5}, Ø, Ø): výstup {4,5} BronKerbosch2 ({4 , 6}, Ø, Ø): výstup {4,6} BronKerbosch2 ({6}, Ø, {4}): žádný výstup

Graf v příkladu má degeneraci dvě; jedno možné uspořádání degenerace je 6,4,3,1,2,5. Pokud je verze verzí algoritmu Bron – Kerbosch použita na vrcholy, v tomto pořadí vypadá strom volání jako

BronKerbosch3 (G) BronKerbosch2 ({6}, {4}, Ø) BronKerbosch2 ({6,4}, Ø, Ø): výstup {6,4} BronKerbosch2 ({4}, {3,5}, {6} ) BronKerbosch2 ({4,3}, Ø, Ø): výstup {4,3} BronKerbosch2 ({4,5}, Ø, Ø): výstup {4,5} BronKerbosch2 ({3}, {2}, { 4}) BronKerbosch2 ({3,2}, Ø, Ø): výstup {3,2} BronKerbosch2 ({1}, {2,5}, Ø) BronKerbosch2 ({1,2}, {5}, Ø) BronKerbosch2 ({1,2,5}, Ø, Ø): výstup {1,2,5} BronKerbosch2 ({2}, {5}, {1,3}): žádný výstup BronKerbosch2 ({5}, Ø, {1,2,4}): žádný výstup

Analýza nejhorších případů

Algoritmus Bron – Kerbosch není algoritmus citlivý na výstup: na rozdíl od některých jiných algoritmů pro problém s klikou se nespustí polynomiální čas za maximální vygenerovanou kliku. Je však efektivní v nejhorším případě: výsledkem Moon & Moser (1965), jakýkoli n-vertexový graf má maximálně 3n/3 maximální kliky a nejhorší doba chodu algoritmu Bron – Kerbosch (s pivotní strategií, která minimalizuje počet rekurzivních hovorů provedených v každém kroku) je O (3n/3), odpovídající této vazbě.[8]

Pro řídké grafy, jsou možné přísnější hranice. Zejména lze zajistit včasnou verzi algoritmu Bron – Kerbosch s objednáváním vrcholů Ó(dn3d/3), kde d je zvrhlost grafu, míra jeho řídkosti. Existují d-degenerovat grafy, pro které je celkový počet maximálních klik (n − d)3d/3, takže tato vazba je téměř těsná.[6]

Poznámky

  1. ^ Cazals & Karande (2008).
  2. ^ Chen (2004).
  3. ^ Johnston (1976).
  4. ^ Tomita, Tanaka & Takahashi (2006); Cazals & Karande (2008).
  5. ^ Johnston (1976); Koch (2001); Cazals & Karande (2008).
  6. ^ A b C Eppstein, Löffler & Strash (2010).
  7. ^ A b Eppstein & Strash (2011).
  8. ^ Tomita, Tanaka & Takahashi (2006).

Reference

  • Akkoyunlu, E. A. (1973), "Výčet maximálních klik velkých grafů", SIAM Journal on Computing, 2: 1–6, doi:10.1137/0202001.
  • Chen, Lingran (2004), „Substructure and maximal common substructure searching“, v Bultinck, Patrick (ed.), Výpočetní léčivá chemie pro objevování léčiv, CRC Press, str. 483–514, ISBN  978-0-8247-4774-9.
  • Bron, Coen; Kerbosch, Joep (1973), „Algoritmus 457: nalezení všech klik nepřímého grafu“, Commun. ACM, ACM, 16 (9): 575–577, doi:10.1145/362342.362367.
  • Cazals, F .; Karande, C. (2008), „Poznámka k problému hlášení maximálních kliků“ (PDF), Teoretická informatika, 407 (1): 564–568, doi:10.1016 / j.tcs.2008.05.010[trvalý mrtvý odkaz ].
  • Eppstein, David; Löffler, Maarten; Strash, Darren (2010), „Výpis všech maximálních klik do řídkých grafů v téměř optimálním čase“, Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.), 21. mezinárodní symposium o algoritmech a výpočtech (ISAAC 2010), Jeju, Korea, Přednášky v informatice, 6506, Springer-Verlag, str. 403–414, arXiv:1006.5440, doi:10.1007/978-3-642-17517-6_36.
  • Eppstein, David; Strash, Darren (2011), „Výpis všech maximálních klik ve velkých řídkých grafech reálného světa“, 10. mezinárodní sympozium o experimentálních algoritmech, arXiv:1103.0318, Bibcode:2011arXiv1103.0318E.
  • Johnston, H. C. (1976), „Kliky grafu - variace na Bron-Kerboschův algoritmus“, International Journal of Parallel Programming, 5 (3): 209–238, doi:10.1007 / BF00991836.
  • Koch, Ina (2001), „Výčet všech spojených maximálních společných podgrafů ve dvou grafech“, Teoretická informatika, 250 (1–2): 1–30, doi:10.1016 / S0304-3975 (00) 00286-3.
  • Moon, J. W .; Moser, L. (1965), „O klikách v grafech“, Israel J. Math., 3: 23–28, doi:10.1007 / BF02760024, PAN  0182577.
  • Tomita, Etsuji; Tanaka, Akira; Takahashi, Haruhisa (2006), „Nejhorší časová složitost pro generování všech maximálních klik a výpočetních experimentů“, Teoretická informatika, 363 (1): 28–42, doi:10.1016 / j.tcs.2006.06.015.

externí odkazy