연결된 거리를 기반으로 K-means plus plus 클러스터링 알고리즘을 사용하여 클러스터 만들기

Question

서로 연결된 노드 세트 (약 10K)가 있습니다. 나는 작은 클러스터 (최대 15 노드)를 만들어야한다.

지형 공간 거리 대신 연결된 거리를 사용하여 (Dijkstra 최단 경로 알고리즘 사용) 연결 거리를 사용하고 있습니다. 이제는 K-means plus plus 알고리즘을 사용하여 작은 클러스터를 만드는 데 1 시간 이상 걸립니다. 두 노드 사이의 최단 거리를 찾는 데 더 많은 시간이 걸린다는 것을 알고 있습니다. 처음에 최단 경로를 모두 저장하려면 더 많은 메모리가 필요합니다 (불가능). 누구나 내가 이것을 어떻게 최적화 할 수 있는지 제안 할 수 있습니까?

Answer 1

그래프의 모든 노드에 대해 dykstras 알고리즘을 실행해야합니다. Dykstras 알고리즘은 조밀 한 그래프에서 O (n^2 * log n) 시간을 필요로합니다. 어떤 결과가 O (n^3 * log n)로 이어지며, 영원히 걸립니다. Floyd-Warshall (https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) 알고리즘을 사용하여 이것을 전처리로 O (n^3)로 바꾼 다음이 알고리즘을 사용하면 꽤 오래 걸릴 수 있습니다. 이것에 대한 긍정적 인 점은 O (n^2) 메모리를 사용하여 메모리를 가장 효율적으로 저장할 수 있다는 것입니다.

밀도가 높은 그래프의 모든 쌍 최단 경로 문제에 더 좋은 방법은 없습니다.