CommencezCommencez gratuitement

Trouver toutes les cliques maximales de taille « n »

Maintenant que vous avez exploré les triangles (et les triangles ouverts), passons au concept de cliques maximales. Les cliques maximales sont des cliques qu'on ne peut pas étendre en ajoutant une arête adjacente, et elles sont utiles pour repérer les communautés dans un graphe. NetworkX offre 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 en l'utilisant sur T dans l'interpréteur IPython, puis répondez à l'exercice.

Cette activité fait partie du cours

Introduction à l'analyse des réseaux en Python

Voir le cours

Instructions de l’exercice

  • É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, parcourez toutes les cliques de G avec 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 y a 33 cliques maximales de taille 3 dans le graphe T.

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

# 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