CommencerCommencer gratuitement

Trouver toutes les cliques maximales de taille « n »

Maintenant que vous avez exploré les triangles (et les triangles ouverts), passons à la notion de clique maximale. Les cliques maximales sont des cliques qui ne peuvent pas être étendues en ajoutant une arête adjacente ; elles sont utiles pour détecter des communautés dans un graphe. NetworkX fournit une fonction qui permet d’identifier les nœuds impliqués dans chaque clique maximale d’un graphe : nx.find_cliques(G). Expérimentez avec cette fonction sur T dans l’IPython Shell, puis répondez à l’exercice.

Cet exercice fait partie du cours

Introduction à l’analyse de réseaux en Python

Afficher le cours

Instructions

  • Écrivez une fonction maximal_cliques() qui prend deux paramètres — G et size — et trouve toutes les cliques maximales de taille n.
    • Dans la boucle for, itérez sur toutes les cliques de G à l’aide de la fonction nx.find_cliques().
    • Si la clique courante est de taille size, ajoutez-la à la liste mcs.
  • Utilisez une instruction assert et votre fonction maximal_cliques() pour vérifier qu’il existe 33 cliques maximales de taille 3 dans le graphe T.

Exercice interactif pratique

Essayez cet exercice en complétant cet exemple de code.

# 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 ____ == ____
Modifier et exécuter le code