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
Exercise instructions
- Write a function
node_in_open_triangle()
that has two parameters -G
andn
- 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
andn2
do not have an edge between them, setin_open_triangle
toTrue
, break out from theif
statement and returnin_open_triangle
.
- In the
- Use this function to count the number of open triangles that exist in
T
.- In the
for
loop, iterate over all the nodes inT
. - If the current node
n
is in an open triangle, incrementnum_open_triangles
.
- In the
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)