НачатьНачать бесплатно

Поиск открытых треугольников

Теперь перейдём к поиску открытых треугольников! Напомним, что они лежат в основе систем рекомендации друзей: если «A» знает «B» и «A» знает «C», то, вероятно, «B» тоже знает «C».

Это упражнение является частью курса

Введение в анализ сетей на Python

Посмотреть курс

Инструкции к упражнению

  • Напишите функцию node_in_open_triangle() с двумя параметрами — G и n — которая определяет, входит ли узел в открытый треугольник со своими соседями.
    • В цикле for переберите все возможные комбинации рёбер для образования треугольника.
    • Если между узлами n1 и n2 нет ребра, присвойте in_open_triangle значение True, выйдите из блока if и верните in_open_triangle.
  • Используйте эту функцию, чтобы подсчитать количество открытых треугольников в T.
    • В цикле for переберите все узлы в T.
    • Если текущий узел n входит в открытый треугольник, увеличьте num_open_triangles на единицу.

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

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)
Редактировать и запускать код