Оптимизация запроса Cypher для анализа топологии сети

У меня есть сеть (например, сеть водоснабжения), и я хочу найти топологические структуры: кластеры (круговые пути), мосты (отношения, соединяющие кластеры) и деревья (остальные).

сеть

Оператор Cypher для создания примера сети находится здесь. nofollow noreferrer">https://www.dropbox.com/s/e1gtqxlm9ngaau5/Cypher%20to%20create%20example%20network.cql?dl=0) Синие отношения — это кластеры, которые я ищу, красные - мосты, а зеленые - деревья.

Чтобы найти кластеры, у меня есть два подхода, оба из которых возвращают правильные результаты. Но оба слишком медленные.

Подход 1: Начните с отношений и посмотрите, есть ли второй путь между начальным и конечным узлами. Это занимает около 10 миллионов ударов дБ

MATCH (n:WN)-[r:PIPE]->(m:WN) 
WHERE EXISTS((n)-[r]->(m)-[:PIPE*2..]-(n))
RETURN r

Подход 2: Начните с поиска круговых путей, игнорируя направления. (около 12000), а затем извлеките уникальные связи. Это занимает около 20 миллионов ударов дБ.

MATCH path=(n:WN)-[:PIPE*..]-(n)
RETURN 
     apoc.coll.subtract(
          apoc.coll.flatten(COLLECT(relationships(path))
          ),
          []
     )
    AS clusterRelationships

Есть ли более разумный подход, дающий результаты быстрее?


neo4j topology cypher
person Graphileon    schedule 29.08.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Алгоритм Strongly Connected Components (SCC) находит наборы связанных узлов в ориентированном графе, где каждый узел достижим в обоих направлениях из любого другого узла в том же наборе.

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

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

person Tomaž Bratanič    schedule 31.08.2020
comment
Привет, спасибо за ваши комментарии. SCC обнаруживает только наборы узлов, в которых каждая пара узлов соединена, что не так. Из neo4j.com/docs/graph-data- science/current/algorithms/: Алгоритм SCC находит максимальные наборы связанных узлов в ориентированном графе. Набор считается компонентом сильной связности, если существует направленный путь между каждой парой узлов в наборе. Он часто используется в начале процесса анализа графа, чтобы помочь нам понять, как устроен наш граф. Кроме того, мне нужно, чтобы он был ненаправленным. - person Graphileon; 31.08.2020
comment
Когда у меня есть кластеры, найти мосты не проблема, как показано на рисунке (он генерируется динамически). - person Graphileon; 31.08.2020