Поможем Ходору найти новых друзей с помощью графов

Привет, Хабр!

На связи участник профессионального сообщества NTA Кухтенко Андрей.

В интернете постоянно что‑то рекомендуют: посмотреть новое видео, добавить друга или купить товар. Как работают эти алгоритмы, расскажу в посте ниже и реализую рекомендательную систему с помощью графов.

Принцип работы

Начну с разбора принципа работы рекомендательной системы на основе графов.

Представим граф:

Алгоритм анализирует существующие связи и на их основе предлагает соединить вершины, которые не связаны ребром, например, так:

В публикации опишу три алгоритма, которые позволяют выявлять вероятные связи.

Анализ датафрейма и подготовка данных

Для анализа буду использовать датасет связей героев «Игры престолов»:

https://www.kaggle.com/code/mmmarchetti/game‑of‑thrones‑network‑analysis/input

Представлю, что сагу написал не Дж. Мартин, а какой‑нибудь идеалист, живущий в мире розовых пони, где все сосуществуют в мире и согласии, а связи в датасете отображают наличие дружбы между персонажами. Попробую выбрать одного из них и найти для него новых друзей.

Импорт библиотек. Работать буду с networkx:

import networkx as nx import pandas as pd import random import operator

Создание графа:

g = nx.Graph()

Загружаю данные в датафрейм:

df = pd.read_csv('got_df.txt') df

Беру только поля Source, Target. Поле Type указывает на направленность графа (в моём случае все ненаправленные), weight — это прочность связи, для задачи предлагаю игнорировать этот параметр, book — порядковый номер книги.

Создаю граф:

edges= df[['Source', 'Target']].values.tolist() graph = nx.Graph(edges) nodes = len(graph.nodes())     

Посчитаю количество друзей у каждого персонажа и выведу список по убыванию:

friends_cnt = {x:len(graph[x]) for x in graph.nodes()} sorted_desc = sorted(friends_cnt.items(), key=operator.itemgetter(1), reverse = True) sorted_desc

Самыми общительными оказались семейство Ланнистеров, с затесавшимся среди них Джоном Сноу. Очевидно, им помощь не нужна. Попробую найти более скромного персонажа с проблемами в общении. На ум приходит немногословный, но добрый великан Ходор:

Одиннадцать друзей — не густо, особенно по сравнению с лидерами. Подходит.

Для начала присвою каждому персонажу индекс и создам граф на основе этих индексов.

mapping = {node:idx for idx, node in enumerate(graph.nodes())} mapped_graph = nx.Graph() for edge in graph.edges():     mapped_graph.add_edge(mapping[edge[0]], mapping[edge[1]]) mapping_reverse = dict((v,k) for k,v in mapping.items())            

Конвертирую граф в словарь формата ID персонажа: [ID персонажей друзей]:

dict_graph = nx.convert.to_dict_of_lists(mapped_graph)

Узнаю индекс Ходора:

mapping['Hodor']

Ответ — 78.

Объявляю переменную person и присваиваю ей значение, равное индексу Ходора:

person = 78

Подготовка завершена, приступаю к реализации.

Алгоритм 1 – Подсчет количества общих соседей

Получаю список соседей исследуемой вершины, а затем сравниваю со списком соседей каждой другой вершины на расстоянии через одну. Чем больше общих соседей, тем больше вероятность наличия не выявленной связи.

Пишу функцию:

def neights_count(graph, node):     '''Список для сохранения результата подсчета соседей'''     cnt_neis = [0] * len(graph)      '''Список соседей исследуемой вершины'''     node_neighbours = set(graph[node])      '''Словарь для списка вершин, не связанных с node, и их соседей'''     after_one_neigh_dict = {}          '''Заполнение словаря after_one_neigh_dict'''     for u in graph[node]:         for v in graph[u]:             after_one_neigh_dict[v] = graph[v]      '''Проход по вершинам в двух шагах от целевой        Поиск пересечений списков соседей'''            for i in after_one_neigh_dict:         check = len(set(after_one_neigh_dict[i]) & node_neighbours)         cnt_neis[i] = check      '''Зануление результата для исследуемой вершины и ее реальных соседей'''     cnt_neis[node] = 0     for neigh in graph[node]:         cnt_neis[neigh] = 0              return cnt_neis

