neo4j - 如何在 Neo4j 中找到关键节点？

Question

所以，假设一个非常简单的图

(A)->(B)->(D)->(E) | (A)->(C)->(D)->(E)

<>-如果您将其可视化，它将看起来像。

图表中的关键节点是一个如果您将其删除，您现在将拥有 2 个图表。（AKA，单点故障）

所以在这个例子中，E 不是关键的，因为它是一个叶子，而 B 和 C 不是关键的，因为 A 和 D 仍然通过另一个节点连接。D 很关键，因为删除它会使 E 从图中的其余部分孤立出来。

使用 Cypher，我如何找到关键节点？（在这种情况下，D）

---

我的第一直觉是走所有路径，并计算每个节点被触摸的次数，但这将是非常低效和不可靠的。我的第二个直觉是WHERE NONE (n in path WHERE NOT n in OTHER_PATHS)，但即使我能弄清楚如何使这项工作发挥作用，我也不知道路径中的哪个节点是关键的。

我找到了这个博客，但似乎假设您已经对关键节点有所了解。

标签： neo4jcypher

Answer 1

我们可以通过它的定义来解决这个问题：

图表中的关键节点是一个如果您将其删除，您现在将拥有（至少）2 个图表。

或者换一种说法，如果所有节点最初都可以相互访问，并且如果我们删除了一个节点，这会改变图中任何其他节点可访问的节点数，那么该删除的节点就是关键节点。

仅通过 Cypher 尝试此操作的最大障碍是 Cypher 可变长度路径匹配旨在查找所有可能的路径，因此查找所有可到达节点的效率低下。

使用APOC 路径扩展程序，我们可以更改遍历期间使用的唯一性，因此我们只找到到每个不同节点的单个路径并忽略所有其他节点，减少我们需要探索的路径数量，从而更快地找到所有可到达的节点图中的节点。

使用这个，我们可以首先计算图中的所有节点，然后对于每个节点，查看在扩展期间将该节点列入黑名单（有效地查看当我们删除节点时会发生什么）导致从另一个节点扩展以找到小于整个图（- 1 当然，对于我们“删除”的节点）。

您需要使用比 Summer 2018 版本更新的 APOC 版本（>= 3.3.0.4 在 3.3.x 行上，或 >= 3.4.0.2 在 3.4.x 行上）才能使用此方法，作为blacklistNodes功能我们需要在此版本中添加。

这是一般方法，假设我们正在考虑所有节点，并且图中的所有节点最初都可以相互访问。

MATCH (n)
WITH collect(n) as allNodes
WITH allNodes, size(allNodes) - 1 as totalNodes, allNodes[..2] as startNodes
// using total as one less than the actual total since we're 'removing' a node.
// 2 potential start nodes so we always have one if the other is to be removed.
UNWIND allNodes as nodeToRemove
// we now have each node in the graph on its row, we'll try removing each one
WITH [node in startNodes WHERE node <> nodeToRemove][0] as startNode, nodeToRemove, totalNodes
CALL apoc.path.subgraphNodes(startNode, {blacklistNodes:[nodeToRemove]}) YIELD node
WITH totalNodes, nodeToRemove, count(node) as reachableNodes
WHERE totalNodes <> reachableNodes
RETURN nodeToRemove as criticalNode