Neo4j 그래프 데이터베이스의 노드 집합을 m 개의 개별 클러스터로 분할하는 방법

Question

내 문제는 n 개의 노드가 있습니다. 각 노드는 임의의 두 노드 A와 B에 대한 유사 함수 S (A, B)에 의해 모든 다른 노드와 관련됩니다. 관계는 "Is Is To"이고이 관계의 속성은 S (A, B).

• 각 노드 하나에 속하고 하나 개의 클러스터 및

• 클러스터가 모두 동일 : 나는 m 노드의 클러스터 (m 같은 크기의 세트로 노드를 분할) 그래서를 생성 할 AVG (C)는 클러스터 C의 노드의 각 쌍 사이의 평균 유사성 경우

  이어서

, 그때의 평균을 원하는 크기는 "( N의 MOD m은 <> 0이 경우 몇몇은 다른 1 개에 따라 다를 수 있음) 유사도 "의 평균 유사도 e 클러스터는 가능한 작고 위의 두 가지 조건을 충족시킵니다. 나는 사이퍼를 어떻게 할 것인지 알아 내려고 노력 중이다. 어떤 아이디어라도 감사 할 것입니다.

Answer 1

적어도 NP 하드 일 가능성이 큽니다.

따라서 큰 그래프에서 허용 가능한 시간에 최상의 솔루션을 찾는 알고리즘을 찾을 수 없습니다. 유일하게 알려진 정확한 알고리즘은 모든 조합을 시도하는 것보다 훨씬 낫지는 않습니다.