Получаю топ-10 вершим с наибольшим количеством соседей:

nc = neights_count(dict_graph, person) nc_ans = {} for ind, el in enumerate(nc):     nc_ans[mapping_reverse[ind]] = el nc_ans_sorted = sorted(nc_ans.items(), key=lambda x: x[1], reverse = True)[:10] nc_ans_sorted

Лидер — Теон Грейджой, он знаком с семью из одиннадцати друзей Ходора.

Алгоритм 2 – Подсчет среднего количества шагов, которое требуется для достижения какой-либо вершины из исследуемой

Запускаю несколько случайных блужданий N из исследуемой вершины, в каждом блужданий фиксируем номер шага, на котором в первый раз была достигнута конкретная вершина. Количество шагов также ограничено, если вершина не была достигнута, то ставится максимум, указанный в ограничении.

Случайное блуждание — набор случайных переходов из одной вершины в другую (в том числе, возможен возврат в ту вершину из которой совершён переход).

Для сохранения результата будем использовать следующий метод — например, я хочу найти расстояния из вершины 1, совершив 10 случайных блужданий с шагом N=3 для следующего графа:

Создаю таблицу для фиксации результата:

В строке «Шаг достижения» увеличиваю значение в ячейке на номер шага, в который вершина была достигнута впервые.

В строке «К блужданий, когда достигнута» — если в текущем блуждании вершина была достигнута, то увеличиваем значение для этой вершины на 1.

Первое блуждание:

Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1 (увеличиваем значение в ячейке на 1: 0 + 1 = 1), вершина 6 — на шаге 2 (увеличиваем значение в ячейке на 2: 0 + 2 = 2) и вершина 7 — на шаге 3 (увеличиваем значение в ячейке на 3: 0 + 3 = 3). Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».

Второе блуждание:

Вершина 1 достигнута на шаге 0, вершина 3 — на шаге 1, вершина 2 — на шаге 2 и на шаге 3 произошел возврат в вершину 3, но она уже была посещена в этом блуждании, значит значение не меняем. Для всех вершин при каждом первом вхождении увеличиваем значение на 1 в строке «К блужданий, когда достигнута».

Третье блуждание:

Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1, вершина 6 — на шаге 2 и вершина 7 — на шаге 3. Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».

Повторяю еще 7 раз, смотрю результат:

Итак, вершина 1 достигнута 10 раз, что естественно, потому что я с нее начинал.

Четыре вершины достигнуты по 5 раз — 2,3,4,6

Пятая вершина — 3 раза, седьмая — 2 и восьмая ни разу.

Но для подсчета среднего количества шагов нужно указать одинаковое количество блужданий для каждой вершины. Для этого, если в блуждании вершина не была достигнута, то считаю для нее количество шагов, равное N — в моём случае, трём. Например, вершина 2 была достигнута 5 раз, значит не достигнута: 10 — 5 = 5 раз, для каждого из них количество шагов равно максимуму (3): 5 * 3 = 15, прибавляю 15 к результату: 10 + 15 = 25, в строке «К блужданий, когда достигнута» ставим 10 — это общее количество блужданий:

Делаю то же самое для остальных вершин:

Делю «Шаг достижения» на К блужданий, получаю среднее количество шагов:

Ближайшие вершины — 3 и 4, но они нас не интересуют, так как уже являются соседями.

Далее идут вершины 2 и 6, значит можно предположить наличие таких ребер:

Реализую в Python.

