![](https://habrastorage.org/getpro/habr/upload_files/e3a/08e/334/e3a08e33494397015ea73a787b39fcbf.png)
Привет, Хабр!
На связи участник профессионального сообщества NTA Кухтенко Андрей.
В интернете постоянно что‑то рекомендуют: посмотреть новое видео, добавить друга или купить товар. Как работают эти алгоритмы, расскажу в посте ниже и реализую рекомендательную систему с помощью графов.
Принцип работы
Начну с разбора принципа работы рекомендательной системы на основе графов.
Представим граф:
![Пример графа Пример графа](https://habrastorage.org/getpro/habr/upload_files/b05/fbe/b2a/b05fbeb2a05ec30c348ef316b2d7b5dd.png)
Алгоритм анализирует существующие связи и на их основе предлагает соединить вершины, которые не связаны ребром, например, так:
![Пример соединения несвязанных рёбер Пример соединения несвязанных рёбер](https://habrastorage.org/getpro/habr/upload_files/84a/bc5/7b0/84abc57b033684d7d89b0b1c5ece7a56.png)
В публикации опишу три алгоритма, которые позволяют выявлять вероятные связи.
Анализ датафрейма и подготовка данных
Для анализа буду использовать датасет связей героев «Игры престолов»:
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
![Первоначальный датафрейм Первоначальный датафрейм](https://habrastorage.org/getpro/habr/upload_files/217/e36/afd/217e36afd635a8643e43ef0dde32b8a4.png)
Беру только поля 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
![Количество друзей у персонажа Количество друзей у персонажа](https://habrastorage.org/getpro/habr/upload_files/bc2/446/e3e/bc2446e3e86c03fa4e0ab8be7dfa8d6f.png)
Самыми общительными оказались семейство Ланнистеров, с затесавшимся среди них Джоном Сноу. Очевидно, им помощь не нужна. Попробую найти более скромного персонажа с проблемами в общении. На ум приходит немногословный, но добрый великан Ходор:
![Друзья Ходора Друзья Ходора](https://habrastorage.org/getpro/habr/upload_files/e47/f06/421/e47f064215f779a99f2437b8dd4b9c60.png)
Одиннадцать друзей — не густо, особенно по сравнению с лидерами. Подходит.
Для начала присвою каждому персонажу индекс и создам граф на основе этих индексов.
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
![Топ 10 друзей – алгоритм 1 Топ 10 друзей – алгоритм 1](https://habrastorage.org/getpro/habr/upload_files/201/778/1d0/2017781d0ba036f9a6622c2daa5d6720.png)
Лидер — Теон Грейджой, он знаком с семью из одиннадцати друзей Ходора.
Алгоритм 2 – Подсчет среднего количества шагов, которое требуется для достижения какой-либо вершины из исследуемой
Запускаю несколько случайных блужданий N из исследуемой вершины, в каждом блужданий фиксируем номер шага, на котором в первый раз была достигнута конкретная вершина. Количество шагов также ограничено, если вершина не была достигнута, то ставится максимум, указанный в ограничении.
Случайное блуждание — набор случайных переходов из одной вершины в другую (в том числе, возможен возврат в ту вершину из которой совершён переход).
Для сохранения результата будем использовать следующий метод — например, я хочу найти расстояния из вершины 1, совершив 10 случайных блужданий с шагом N=3 для следующего графа:
![Пример графа Пример графа](https://habrastorage.org/getpro/habr/upload_files/cad/92a/546/cad92a5463652da3548b532da2079341.png)
Создаю таблицу для фиксации результата:
![Таблица для фиксации результата Таблица для фиксации результата](https://habrastorage.org/getpro/habr/upload_files/3fa/a6a/963/3faa6a9630cb1b75b332572363766bd1.png)
В строке «Шаг достижения» увеличиваю значение в ячейке на номер шага, в который вершина была достигнута впервые.
В строке «К блужданий, когда достигнута» — если в текущем блуждании вершина была достигнута, то увеличиваем значение для этой вершины на 1.
Первое блуждание:
![Шаг 0 Шаг 0](https://habrastorage.org/getpro/habr/upload_files/219/aee/0a7/219aee0a7453512fcfb8530998c22a2e.png)
![Шаг 1 Шаг 1](https://habrastorage.org/getpro/habr/upload_files/906/ddc/22e/906ddc22e42ffd9f2571453e6471aaf0.png)
![Шаг 2 Шаг 2](https://habrastorage.org/getpro/habr/upload_files/c37/dbc/2e0/c37dbc2e0fe3ae5a6f94ab9651d271fd.png)
![Шаг 3 Шаг 3](https://habrastorage.org/getpro/habr/upload_files/fe2/784/ece/fe2784ecebb487dafdc2a9dd51d09d8c.png)
![Фиксация результата после первого блуждания Фиксация результата после первого блуждания](https://habrastorage.org/getpro/habr/upload_files/a06/0b3/273/a060b327332ed19f5d05d014c3989aa2.png)
Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1 (увеличиваем значение в ячейке на 1: 0 + 1 = 1), вершина 6 — на шаге 2 (увеличиваем значение в ячейке на 2: 0 + 2 = 2) и вершина 7 — на шаге 3 (увеличиваем значение в ячейке на 3: 0 + 3 = 3). Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».
Второе блуждание:
![Шаг 0 Шаг 0](https://habrastorage.org/getpro/habr/upload_files/b4e/d1e/4d8/b4ed1e4d86fc16ad1c3532ed3611f734.png)
![Шаг 1 Шаг 1](https://habrastorage.org/getpro/habr/upload_files/fd6/c3c/433/fd6c3c433423fd3c4303a3f1a1cc9cbb.png)
![Шаг 2 Шаг 2](https://habrastorage.org/getpro/habr/upload_files/65e/111/917/65e11191777451dfa9e48b9b78c14f83.png)
![Шаг 3 Шаг 3](https://habrastorage.org/getpro/habr/upload_files/bec/e37/630/bece376302ba3b2a75d3fdda9d87956a.png)
![Фиксация результата после второго блуждания Фиксация результата после второго блуждания](https://habrastorage.org/getpro/habr/upload_files/329/1e5/d0f/3291e5d0f983d0cff350b2a1c9a50685.png)
Вершина 1 достигнута на шаге 0, вершина 3 — на шаге 1, вершина 2 — на шаге 2 и на шаге 3 произошел возврат в вершину 3, но она уже была посещена в этом блуждании, значит значение не меняем. Для всех вершин при каждом первом вхождении увеличиваем значение на 1 в строке «К блужданий, когда достигнута».
Третье блуждание:
![Шаг 0 Шаг 0](https://habrastorage.org/getpro/habr/upload_files/5e7/d60/354/5e7d60354c21be9ec5d1f9675a0fbb1d.png)
![Шаг 1 Шаг 1](https://habrastorage.org/getpro/habr/upload_files/601/3a6/10c/6013a610cb692cb525b6392f76b5e8be.png)
![Шаг 2 Шаг 2](https://habrastorage.org/getpro/habr/upload_files/814/6bc/48f/8146bc48f13494ba35a7af005d0a55d6.png)
![Шаг 3 Шаг 3](https://habrastorage.org/getpro/habr/upload_files/b11/53d/5b0/b1153d5b0741d66af3e238be4ecfebaa.png)
![Фиксация результата после третьего блуждания Фиксация результата после третьего блуждания](https://habrastorage.org/getpro/habr/upload_files/609/ae7/e67/609ae7e6768fdcba2560ea8f81238dfa.png)
Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1, вершина 6 — на шаге 2 и вершина 7 — на шаге 3. Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».
Повторяю еще 7 раз, смотрю результат:
![Фиксация результата после десятого блуждания Фиксация результата после десятого блуждания](https://habrastorage.org/getpro/habr/upload_files/003/bdb/e45/003bdbe459fe9e4e08cce3429ff357ca.png)
Итак, вершина 1 достигнута 10 раз, что естественно, потому что я с нее начинал.
Четыре вершины достигнуты по 5 раз — 2,3,4,6
Пятая вершина — 3 раза, седьмая — 2 и восьмая ни разу.
Но для подсчета среднего количества шагов нужно указать одинаковое количество блужданий для каждой вершины. Для этого, если в блуждании вершина не была достигнута, то считаю для нее количество шагов, равное N — в моём случае, трём. Например, вершина 2 была достигнута 5 раз, значит не достигнута: 10 — 5 = 5 раз, для каждого из них количество шагов равно максимуму (3): 5 * 3 = 15, прибавляю 15 к результату: 10 + 15 = 25, в строке «К блужданий, когда достигнута» ставим 10 — это общее количество блужданий:
![Добавление блужданий для второй вершины Добавление блужданий для второй вершины](https://habrastorage.org/getpro/habr/upload_files/4ce/6ed/a21/4ce6eda2179414049ea9582f3c17e1eb.png)
Делаю то же самое для остальных вершин:
![Добавление блужданий для всех вершин Добавление блужданий для всех вершин](https://habrastorage.org/getpro/habr/upload_files/8a7/815/30d/8a781530dc3f8b891cd3540e8889d5c1.png)
Делю «Шаг достижения» на К блужданий, получаю среднее количество шагов:
![Среднее количество шагов для достижения вершины Среднее количество шагов для достижения вершины](https://habrastorage.org/getpro/habr/upload_files/c18/554/d36/c18554d36740ba7c1e05adb3cc97f0dc.png)
Ближайшие вершины — 3 и 4, но они нас не интересуют, так как уже являются соседями.
Далее идут вершины 2 и 6, значит можно предположить наличие таких ребер:
![Найденные рёбра Найденные рёбра](https://habrastorage.org/getpro/habr/upload_files/560/8df/e8e/5608dfe8e85119ffd29bf121192eb32a.png)
Реализую в 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
![Топ 10 друзей – алгоритм 2 Топ 10 друзей – алгоритм 2](https://habrastorage.org/getpro/habr/upload_files/e26/db6/4b3/e26db64b385bb3ab0c3a89aedae83d23.png)
Ближайшими вершинами снова оказались Теон Грейджой и Джон Сноу. Необходимо отметить, что поскольку блуждания случайные, результаты могут немного отличаться при каждом запуске функции, также они зависят от количества блужданий и шагов.
Алгоритм 3 – Подсчет среднего количества шагов, которое требуется для достижения исследуемой вершины из всех остальных
Для расчёта расстояний используется рекурсивная формула:
![](https://habrastorage.org/getpro/habr/upload_files/182/207/949/182207949f0dfb128d8a5f9b75ea37b1.png)
где N – номер шага,
(v) – текущая вершина,
|N(v)| - количество соседей вершины.
Для каждой вершины можно вычислить расстояние до исследуемой вершины, если знаю все расстояния до исследуемой вершины для всех вершин, которые находятся к ней ближе.
В качестве примера буду использовать тот же граф:
![Пример графа Пример графа](https://habrastorage.org/getpro/habr/upload_files/039/0ea/7de/0390ea7de4a1ebbd5131fdc20cc11da3.png)
Для оптимизации вычислений можно использовать матрицу номер вершины x шаг от исследуемой вершины.
![Матрица для алгоритма 3 Матрица для алгоритма 3](https://habrastorage.org/getpro/habr/upload_files/dee/cda/950/deecda9501f8e4449e7ab8a0a1f496dc.png)
Для исследуемой вершины значение всегда будет равно 0.
Осуществляю вычисления для N = 1.
![Заполнение столбца N=1 Заполнение столбца N=1](https://habrastorage.org/getpro/habr/upload_files/661/4f5/cd5/6614f5cd5e381fc39d76f4a6c3123069.png)
Вершина 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.
По этому же принципу заполняю остальные столбцы:
![Заполнение всех столбцов матрицы Заполнение всех столбцов матрицы](https://habrastorage.org/getpro/habr/upload_files/84d/dc5/6c1/84ddc56c1c0a6d4c9126ce5106c7c7d3.png)
Минимальные расстояния у вершин 3 и 4, но это соседи исследуемой вершины‑ их не учитываю.
Далее следуют вершины 2 и 6 — 3 и 3,67 соответственно. Опять выходит такая же картина, что и в предыдущем алгоритме:
![Найденные рёбра Найденные рёбра](https://habrastorage.org/getpro/habr/upload_files/587/da4/ae7/587da4ae746662534315e56ba7853396.png)
Но так случается далеко не всегда.
Реализую в 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 друзей – алгоритм 3 Топ 10 друзей – алгоритм 3](https://habrastorage.org/getpro/habr/upload_files/387/697/1b1/3876971b178d2f8305deb0a4b4f8c3cd.png)
А вот тут Теон даже не входит в топ-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
![Финальный результат Финальный результат](https://habrastorage.org/getpro/habr/upload_files/2d9/ae6/479/2d9ae6479f9725a32faf124d9d4242ef.png)
Итак, нашлось десять персонажей, с которыми может подружиться Ходор. Половину из них составляют члены семейства Старк — вполне логично, учитывая его заботу о Бране, также есть Тирион Ланнистер — он, похоже, дружит со всеми и Сэм Тарли — друг Джона Сноу. Позабавило наличие Рамзи Сноу, видимо, существуют какие‑то неявные связи. Остальных, к сожалению, не помню, так как смотрел сериал довольно давно.
Заключение
Представленные алгоритмы можно применять не только для поиска социальных связей, но и в любых других кейсах, связанных с анализом графов: поиск похожих фильмов, книг, в решении транспортных вопросов. Как и у любой рекомендательной системы, результат их работы не являются непреложной истиной, так как он носит, скорее, характер предположений, чем утверждений, но все равно может помочь в решении многих задач.
Tinkz
Здравствуйте, а можно весь проект целиком где-то увидеть, на гитхаб, например?
Tinkz
спасибо, разобрался