Типовые задачи: рекомендации, путь, сообщества

Готовые паттерны под задачи, ради которых берут граф: считаем силу рекомендации, ищем путь, нащупываем сообщества.

Большинство прикладных графовых задач сводятся к трём шаблонам: общие соседи (похожесть/рекомендации), путь между узлами и плотность связей (сообщества).

Эти три шаблона стоит запомнить как «графовый алфавит». Почти любая бизнес-задача, ради которой берут граф, раскладывается на их комбинацию. «Кого порекомендовать в друзья» — общие соседи. «Как этот перевод связан с подозрительным счётом» — путь. «Это организованная группа или случайные люди» — плотность. Освоив три рецепта ниже, вы закроете большую часть практики, а оставшееся доберёте алгоритмами из следующего урока. Важно, что все рецепты — это короткие Cypher-обходы, которые читаются как картинка.

Рекомендация через общих соседей

«Товары, которые покупали вместе с вашими». Сила рекомендации — это число пользователей, прошедших путь к товару:

(Вы)-[:BOUGHT]->(Товар A)<-[:BOUGHT]-(Другие)-[:BOUGHT]->(Товар B)

MATCH (me:User {id:'u-1'})-[:BOUGHT]->(:Product)<-[:BOUGHT]-(other:User)-[:BOUGHT]->(rec:Product)
WHERE NOT (me)-[:BOUGHT]->(rec)
RETURN rec.title AS recommend, count(DISTINCT other) AS strength
ORDER BY strength DESC
LIMIT 10

count(DISTINCT other) — сколько разных людей подтвердили связь товаров. NOT (me)-[:BOUGHT]->(rec) отсекает то, что вы уже купили.

Прелесть этого паттерна в том, что он сам себя объясняет: «люди, купившие то же, что и вы, купили ещё вот это». Тот же рисунок работает на фильмах — заменив BOUGHT на RATED, получаем «зрители, ставившие схожие оценки, любят и этот фильм». А если на связи RATED есть число звёзд, рекомендацию можно усилить, потребовав совпадения вкуса:

MATCH (me:User {id:'u-1'})-[r1:RATED]->(m:Movie)<-[r2:RATED]-(other:User)
WHERE r1.stars >= 4 AND r2.stars >= 4
MATCH (other)-[r3:RATED]->(rec:Movie)
WHERE r3.stars >= 4 AND NOT (me)-[:RATED]->(rec)
RETURN rec.title AS recommend, count(DISTINCT other) AS strength
ORDER BY strength DESC LIMIT 10

Здесь мы оставляем только «единомышленников» — тех, кто высоко оценил те же фильмы, что и вы, — и берём то, что высоко оценили они. Это уже почти настоящая коллаборативная фильтрация, выраженная одним обходом.

Кратчайший путь

«Как Алиса связана с Глебом и через кого» — классическая задача степеней разделения:

MATCH p = shortestPath(
  (a:Person {name:'Алиса'})-[:ЗНАЕТ*..6]-(b:Person {name:'Глеб'})
)
RETURN [n IN nodes(p) | n.name] AS chain, length(p) AS degrees

Ограничение *..6 страхует от взрыва: дальше шести рукопожатий искать обычно бессмысленно.

Путь — это не только «социальные рукопожатия». В антифроде тот же запрос отвечает на вопрос «как новый счёт связан с уже заблокированным мошенником» — через общее устройство, карту или адрес. В IT-инфраструктуре путь показывает, как падение одного сервиса докатится до пользователя. Если важна не просто связь, а «дешёвый» маршрут (по километрам, времени, стоимости), берут взвешенный путь — алгоритм Dijkstra из библиотеки GDS, о которой следующий урок; shortestPath же считает кратчайшим путь с наименьшим числом рёбер.

Друзья друзей с ранжированием

Рекомендация знакомых тем сильнее, чем больше общих друзей:

