CommencezCommencez gratuitement

Repérer les triangles ouverts

Passons maintenant à la détection des triangles ouverts! Rappelez-vous qu'ils servent de base aux systèmes de recommandation d'ami·e·s; si « A » connaît « B » et « A » connaît « C », il est probable que « B » connaisse aussi « C ».

Cette activité fait partie du cours

Introduction à l'analyse des réseaux en Python

Voir le cours

Instructions de l’exercice

  • Écrivez une fonction node_in_open_triangle() qui prend deux paramètres — G et n — et indique si un nœud fait partie d'un triangle ouvert avec ses voisins.
    • Dans la boucle for, parcourez toutes les combinaisons possibles de relations de triangle.
    • Si les nœuds n1 et n2 n'ont pas d'arête entre eux, affectez True à in_open_triangle, quittez l'instruction if et retournez in_open_triangle.
  • Utilisez cette fonction pour compter le nombre de triangles ouverts présents dans T.
    • Dans la boucle for, parcourez tous les nœuds de T.
    • Si le nœud courant n est dans un triangle ouvert, incrémentez num_open_triangles.

Exercice interactif pratique

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

from itertools import combinations

# Define node_in_open_triangle()
def node_in_open_triangle(G, n):
    """
    Checks whether pairs of neighbors of node `n` in graph `G` are in an 'open triangle' relationship with node `n`.
    """
    in_open_triangle = False

    # Iterate over all possible triangle relationship combinations
    for n1, n2 in ____:

        # Check if n1 and n2 do NOT have an edge between them
        if not ____:

            in_open_triangle = ____

            break

    return ____

# Compute the number of open triangles in T
num_open_triangles = 0

# Iterate over all the nodes in T
for n in ____:

    # Check if the current node is in an open triangle
    if ____:

        # Increment num_open_triangles
        ____ += 1

print(num_open_triangles)
Modifier et exécuter le code