def from_distance(graph, node, time=15, samples = 50):     '''Список для сохранения результата'''     from_dist = [0] * nodes          '''Список для подсчета количества раз достижения вершин'''     ach_times = [0] * nodes          '''Список для суммы порядковых номеров шагов при достижении'''     used = [0] * nodes         '''Совершение блужданий'''     for iter in range(samples):         u = node          '''Список вершин, посещенных в блуждании'''         visited_nodes = []          for step in range(time):             '''Выбор случайной вершины из числа соседних'''             next_node = random.choice(graph[u])                          '''Проверка наличия вершины в списке посещенных'''             if next_node not in visited_nodes:                 '''Если вершина не посещена'''                  '''Увеличение значения суммы шагов для текщей вершины'''                 used[next_node] += step + 1                  '''Увеличение значения в списке для фиксации количества                    блужданий, в которых была достигнута вершина'''                 ach_times[next_node] += 1                  '''Добавление вершины в список посещенных                    вершин в текущем блуждании'''                 visited_nodes.append(next_node)                          u = next_node           '''Для каждой вершины считаем количество блужданий, в которые она не была посещена'''     plus_to_used = [(samples - el)*time for el in ach_times]          '''Вычисляем среднее количество шагов для каждой вершины'''     from_dist = [el/samples for el in list(map(sum, zip(used,plus_to_used)))]          '''Для исследуемой вершины и ее соседей проставляем максимальное количество шагов'''     from_dist[node] = time*samples     for neigh in graph[node]:         from_dist[neigh] = time*samples          return from_dist

Топ-10 вершин с наименьшим количеством шагов:

fd = from_distance(dict_graph, person) fd_ans = {} for ind, el in enumerate(fd):     fd_ans[mapping_reverse[ind]] = el fd_ans_sorted = sorted(fd_ans.items(), key=lambda x: x[1], reverse = False)[:10] fd_ans_sorted

Ближайшими вершинами снова оказались Теон Грейджой и Джон Сноу. Необходимо отметить, что поскольку блуждания случайные, результаты могут немного отличаться при каждом запуске функции, также они зависят от количества блужданий и шагов.

Алгоритм 3 – Подсчет среднего количества шагов, которое требуется для достижения исследуемой вершины из всех остальных

Для расчёта расстояний используется рекурсивная формула:

где N – номер шага,

       (v) – текущая вершина,

       |N(v)| — количество соседей вершины.

Для каждой вершины можно вычислить расстояние до исследуемой вершины, если знаю все расстояния до исследуемой вершины для всех вершин, которые находятся к ней ближе.

В качестве примера буду использовать тот же граф:

Для оптимизации вычислений можно использовать матрицу номер вершины x шаг от исследуемой вершины.

Для исследуемой вершины значение всегда будет равно 0.

Осуществляю вычисления для N = 1.

Вершина 1 = всегда 0.

Вершина 2 = 1 + 1/1 * 1 = 2, у вершины 1 сосед (вершина 3), N-1 для соседа равен 1.

Вершина 3 = 1 + 1/2 * (0+1) = 1,5, у вершины 2 соседа (вершины 1,2), N-1 для соседа 1 равен 0, N-1 для соседа 2 равен 1.

Вершина 4 = 1 + 1/2 * (0+1) = 1,5, у вершины 2 соседа (вершины 1,6), N-1 для соседа 1 равен 0, N-1 для соседа 6 равен 1.

Вершина 5 = 1 + 1/2 * (1+1) = 2, у вершины 2 соседа (вершины 6,7), N-1 для соседа 6 равен 1, N-1 для соседа 7 равен 1.

Вершина 6 = 1 + 1/3 * (1+1+1) = 2, у вершины 3 соседа (вершины 4,5,7), N-1 для соседа 4 равен 1, N-1 для соседа 5 равен 1, N-1 для соседа 7 равен 1.

Вершина 7 = 1 + 1/3 * (1+1+1) = 2, у вершины 3 соседа (вершины 5,6,8), N-1 для соседа 5 равен 1, N-1 для соседа 6 равен 1, N-1 для соседа 8 равен 1.

