Get startedGet started for free

Finding open triangles

Let us now move on to finding open triangles! Recall that they form the basis of friend recommendation systems; if "A" knows "B" and "A" knows "C", then it's probable that "B" also knows "C".

This exercise is part of the course

Introduction to Network Analysis in Python

View Course

Exercise instructions

  • Write a function node_in_open_triangle() that has two parameters - G and n - and identifies whether a node is present in an open triangle with its neighbors.
    • In the for loop, iterate over all possible triangle relationship combinations.
    • If the nodes n1 and n2 do not have an edge between them, set in_open_triangle to True, break out from the if statement and return in_open_triangle.
  • Use this function to count the number of open triangles that exist in T.
    • In the for loop, iterate over all the nodes in T.
    • If the current node n is in an open triangle, increment num_open_triangles.

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

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)
Edit and Run Code