Neo4j Cypher：切断されたサブグラフを高速に見つける

Question

私は100万のノードを持つグラフを持っています。その中には多くの切断された部分グラフがあります。私は最大の切断されたサブグラフが何であるか知っています。

たとえば、私はこれを試してみました7.

我々は、3つの切断部分グラフを得た。このグラフの例では、これは、この場合の出力は次のようになりますので、それは長い時間がかかっている、

match p =()-[*]-() return MAX(length(p)) as l order by l desc limit 1 

Answer 1

クエリは、接続されている最大のサブグラフのサイズではなく、2つの別々のノード間で最長のパスのみを返します。

残念ながら、Neo4jは現在、サブグラフ操作のネイティブサポートを持っていません。また、APOCプロシージャーにはここでは何もありません。

Cypherには部分グラフを見つける方法がありますが、私が考えることができるクエリは高速ではなく、大きなグラフではタイムアウトする可能性があります。ここで一つだ、と再び、これは推奨されません、素晴らしいそれはあなたのためにタイムアウトに思われるが、それは動作するかどうか：

MATCH (n)-[*0..]-(subgraphNode) 
WITH n, COUNT(DISTINCT subgraphNode) as subSize 
RETURN MAX(subSize) 

これは、クエリではなく、時々頻繁に実行するか、またはする場合あなたのサブグラフを追跡する方法をお勧めします。

サブグラフトラッキングを作成するアプローチを提供することはできますが、グラフ操作（サブグラフをマージしたり、より小さなサブグラフに分割したり、新しいサブグラフを作成する）で更新されたままにする方法は難しくなります。これを維持するためにトランザクション後の処理を実行するには、ある種のJava拡張が必要になるでしょう。

また、この方法は、書き込み操作が行われていないときにメンテナンスウィンドウで行うのが最適です。

最後の目標は、切断されたすべてのサブグラフに単一のサブグラフノードを追加することです。切断されたサブグラフを最大に見つける場合を含めて、サブグラフに対する将来の操作が簡単になります。

この目標を達成するための全体的なアプローチは、まず、グラフ内のすべてのノードにラベルを付け（未処理のようなラベルを付けて）、次のバッチクエリでラベルを付けます。未処理ノード、 Subgraphノードを添付して、次のものを削除します。サブグラフから未処理のラベルを削除します。

だから、まず、あなたのDB内のすべてのノードレーベル：

MATCH (n) 
SET n:Unprocessed 

次に、バッチ操作を。 APOCプロシージャを使用して、バッチ処理を可能にしたいとします（未処理のラベルから処理されているサブグラフ全体を利用します：処理していないラベル...サブグラフに対する操作を重複して実行したくありません）。

CALL apoc.periodic.commit(" 
// only process a batch of :Unproccessed nodes at a time 
MATCH (n:Unprocessed) 
WITH n LIMIT {limit} 
// subgraphNode will be all nodes in the subgraph including n 
MATCH (n)-[*0..]-(subgraphNode) 
WITH DISTINCT n, subgraphNode 
REMOVE subgraphNode:Unprocessed 
// find attach point node in each subgraph with smallest id 
WITH n, min(id(subgraphNode)) as attachId 
WITH DISTINCT attachId 
MATCH (attachNode) 
WHERE id(attachNode) = attachId 
CREATE (attachNode)<-[:SUBGRAPH]-(:Subgraph) 
RETURN count(*) 
",{limit:100}) 

必要に応じて制限を調整できます。同じサブグラフのノード上での冗長な操作を減らすことができるので、下限は実際にはより良く機能するかもしれません。

すべての切断されたサブグラフには：サブグラフノードが添付されているため、各サブグラフに対してより迅速で簡単なクエリを作成できます。

MATCH (sub:Subgraph)-[*]-(subgraphNode) 
WITH sub, COUNT(DISTINCT subgraphNode) as subSize 
RETURN MAX(subSize) 

EDIT

私は、変数関係の一致を使用する場合と比較して収集部分グラフノードの高速化手段を見つけた：だから、最大の切断部分グラフを見つけるために、あなたが使用する可能性があります。 APOCのパスエクスパンダ機能は、NODE_GLOBALの一意性を使用してより高速に実行する必要があります。このアプローチを使用するために変更された関連クエリがここにあります。

CALL apoc.periodic.commit(" 
// only process a batch of :Unproccessed nodes at a time 
MATCH (n:Unprocessed) 
WITH n LIMIT {limit} 
// subgraphNode will be all nodes in the subgraph including n 
CALL apoc.path.expandConfig(n,{bfs:true, uniqueness:"NODE_GLOBAL"}) 
    YIELD path 
WITH n, LAST(NODES(path)) as subgraphNode 
REMOVE subgraphNode:Unprocessed 
// find attach point node in each subgraph with smallest id 
WITH n, min(id(subgraphNode)) as attachId 
WITH DISTINCT attachId 
MATCH (attachNode) 
WHERE id(attachNode) = attachId 
CREATE (attachNode)<-[:SUBGRAPH]-(:Subgraph) 
RETURN count(*) 
",{limit:100}) 

そして、各部分グラフの処理：

MATCH (sub:Subgraph) 
CALL apoc.path.expandConfig(sub,{minLevel:1, bfs:true, uniqueness:"NODE_GLOBAL"}) 
    YIELD path 
WITH sub, LAST(NODES(path)) as subgraphNode 
WITH sub, COUNT(DISTINCT subgraphNode) as subSize 
RETURN MAX(subSize)