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

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

Рекомендации через знакомых

Самый простой рецепт: посоветуй то, что читают твои знакомые, а ты ещё нет. Для Глеба:

MATCH (a:Person {name: 'Глеб'})-[:KNOWS]-(f)-[r:READ]->(b:Book)
WHERE NOT (a)-[:READ]->(b)
RETURN b.title, count(*) AS friends, round(avg(r.rating), 1) AS rating
ORDER BY friends DESC, rating DESC, b.title;

+-----------------------------------------+
| b.title              | friends | rating |
+-----------------------------------------+
| "Двенадцать стульев" | 1       | 5.0    |
| "Пикник на обочине"  | 1       | 4.0    |
| "Обломов"            | 1       | 2.0    |
+-----------------------------------------+

3 rows

Три шага: Глеб, его знакомые, их книги. WHERE NOT убирает прочитанное, count(*) считает, сколько знакомых читали книгу, средняя оценка помогает разбить ничьи.

Рекомендации по похожим вкусам

Второй рецепт сильнее: искать не знакомых, а людей с похожими вкусами, даже если Аня их не знает. Сходство измеряем числом общих книг, а потом берём то, что читали самые похожие:

MATCH (a:Person {name: 'Аня'})-[:READ]->(b:Book)<-[:READ]-(other)
WITH a, other, count(b) AS common
ORDER BY common DESC, other.name
LIMIT 3
MATCH (other)-[:READ]->(rec:Book)
WHERE NOT (a)-[:READ]->(rec)
RETURN rec.title, collect(other.name) AS via, count(*) AS votes
ORDER BY votes DESC, rec.title;

+--------------------------------------------------------+
| rec.title                          | via       | votes |
+--------------------------------------------------------+
| "Двенадцать стульев"               | ["Борис"] | 1     |
| "Понедельник начинается в субботу" | ["Вера"]  | 1     |
+--------------------------------------------------------+

2 rows

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

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

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

MATCH p = shortestPath((a:Person {name: 'Аня'})-[:KNOWS*]-(b:Person {name: 'Илья'}))
RETURN length(p) AS hops, [n IN nodes(p) | n.name] AS chain;

+----------------------------------------------------------------+
| hops | chain                                                   |
+----------------------------------------------------------------+
| 6    | ["Аня", "Глеб", "Дина", "Егор", "Жанна", "Зоя", "Илья"] |
+----------------------------------------------------------------+

1 row

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

Если коротких путей несколько, allShortestPaths вернёт все:

MATCH p = allShortestPaths((a:Person {name: 'Вера'})-[:KNOWS*]-(b:Person {name: 'Глеб'}))
RETURN [n IN nodes(p) | n.name] AS chain
ORDER BY chain;

+---------------------------+
| chain                     |
+---------------------------+
| ["Вера", "Аня", "Глеб"]   |
| ["Вера", "Борис", "Глеб"] |
+---------------------------+

2 rows

А если пути нет, ответ пустой. До Яны не добраться никак:

MATCH p = shortestPath((a:Person {name: 'Аня'})-[:KNOWS*]-(b:Person {name: 'Яна'}))
RETURN p;

+---+
| p |
+---+
+---+

0 rows

В Cypher 25 есть и новая запись из стандарта GQL: SHORTEST 1 перед паттерном и + после связи вместо звёздочки. Она умеет больше, например SHORTEST 3 для трёх кратчайших путей:

MATCH p = SHORTEST 1 (a:Person {name: 'Аня'})-[:KNOWS]-+(b:Person {name: 'Илья'})
RETURN length(p) AS hops;

+------+
| hops |
+------+
| 6    |
+------+

1 row

Кратчайший путь здесь считается по числу связей. Если у связей есть вес, например минуты в пути, нужен алгоритм Дейкстры, он есть в библиотеке Graph Data Science, о ней следующий урок.

Сообщества на чистом Cypher

Сообщество это группа, внутри которой связей много, а наружу мало. Серьёзные алгоритмы поиска сообществ живут в GDS, но два полезных сигнала видны и обычными запросами.

Первый сигнал это треугольники: трое, которые все знакомы друг с другом. Чем больше у человека треугольников, тем плотнее его круг:

MATCH (a:Person)-[:KNOWS]-(b:Person)-[:KNOWS]-(c:Person)-[:KNOWS]-(a)
WHERE a.name < b.name < c.name
RETURN a.name, b.name, c.name
ORDER BY b.name, c.name;

+---------------------------+
| a.name | b.name  | c.name |
+---------------------------+
| "Аня"  | "Борис" | "Вера" |
| "Аня"  | "Борис" | "Глеб" |
+---------------------------+

2 rows

Условие a.name < b.name < c.name оставляет каждый треугольник один раз, без перестановок. Оба треугольника в верхней половине клуба: Аня, Борис, Вера и Глеб образуют плотное ядро.

Второй сигнал это связность: кто вообще достижим от человека. Те, до кого от Ани нельзя дойти никакой цепочкой, живут в другой компоненте связности:

MATCH (p:Person)
WHERE NOT EXISTS { MATCH (:Person {name: 'Аня'})-[:KNOWS*1..9]-(p) }
RETURN p.name;

+--------+
| p.name |
+--------+
| "Яна"  |
+--------+

1 row

Только Яна: у неё нет связей вовсе. Сама Аня в ответ не попала, потому что до неё самой можно дойти по кругу через Бориса и Веру.

Попробуй сам

Запрос рисует кратчайшую цепочку знакомств от Ани до Ильи. На картинке видно, что вся цепочка проходит через Глеба и Дину: это мост между двумя половинами клуба.

Удали знакомство Глеба и Дины и выполни запрос снова. Потом найди кратчайший путь от Веры до Зои и посчитай его длину.

Проверь себя

Задание

Дальше

Треугольники и связность на чистом Cypher это только начало. Для настоящих графовых алгоритмов есть библиотека Graph Data Science. В следующем уроке посмотрим, как она устроена и что умеют PageRank, Louvain и их соседи.