时间戳

首页 > 解决方案 > 优化 Cypher 查询以分析网络中的拓扑

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

问题描述

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

网络

创建示例网络的 Cypher 语句在这里。（https://www.dropbox.com/s/e1gtqxlm9ngaau5/Cypher%20to%20create%20example%20network.cql?dl=0）蓝色关系是我所在的集群寻找，红色的是桥梁，绿色的是树木。

为了找到集群，我有两种方法，这两种方法都返回正确的结果。但两者都太慢了。

方法1：从关系开始，看看在开始和结束节点之间是否有第二条路径。这个需要大约 10M 分贝点击

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

方法 2：从寻找圆形路径开始，忽略方向。（大约 12000）然后提取唯一关系。这个需要大约 20M 分贝的点击量。

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

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

标签： neo4jcyphertopology

解决方案

您可以使用 GDS 库中提供的强连通分量算法检测集群。我认为它符合您对集群的定义，并且它也适用于您的示例。

强连通分量 (SCC) 算法在有向图中找到连接节点的集合，其中每个节点都可以从同一集合中的任何其他节点在两个方向上到达。

为了检测桥梁，您可以使用中介中心性算法来查找潜在的桥梁节点，这些节点具有与其连接的桥梁关系。这将限制在计算哪些边是桥时需要考虑的边数。不幸的是，这个解决方案对于一些非常小的桥来说并不完美，假设它们是一个只有一个或两个节点的桥，中介中心性不会那么高。图中间的一些节点会有很高的介数分数，因为理论上所有的信息都会流过它们。

我有另一个想法可能会很快奏效。运行强连通分量算法并将结果存储回 Neo4j。然后尝试找到连接不同节点集群的边。这将包括树木和桥梁，然后您必须决定应将关系分类为两个选项中的哪一个。

推荐阅读