Maximale Clique Finder

Pseudocode

Bron-Kerbosch arbeitet mit drei Mengen: R ist die bisher gebaute Clique, P enthält die Kandidaten, die sie noch erweitern könnten, und X enthält die bereits probierten Knoten. Eine Clique ist genau dann maximal, wenn P und X beide leer sind.

BronKerbosch(R, P, X):
    wenn P und X beide leer sind:
        melde R als maximale Clique
        return

    für jeden Knoten v in P:
        BronKerbosch(R + {v},
                     P geschnitten Nachbarn(v),
                     X geschnitten Nachbarn(v))
        P = P - {v}
        X = X + {v}

// Mit Pivot: wähle einen Pivot u aus P vereinigt X und
// verzweige nur über die v in P, die KEINE Nachbarn von u sind

X ist der Teil, den man gern weglässt, und ohne ihn meldet der Algorithmus Cliquen, die nicht maximal sind. Sobald ein Knoten auf dieser Ebene bereits erkundet wurde, wandert er nach X, sodass jede Clique, die ihn hätte enthalten können, als nicht maximal verworfen wird. Die Pivot-Verfeinerung senkt anschließend den Verzweigungsgrad erheblich: jede maximale Clique muss den Pivot oder einen seiner Nichtnachbarn enthalten, über den Rest zu verzweigen ist also verlorene Arbeit.

Durchgerechnetes Beispiel, Schritt für Schritt

Zähle alle maximalen Cliquen eines Graphen mit sechs Kanten auf, der zwei überlappende Dreiecke und eine hängende Kante enthält.

Beispielgraph: Ungerichtete Kanten A-B, A-C, B-C, B-D, C-D und D-E.

1. Start. R ist leer, P enthält alle fünf Knoten, X ist leer. Verzweige zuerst über A.
2. Über A verzweigen. R wird zu {A}. P schrumpft auf die Nachbarn von A, also B und C. Verzweigen über B und dann C baut {A, B} und danach {A, B, C}. Dort sind P und X beide leer, da D nicht zu A benachbart ist, {A, B, C} wird also als maximal gemeldet.
3. Über B verzweigen, A liegt nun in X. R wird zu {B}. P schrumpft auf C und D, da A nach X gewandert ist. Erweitern liefert {B, C} und dann {B, C, D}, weil C und D benachbart sind. Dort sind P und X leer, {B, C, D} ist also maximal.
4. Warum {B, C} nicht gemeldet wird. Wenn R gleich {B, C} ist, liegt D noch in P, die Leerheitsprüfung schlägt also fehl und es wird keine Clique gemeldet. Genau dafür ist diese Prüfung da: {B, C} ist eine Clique, aber keine maximale, denn sie steckt in {A, B, C} und in {B, C, D}.
5. Die hängende Kante. Verzweigt man bis D hinab, während A, B und C erschöpft sind, bleibt E als einziger Kandidat und liefert {D, E}. E hat keine weiteren Nachbarn, das ist also maximal, obwohl es nur zwei Knoten umfasst.

Die maximalen Cliquen sind {A, B, C}, {B, C, D} und {D, E}. Die maximum Clique, also die größte, hat Größe 3, und davon gibt es zwei. Beachte, dass maximal und maximum verschieden sind: {D, E} ist maximal, weil sich nichts anfügen lässt, aber weit von maximum entfernt. Beachte außerdem, dass B und C in je zwei maximalen Cliquen vorkommen, was normal ist und erklärt, warum die Zahl maximaler Cliquen die Knotenzahl deutlich übersteigen kann.

Komplexität und woher sie kommt

Zeit: O(3^(V/3)) · Speicher: O(V^2)

Die Schranke stammt aus dem Satz von Moon und Moser: ein Graph mit V Knoten kann höchstens 3 hoch V/3 maximale Cliquen besitzen, und diese Schranke ist scharf, erreicht von einem vollständig multipartiten Graphen aus V/3 Dreiecken. Da der Algorithmus mindestens jede davon ausgeben muss, kann kein Aufzählungsalgorithmus das im schlechtesten Fall unterbieten, und Bron-Kerbosch mit Pivot erreicht sie. Das lohnt sich zu verinnerlichen: der Algorithmus ist optimal, doch das Problem selbst ist exponentiell. Nur die größte Clique zu finden ist NP-schwer, und selbst sie innerhalb eines vernünftigen Faktors zu approximieren ist schwer. In der Praxis machen Pivot und eine Degeneriertheitsordnung dünne reale Graphen mit Zehntausenden Knoten handhabbar, weil dünne Graphen weit weniger maximale Cliquen haben als der schlechteste Fall.

