neo4j - 优化 Cypher 查询以分析网络中的拓扑

Question

我有一个网络(例如水网络)，我想找到拓扑结构:集群(圆形路径)、桥梁(连接集群的关系)和树(其余的)。

创建示例网络的 Cypher 语句在这里。( https://www.dropbox.com/s/e1gtqxlm9ngaau5/Cypher%20to%20create%20example%20network.cql?dl=0 ) 蓝色关系是我正在寻找的集群，红色关系是桥梁，绿色关系是树木。
为了找到集群，我有两种方法，这两种方法都返回正确的结果。但两者都太慢了。
方法一:
从关系开始，看看开始和结束节点之间是否有第二条路径。
这个需要大约 10M db 命中

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

方法二:
从寻找圆形路径开始，忽略方向。 (约 12000)然后提取唯一关系。
这个需要大约 20M db 命中。

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

有没有更聪明的方法，更快地返回结果？

Answer 1

您可以使用 Strongly connected component algorithm 检测集群GDS 库中提供。我认为它符合您对集群的定义，并且也适用于您的示例。

The Strongly Connected Components (SCC) algorithm finds sets ofconnected nodes in a directed graph where each node is reachable inboth directions from any other node in the same set.

要检测桥梁，您可以使用 Betweenness centrality algorithm找到潜在的桥节点，这些节点具有连接到它们的桥接关系。这将限制在计算哪些边是桥时需要考虑的边数。不幸的是，对于一些非常小的桥，这个解决方案并不完美，假设它们只是一个或两个节点的桥，中间中心性不会那么高。并且图中间的一些节点将具有较高的介数分数，因为理论上所有信息都会流经它们。
我有另一个想法可能会很快奏效。运行强连通分量算法并将结果存储回 Neo4j。然后尝试找到连接不同节点集群的边。这将包括树木和桥梁，然后您必须决定该关系应归类为两个选项中的哪一个。