Zacznij terazZacznij za darmo

Znajdowanie wszystkich maksymalnych klik o rozmiarze "n"

Skoro zapoznałeś się już z trójkątami (i otwartymi trójkątami), czas przejść do pojęcia maksymalnych klik. Maksymalne kliki to kliki, których nie można rozszerzyć przez dodanie sąsiedniej krawędzi – są przydatną właściwością grafu podczas wykrywania społeczności. NetworkX udostępnia funkcję pozwalającą zidentyfikować węzły wchodzące w skład każdej maksymalnej kliki w grafie: nx.find_cliques(G). Poeksperymentuj z tą funkcją, wywołując ją na grafie T w powłoce IPython, a następnie spróbuj rozwiązać ćwiczenie.

To ćwiczenie jest częścią kursu

Wprowadzenie do analizy sieci w Pythonie

Zobacz kurs

Instrukcje do ćwiczenia

  • Napisz funkcję maximal_cliques() przyjmującą dwa parametry – G i size – która znajduje wszystkie maksymalne kliki o rozmiarze n.
    • W pętli for iteruj po wszystkich klikach w G, używając funkcji nx.find_cliques().
    • Jeśli bieżąca klika ma rozmiar size, dołącz ją do listy mcs.
  • Użyj instrukcji assert oraz funkcji maximal_cliques(), aby sprawdzić, czy w grafie T istnieje dokładnie 33 maksymalne kliki o rozmiarze 3.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

# 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 ____ == ____
Edytuj i uruchom kod