Wann Maximale Clique passt und wann nicht

Kläre zuerst, ob du alle maximalen Cliquen willst oder nur die größte, denn das sind verschiedene Probleme mit verschiedenen Werkzeugen.

Häufige Fehler

• Die Menge X weglassen. Ohne X meldet der Algorithmus jede Clique statt nur der maximalen, sodass {B, C} neben {A, B, C} auftauchen würde. Die Ausgabe bläht sich auf und ist falsch. X ist das Gedächtnis dafür, dass ein Zweig bereits abgedeckt wurde.
• Maximal mit maximum verwechseln. Eine maximale Clique lässt sich nicht erweitern; eine maximum Clique ist die größte im Graphen. {D, E} im Beispiel ist maximal und hat Größe 2, während die maximale Größe 3 beträgt. Nach der maximalen Clique zu fragen ist mehrdeutig und meint meist die größte.
• Den Pivot auf dichten Graphen weglassen. Reines Bron-Kerbosch ohne Pivot durchsucht enorm viel mehr Zweige. Auf dichten Graphen ist der Pivot keine Optimierung, sondern der Unterschied zwischen Fertigwerden und Nichtfertigwerden.
• Polynomielles Verhalten erwarten. Die Anzahl maximaler Cliquen kann exponentiell in der Knotenzahl sein, kein Implementierungstrick macht den allgemeinen Fall also schnell. Ist ein Graph dicht und groß, zähle mit einer Obergrenze auf oder formuliere die Frage um.
• Schleifen oder Richtungen als bedeutsam behandeln. Cliquen sind für einfache ungerichtete Graphen definiert. Gerichtete Kanten müssen zuerst symmetrisiert werden, und es ist zu entscheiden, ob eine Einbahnkante als Nachbarschaft zählt, denn diese Wahl verändert die Antwort.

Häufig gestellte Fragen

Was ist eine maximale Clique?

Eine Clique ist eine Menge von Knoten, die paarweise benachbart sind. Eine Clique ist maximal, wenn sich kein weiterer Knoten hinzufügen lässt, ohne diese Eigenschaft zu verlieren. Das unterscheidet sich von einer maximum Clique, der größten im Graphen: jede maximum Clique ist maximal, doch eine kleine maximale Clique kann neben weit größeren bestehen.

Wie funktioniert der Bron-Kerbosch-Algorithmus?

Er rekursiert über drei Mengen: R, die bisher gebaute Clique, P, die Kandidaten, die sie noch erweitern können, und X, die auf dieser Ebene bereits erkundeten Knoten. In jedem Schritt verschiebt er einen Kandidaten von P nach R und schränkt P und X auf dessen Nachbarn ein. Sind P und X beide leer, ist R eine maximale Clique. Einen Pivot zu wählen und nur über dessen Nichtnachbarn zu verzweigen beschneidet den größten Teil der Suche.

Was ist der Unterschied zwischen maximaler und maximum Clique?

Maximal heißt lokal unerweiterbar: du kannst ihr keinen Knoten hinzufügen. Maximum heißt global am größten: keine Clique im Graphen hat mehr Knoten. Ein Graph kann viele maximale Cliquen unterschiedlicher Größe besitzen, und sie alle zu finden ist ein anderes Problem als die einzelne größte zu finden.

Wie ist die Zeitkomplexität, alle maximalen Cliquen zu finden?

O(3 hoch V/3) im schlechtesten Fall, und das ist optimal. Nach dem Satz von Moon und Moser kann ein Graph so viele maximale Cliquen enthalten, jeder Algorithmus, der sie alle auflistet, braucht also mindestens so lange. Auf dünnen Graphen liefert eine Degeneriertheitsordnung eine weit bessere praktische Schranke.

Wofür werden Cliquen verwendet?

Für Community-Erkennung in sozialen Netzwerken, das Auffinden koexprimierter Gengruppen in der Bioinformatik, das Bestimmen paarweise verträglicher Mengen in Ablaufplanung und Empfehlung, das Aufspüren von Betrugsringen, in denen alle Beteiligten miteinander handeln, sowie für Zuordnungsprobleme, in denen eine Clique eine vollständig konsistente Auswahl darstellt.