Alle maximale cliques van grootte "n" vinden
Nu je driehoeken (en open driehoeken) hebt verkend, gaan we door naar het concept van maximale cliques. Maximale cliques zijn cliques die niet kunnen worden uitgebreid door een aangrenzende rand toe te voegen, en zijn een nuttige eigenschap van de graaf bij het vinden van communities. NetworkX biedt een functie waarmee je de knopen kunt identificeren die bij elke maximale clique in een graaf horen: nx.find_cliques(G). Experimenteer met de functie door deze op T te gebruiken in de IPython Shell en beantwoord daarna de oefening.
Deze oefening maakt deel uit van de cursus
Introductie tot netwerkanalyse in Python
Oefeninstructies
- Schrijf een functie
maximal_cliques()met twee parameters —Gensize— die alle maximale cliques van groottenvindt.- Doorloop in de
for-lus alle cliques inGmet de functienx.find_cliques(). - Als de huidige clique de grootte
sizeheeft, voeg deze dan toe aan de lijstmcs.
- Doorloop in de
- Gebruik een assert-statement en je functie
maximal_cliques()om te controleren dat er33maximale cliques van grootte3zijn in de graafT.
Praktische interactieve oefening
Probeer deze oefening eens door deze voorbeeldcode in te vullen.
# 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 ____ == ____