Вершина 8 = 1 + 1/1 * 1 = 2, у вершины 1 сосед (вершина 7), N-1 для соседа 7 равен 1.

По этому же принципу заполняю остальные столбцы:

Минимальные расстояния у вершин 3 и 4, но это соседи исследуемой вершины‑ их не учитываю.

Далее следуют вершины 2 и 6 — 3 и 3,67 соответственно. Опять выходит такая же картина, что и в предыдущем алгоритме:

Но так случается далеко не всегда.

Реализую в Python:

def to_distance(graph, node, time=10):     '''Формируем матрицу, наполняем нулями'''     martix = [[0 for _ in range(nodes)] for _ in range(time + 1)]          '''Цикл расчетов'''     for t in range(1, time + 1):         '''Проверка каждой вершины'''         for curr_node in range(nodes):             '''Если текущая вершина равна исследуемой, то пропускаем'''             if curr_node == node:                 continue             '''Если не исследуемая'''             if graph[curr_node]:                 '''Для первого шага всем ставим 1'''                 '''Для остальных делаем расчет по формуле'''                 if t == 1:                     martix[t][curr_node] = 1                 else:                     prev_t_sum = 0                     node_nei = graph[curr_node]                     for prev_node in node_nei:                         prev_t_sum += martix[t - 1][prev_node]                                              martix[t][curr_node] = 1 + (1/len(node_nei))          '''Для исследуемой вершины и ее соседей проставляем максимальное количество шагов'''     martix[time][node] = time     for neigh in graph[node]:         martix[time][neigh] = time             return martix[time]    

Топ-10 вершин с наименьшим количеством шагов:

td = to_distance(dict_graph, person) td_ans = {} for ind, el in enumerate(td):     td_ans[mapping_reverse[ind]] = el td_ans_sorted = sorted(td_ans.items(), key=lambda x: x[1], reverse = False)[:10] td_ans_sorte

А вот тут Теон даже не входит в топ-10, зато остался Джон Сноу, скорее всего, это первый кандидат на дружбу с Ходором.

Объединение результатов работы алгоритмов

def normalize_list(lst, reverse=False):     min_val = min(lst)     max_val = max(lst) if reverse:         normalized_list = [1 - (x - min_val) / (max_val - min_val) for x in lst] else:     normalized_list = [(x - min_val) / (max_val - min_val) for x in lst]  return normalized_list</code></pre><!--EndFragment-->   

norm_nc = normalize_list(nc, True) norm_fd = normalize_list(fd) norm_td = normalize_list(td)

Затем объединяю результаты:

def combine_ans(data1, data2, data3):     return [x + y + z for x,y,z in zip(data1,data2,data3)] 

ca = combine_ans(norm_nc,norm_fd,norm_td) comb_ans = {} for ind, el in enumerate(ca):     comb_ans[mapping_reverse[ind]] = el comb_ans_sorted = sorted(comb_ans.items(), key=lambda x: x[1], reverse = False)[:10] comb_ans_sorted

Итак, нашлось десять персонажей, с которыми может подружиться Ходор. Половину из них составляют члены семейства Старк — вполне логично, учитывая его заботу о Бране, также есть Тирион Ланнистер — он, похоже, дружит со всеми и Сэм Тарли — друг Джона Сноу. Позабавило наличие Рамзи Сноу, видимо, существуют какие‑то неявные связи. Остальных, к сожалению, не помню, так как смотрел сериал довольно давно.

Заключение

Представленные алгоритмы можно применять не только для поиска социальных связей, но и в любых других кейсах, связанных с анализом графов: поиск похожих фильмов, книг, в решении транспортных вопросов. Как и у любой рекомендательной системы, результат их работы не являются непреложной истиной, так как он носит, скорее, характер предположений, чем утверждений, но все равно может помочь в решении многих задач.