LoslegenKostenlos loslegen

Alle maximalen Cliquen der Größe "n" finden

Nachdem du dir Dreiecke (und offene Dreiecke) angeschaut hast, geht es jetzt um maximale Cliquen. Maximale Cliquen sind Cliquen, die sich nicht durch Hinzufügen einer benachbarten Kante erweitern lassen, und sie sind hilfreich, um Gemeinschaften im Graphen zu finden. NetworkX stellt eine Funktion bereit, mit der du die Knoten in jeder maximalen Clique eines Graphen bestimmen kannst: nx.find_cliques(G). Probiere die Funktion in der IPython Shell mit T aus und beantworte anschließend die Aufgabe.

Diese Übung ist Teil des Kurses

Einstieg in die Netzwerkanalyse mit Python

Kurs anzeigen

Anleitung zur Übung

  • Schreibe eine Funktion maximal_cliques() mit zwei Parametern – G und size – die alle maximalen Cliquen der Größe n findet.
    • Iteriere in der for-Schleife über alle Cliquen in G mit der Funktion nx.find_cliques().
    • Wenn die aktuelle Clique die Größe size hat, hänge sie an die Liste mcs an.
  • Verwende ein assert-Statement und deine Funktion maximal_cliques(), um zu prüfen, dass es 33 maximale Cliquen der Größe 3 im Graphen T gibt.

Interaktive Übung

Vervollständige den Beispielcode, um diese Übung erfolgreich abzuschließen.

# Define maximal_cliques()
def ____:
    """
    Finds all maximal cliques in graph `G` that are of size `size`.
    """
    mcs = []
    for clique in ____:
        if ____ == ____:
            ____
    return mcs

# Check that there are 33 maximal cliques of size 3 in the graph T
assert ____ == ____
Code bearbeiten und ausführen