MATCH (me:Person {name:'Алиса'})-[:ЗНАЕТ]->(mutual)-[:ЗНАЕТ]->(candidate)
WHERE candidate <> me AND NOT (me)-[:ЗНАЕТ]->(candidate)
RETURN candidate.name AS suggest, count(DISTINCT mutual) AS mutual_friends
ORDER BY mutual_friends DESC

Обратите внимание на два защитных условия. candidate <> me не даёт порекомендовать саму Алису (она ведь общий друг для своих друзей), а NOT (me)-[:ЗНАЕТ]->(candidate) убирает тех, с кем она уже знакома. Ранжирование по count(DISTINCT mutual) ставит вперёд тех, с кем больше всего пересечений: именно так работает «возможно, вы знакомы» в соцсетях. Если хочется ещё точнее, в ранжирование добавляют вес — например, делят число общих друзей на общую популярность кандидата, чтобы не выпячивать «всем известных» людей.

Заготовка под сообщества

Полноценное обнаружение сообществ — это алгоритм (следующий урок), но «плотный кружок» можно нащупать и Cypher-ом: найти троих, которые все знают друг друга (треугольник):

MATCH (a:Person)-[:ЗНАЕТ]-(b:Person)-[:ЗНАЕТ]-(c:Person)-[:ЗНАЕТ]-(a)
WHERE id(a) < id(b) AND id(b) < id(c)
RETURN a.name, b.name, c.name

Условие на id отсекает повторы одного и того же треугольника в разном порядке.

Зачем вообще искать треугольники? Треугольник — это минимальная плотная группа: трое, замкнутые друг на друга. Чем больше треугольников вокруг человека, тем плотнее его окружение — этот показатель называют коэффициентом кластеризации. В соцсетях много треугольников означает сплочённую компанию; в антифроде неожиданно плотный треугольник из «незнакомых» аккаунтов — повод присмотреться. Полноценные сообщества (десятки и сотни узлов) Cypher-ом считать уже неудобно: для этого есть алгоритм Louvain. Но треугольник — отличная иллюстрация того, что «плотность» — это просто замкнутый обход.

Как работает под капотом

Все три шаблона — это обходы фиксированной формы: рекомендация — обход на 3 ребра с агрегацией, путь — BFS, треугольник — замкнутый обход на 3 узла. Их стоимость определяется степенями узлов на маршруте. Для «горячих» рекомендаций результат часто предвычисляют ночью и кэшируют, потому что онлайн-обход на суперактивных пользователях может быть тяжёлым.

Чуть подробнее про стоимость. Рекомендация раскрывается так: от вас разворачиваются купленные товары, от каждого — другие покупатели, от каждого — их покупки. Это значит, что число обработанных путей растёт как произведение степеней узлов на маршруте. Если вы купили 50 ходовых товаров, у каждого по 100 000 покупателей, а у каждого ещё по 50 покупок — счёт идёт на сотни миллионов путей. Вот почему такие рекомендации редко считают «вживую» на каждый клик: их гоняют пакетно ночью и складывают результат в кэш или в отдельные связи (:User)-[:MAY_LIKE]->(:Product), которые потом достаются за один шаг. shortestPath, наоборот, дёшев: поиск в ширину (BFS) идёт волнами от обоих концов и останавливается, едва волны встретятся, не разворачивая весь граф.

Частые ошибки

• Не исключить уже имеющееся. Без NOT (me)-[:BOUGHT]->(rec) вы порекомендуете уже купленное.
• Считать без DISTINCT. Сила рекомендации завысится из-за повторов путей.
• Безграничный shortestPath. Ставьте верхнюю границу глубины.
• Дубли треугольников. Без условия на id один треугольник вернётся шесть раз.

Итоги

• Рекомендации = обход через общих соседей; сила = count(DISTINCT) подтвердивших.
• «Степени разделения» — это shortestPath с ограничением глубины.
• Друзей друзей ранжируют по числу общих знакомых.
• Плотные кружки (треугольники) — заготовка под обнаружение сообществ; тяжёлые рекомендации предвычисляют.