Поиск треугольных связей
Теперь, когда вы познакомились с понятием клик, пришло время применить эти знания для поиска структур в сети. Начнём с треугольников — простейшего вида нетривиальных клик. Давайте напишем несколько функций: эти упражнения помогут вам разобраться в базовой логике сетевых алгоритмов.
В сети Twitter каждый узел имеет метку 'occupation', которая разделяет пользователей по роду деятельности на три категории: celebrity (знаменитость), politician (политик) и scientist (учёный). Один из возможных способов применения алгоритмов поиска треугольников — выяснить, склонны ли пользователи со схожей профессией образовывать клики друг с другом.
Это упражнение является частью курса
Введение в анализ сетей на Python
Инструкции к упражнению
- Импортируйте
combinationsизitertools. - Напишите функцию
is_in_triangle()с двумя параметрами —Gиn— которая проверяет, входит ли заданный узел в треугольную связь.combinations(iterable, n)возвращает комбинации размераnизiterable. Это пригодится здесь: вам нужны комбинации размера2изlist(G.neighbors(n)).- Чтобы проверить, существует ли ребро между двумя узлами, используйте метод
.has_edge(node1, node2). Если ребро существует, значит, заданный узел входит в треугольную связь — вернитеTrue.
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
____
# Define is_in_triangle()
def is_in_triangle(G, n):
"""
Checks whether a node `n` in graph `G` is in a triangle relationship or not.
Returns a boolean.
"""
in_triangle = False
# Iterate over all possible triangle relationship combinations
for n1, n2 in ____:
# Check if an edge exists between n1 and n2
if ____:
in_triangle = ____
break
return in_triangle