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

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

На связи участник профессионального сообщества 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

Топ 10 друзей — алгоритм 1

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

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

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

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

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

Пример графа

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

Таблица для фиксации результата

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

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

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

Шаг 0

Шаг 1

Шаг 2

Шаг 3

Фиксация результата после первого блуждания

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

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

             Шаг 0

             Шаг 1                    

             Шаг 2                  

             Шаг 3

Фиксация результата после второго блуждания

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

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

Шаг 0

Шаг 1

Шаг 2

Шаг 3

Фиксация результата после третьего блуждания

Вершина 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

Топ 10 друзей — алгоритм 2

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

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

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

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

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

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

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

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

Пример графа

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

Матрица для алгоритма 3

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

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

Заполнение столбца N=1

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

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

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

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

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

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

Вершина 7 = 1 + ⅓ * (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 друзей — алгоритм 3

А вот тут Теон даже не входит в топ-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

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

Финальный результат

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

Заключение

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

© Habrahabr.ru