Neo4jグラフデータベースのノードの集合をm個の別々のクラスタに分割する方法

Question

私の問題では、n個のノードがあります。各ノードは、任意の2つのノードAおよびBについての類似関数S（A、B）によって他のすべてのノードに関連する。この関係は「Is Similar To」であり、この関係の特性は類似性-S（A、B ）。各ノードは唯一つのクラスタに属し、

クラスタが全て同じである

• ：ように私は（M等しいサイズのセットにノードをパーティション）ノードのM個のクラスタを生成しますサイズ（ NモッドのM> 0 <場合、一部は他から1によって変えることができる）

そしてAVG（C）は、クラスタC内のノードのすべての対の間の平均類似性である場合、私は「平均を望んすべてのthの平均類似度の類似度eクラスタは可能な限り小さく、上記の2つの条件を満たしている必要があります。私はCypherでこれをどうやってやるかを考えようとしています。任意のアイデアをいただければ幸いです。

Answer 1

これは少なくともNP困難です。

したがって、大きなグラフで許容できる時間内に最適な解を見つけるアルゴリズムはありません。既知の唯一の正確なアルゴリズムは、すべての組み合わせを試すよりはるかによくない可能性があります。