如何在Neo4j中查找关键节点？

Question

假设有一个非常简单的图形

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

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

图中的关键节点是指，如果您删除它，则现在将有2个图形。 （也就是说，单一故障点）

所以在这个例子中，E不是关键的，因为它是叶子节点，B和C也不是关键的，因为A和D仍然通过其他节点连接。但是，D是关键的，因为删除它将使E与图的其余部分失去联系。

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

---

我的第一反应是走所有路径，并计算每个节点被访问的次数，但这样做非常低效且不可靠。我的第二反应是类似于WHERE NONE (n in path WHERE NOT n in OTHER_PATHS)，但即使我能弄清楚如何让它起作用，我也不知道路径中哪个节点是关键的。

我找到了this博客，但它似乎假定你已经知道一些关键节点的知识。

- Tezra

---

请记住，关键节点问题是NP完全问题，这种问题不会有快速的可扩展解决方案。 - InverseFalcon

@InverseFalcon 是的，但我能想到的所有方法都非常不专业/容易出错。我并不指望图形太大，我只需要一个可靠的解决方案。 - Tezra

Answer 1

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

在图中，关键节点是指当你移除它时，你现在会有（至少）两个图。

或者换句话说，如果最初所有节点都可以相互到达，如果我们删除一个节点，并且这改变了任何其他节点在图中可到达的节点数量，则该已删除节点为关键节点。

通过Cypher单独尝试此操作的难点在于，Cypher变量长度路径匹配旨在找到所有可能的路径，因此在查找所有可到达节点时效率不高。

使用 APOC Path expander procedures，我们可以更改遍历期间使用的唯一性，以便我们仅找到通向每个不同节点的单个路径并拒绝所有其他路径，缩减我们需要探索的路径数，从而使其在图中查找所有可到达的节点时更快。

使用此方法，我们首先可以计算出图中的所有节点，然后对于每个节点，看看在扩展过程中黑名单化该节点（有效地查看我们删除该节点会发生什么）是否会导致从另一个节点进行扩展发现少于整个图的节点数（当然要减去我们“删除”的节点数）。

您需要使用比2018年夏季版本更新的APOC版本（3.3.x线上的 >= 3.3.0.4 或者3.4.x线上的 >= 3.4.0.2）才能使用此方法，因为我们需要的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

- InverseFalcon

Answer 2

首先，您需要确定图中节点的类型：如果所有节点都是相同类型，则可以计算它们的所有关系（或特定关系）；如果一个节点有超过n个关系（可能是2个），则它可能是关键节点，否则此节点不是关键节点。

但是，如果您有多种类型的节点，则需要确定哪些类型的节点和关系更重要，然后查询每种类型的节点和关系，并最终计算它们与所有类型的节点或特定节点的关系（所有关系或特定关系）。

MATCH (n)-[r]->() RETURN COUNT(r)

如果该节点被认为不是关键节点，您可以继续删除此节点。

- juanbits

---

如何通过关系计数来判断节点是否关键？这似乎更容易出错。 - Tezra

Answer 3

我发现如何进行基于路径的过滤，其中条件需要在每条可能的路径上都为真。您可以在谓词中使用模式识别来在所有路径上进行过滤。（对于我的集合，我使用合理的路径长度限制来限制失控。如果我的图中存在替代路径，我期望会有一个短暂的绕路。因此，请根据您的期望进行调整）

MATCH (a)-[*..10]->(c)-[*..10]->(b) 
WHERE ALL(p in (a)-[*..20]->(b) WHERE c in NODES(p)) 
RETURN DISTINCT c

---

我也尝试过像这样使用allShortestPaths，但在我的示例集中，性能实际上更差。不同情况可能会有不同结果。

MATCH (a)-[*..10]->(c)-[*..10]->(b) 
WHERE ALL(p in allShortestPaths((a)-[*..20]->(b)) WHERE c in NODES(p)) 
RETURN DISTINCT c

- Tezra