Как я теорию 6-ти рукопожатий проверял. Часть 2
В первой части я собрал данные из социальной сети вконтакте по друзьям друзей друзей 9 пользователей из разных возрастных категорий, с которыми мне довелось пересечься в жизни. Я организовал хранение самих пользователей, а также их связей с другими пользователями в реляционной БД. Для этого я использовал postgres.
Схема БД:
Поля в таблице friends ссылаются на vk_id поле таблицы users.
Изначально я хотел проверить теорию 6-ти рукопожатий для этих девяти человек, а также расширить свой навык использования рекурсивных запросов.
Собирая данные для базы, и друзей 3-го уровня, у меня получилось порядка полумилиона пользователей. В результате мне удалось показать, что для моей выборке достаточно даже пяти рукопожатий. В этой статье я хочу доработать полученный результат и попробовать реализовать построение кратчайших цепочек-связей между двумя пользователями.
Ищу кратчайшие пути
В прошлой статье я показал запрос, который позволял построить все возможные цепочки между двумя пользователями. Главная его проблема заключалась в том, что с ростом уровня, дерево отношений сильно разрасталось и для 5 уровней составляло порядка 56 млн записей. А время на выполнение запроса составляло порядка 5 минут на запрос.
Так что, в этой статье я продумал альтернативный способ построения цепочек, чтобы минимизировать количество неподходящих вариантов.
Для этого я решил осуществлять поиск сразу с двух концов. Найти уровень, на котором обнаруживаются общие друзья, выбрать первого попавшегося друга на этом уровне и от него уже строить цепочки влево и вправо.
Ключевым запросом у меня выступил следующий скрипт, который осуществлял поиск пересечения друзей (до 3-го уровня) пользователей 123 и 567:
WITH RECURSIVE levels(d1, d2) AS (
-- список комбинаций соединения уровней
VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
), level_from(id, depth) AS (
-- первые 3 уровня друзей первого пользователя
SELECT 123, 123 as id, 0 as depth
UNION ALL
SELECT DISTINCT
start_id,
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_from l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
), level_to(id, depth) AS (
-- первые 3 уровня друзей второго пользователя
SELECT 567, 567 as id, 0 as depth
UNION ALL
SELECT DISTINCT
end_id,
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_to l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
)
-- выбираем первого пользователя, являющегося центром в цепочке
SELECT start_id, d1, l1.id, d2, end_id
FROM levels l
JOIN level_from l1 ON l1.depth = l.d1
JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id
ORDER BY d1 + d2
LIMIT 1
В результате получился такой ответ:
| id 1-го пользователя | Расстояние до центра | id центрального пользователя в цепи | Расстояние до 2-го пользователя | id 2-го пользователя |
|---|---|---|---|---|
| 123 | 1 | 999 | 2 | 567 |
Расстояние 1 - означает, что пользователь является непосредственным другом 1-го пользователя.
Расстояние 2 - означает, что центральный пользователь является другом друга 2-го пользователя.
Так как максимально возможное расстояние у меня в 3 уровня, то можно перебрать все цепочки. А из них уже выбрать любую.
Для этого я доработал скрипт из предыдущей статьи, который выдавал все цепочки для заданного пользователя:
WITH RECURSIVE chains(id, chain, depth) AS (
-- строим левые цепочки
SELECT
123,
123 :: TEXT AS chain,
0 AS depth
UNION
SELECT
CASE WHEN l.id = f.user2_id
THEN user1_id
ELSE user2_id END AS id,
l.chain || ' -> ' || CASE WHEN l.id = f.user2_id
THEN user1_id ELSE user2_id END AS chain,
l.depth + 1 AS depth
FROM friends f
JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
)
SELECT *
FROM chains
Порождаем чудовище
Немного доработаем его, чтоб он хватал цепочки, и получим такого монстра:
WITH RECURSIVE
users (from_user, to_user) AS (
SELECT 123, 567
),
levels(d1, d2) AS (
VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
),
level_from(id, depth) AS (
SELECT
(SELECT from_user FROM users) as id,
0 as depth
UNION ALL
SELECT DISTINCT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_from l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
),
level_to(id, depth) AS (
SELECT
(SELECT to_user FROM users) as id,
0 as depth
UNION ALL
SELECT DISTINCT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_to l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
),
center_info AS (
SELECT
(SELECT from_user FROM users) as start_id,
d1,
l1.id as center_id,
d2,
(SELECT to_user FROM users) as end_id
FROM levels l
JOIN level_from l1 ON l1.depth = l.d1
JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id
ORDER BY d1 + d2
LIMIT 1
),
left_chains(id, chain, depth, max_depth, center_id) AS (
-- строим левые цепочки
SELECT
ci.start_id,
ci.start_id::text as chain,
0 as depth, -- уровень дерева
ci.d1 as max_depth,
ci.center_id as center_id
FROM center_info ci
UNION
SELECT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.chain || ' -> ' || CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END as chain,
l.depth + 1 as depth, -- изменение уровня дерева
l.max_depth,
l.center_id
FROM friends f
JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.center_id
)
),
right_chains(id, chain, depth, max_depth, end_id) AS (
-- строим правые цепочки
SELECT
ci.center_id,
'' as chain,
0 as depth, -- уровень дерева
ci.d2 as max_depth,
ci.end_id as end_id
FROM center_info ci
UNION
SELECT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.chain || CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END ||
CASE WHEN l.depth < l.max_depth - 1 THEN ' -> ' ELSE '' END as chain,
l.depth + 1 as depth, -- изменение уровня дерева
l.max_depth,
l.end_id
FROM friends f
JOIN right_chains l ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.end_id
)
)
SELECT l.chain || ' -> ' || r.chain
FROM left_chains l, right_chains r
WHERE l.depth = l.max_depth and r.depth = r.max_depth
Разъяснение
Хоть скрипт внешне и выглядит страшно, на самом деле не так ужасен. Давайте разберем его по частям. Всего у нас 7 CTE подзапросов и один основной, который объединяет последние два CTE запроса. Что же тут происходит? Поехали:
1. Первый нужен, чтоб не вводить список пользователей по несколько раз, просто фиксируем во временную таблицу с одной записью и двумя столбцами:
users (from_user, to_user) AS (
SELECT 123, 567
)
2. Это список возможных комбинаций расстояний (в уровнях) между крайними элементами цепочек (то есть пользователями, которых мы хотим соединить) и центральным связывающим пользователем. Это не значит, что все комбинации понадобятся, но значит, что мы рассматриваем только такие:
levels(d1, d2) AS (
VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
)
3. Формирует три уровня друзей (то есть друзья, друзья-друзей, друзья-друзей-друзей) для пользователя, от которого мы начинаем строить цепочку:
level_from(id, depth) AS (
SELECT -- начальная итерация
(SELECT from_user FROM users) as id,
0 as depth
UNION ALL
SELECT DISTINCT -- наращиваем уровни
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_from l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
)
Графически это выглядит так:
4. По аналогии с запросом выше, формируем три уровня друзей для пользователя, до которого мы пытаемся построить цепочку:
level_to(id, depth) AS (
SELECT
(SELECT to_user FROM users) as id,
0 as depth
UNION ALL
SELECT DISTINCT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.depth + 1 as depth
FROM level_to l
JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < 3
)
Выглядит вот так (но тут, для разннобразия, показываю только два уровня):
5. Находим самую короткую комбинацию уровней, на которой происходит пересечение друзей левого и правого пользователя соответственно:
center_info AS (
SELECT
(SELECT from_user FROM users) as start_id, -- левый пользователь
d1, -- растояние до точки наложения
l1.id as center_id, -- центральный пользователь
d2, -- прстояние до правого пользователя
(SELECT to_user FROM users) as end_id -- правый пользователь
FROM levels l -- выбираем из комбинаций расстояний
JOIN level_from l1 ON l1.depth = l.d1 -- подклеиваем с комбинациями существующие уровни левого пользователя
JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id -- подклеиваем существующие уровни второго пользователя, в местах, где идет наложение на уровни левого пользователя
ORDER BY d1 + d2 -- упорядочиваем по кратчайшему пути
LIMIT 1 -- берем только первый (самый короткий) путь
)
Грубо говоря, тут рассчитываются различные комбинации пересечения множеств друзей. И выбирается та, которая позволит построить кратчайший путь от пользователя до пользователя.
На схеме цветом выделены общие друзья. Для первого пользователя они впервые встречаются на третьем уровне. Для второго - на втором уровне. В целях оптимизации, я выбирают только одного пользователя из списка (помечен красным):
6. Строим все возможные цепочки от левого пользователя до центрального, с длиной равной той, что была указана в center_info:
left_chains(id, chain, depth, max_depth, center_id) AS (
SELECT
ci.start_id,
ci.start_id::text as chain,
0 as depth, -- уровень дерева
ci.d1 as max_depth, -- ограничение на размер дерева
ci.center_id as center_id -- правый пользователь в подцепи
FROM center_info ci
UNION
SELECT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.chain || ' -> ' || CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END as chain,
l.depth + 1 as depth, -- изменение уровня дерева
l.max_depth,
l.center_id
FROM friends f
JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.center_id
)
)
Тут, думаю, все и без комментариев ясно:
7. Строим все возможные цепочки от центрального пользователя до правого, с длиной равной той, что была указана в center_info:
right_chains(id, chain, depth, max_depth, end_id) AS (
SELECT
ci.center_id,
'' as chain,
0 as depth, -- уровень дерева
ci.d2 as max_depth,
ci.end_id as end_id
FROM center_info ci
UNION
-- тут небольшое отличие в формировании строки цепи, чтобы не появлялся двойной знак ->
SELECT
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
l.chain || CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END ||
CASE WHEN l.depth < l.max_depth - 1 THEN ' -> ' ELSE '' END as chain,
l.depth + 1 as depth, -- изменение уровня дерева
l.max_depth,
l.end_id
FROM friends f
JOIN right_chains l ON l.id = f.user1_id OR l.id = f.user2_id
WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.end_id
)
)
Аналогично предыдущему пункту:
8. Основной запрос, просто склеивает две таблицы, выдающие цепочки, чтобы получить все возможные комбинации цепочек:
SELECT l.chain || ' -> ' || r.chain
FROM left_chains l, right_chains r
-- тут фильтруем по максимальной указанной длине цепи, потому что промежуточные цепочки нас не интересуют
WHERE l.depth = l.max_depth and r.depth = r.max_depth
Заключение
Как видно, рекурсивные запросы дают достаточно мощный инструмент для работы с графами. Для моего примера скорость нахождения цепочки составила порядка 4 секунд для полумиллиона ползователей на моем четырехядерном ноутбуке с SSD. Хороший ли это результат? Ну для работы в райнтайме, наверное, нет. Для разового запуска или для работы в бэкграунде - вполне приличный. Можно ли его улучшить? Полагаю, что можно.
В целом, считаю, что эксперимент удался - я лучше разобрался с рекурсивными запросами. На каком-то этапе я даже не был уверен, что удастся решить эту задачу, не прибегая к использованию функций. Но, к моей радости, у меня это получлось.
Более того, я собрал достаточно внушительный набор данных для дальнейшего анализа. Который в ближайшее время, я планирую более глубоко проанализировать. Возможно, попробовать найти "ключевых" пользователей, за счет которых и обеспечивается покрытие рукопожатиями. Но пока на этом все.
