그래프가 연결되어 있고 가장자리에 가중치가 있습니다. 모서리 사이의 무게가 작을수록 인접한 정점이 더 가깝습니다. 모든 서브 그래프의 노드가 매우 유사하도록 그래프를 k 개의 작은 서브 그래프로 나누고 싶습니다.그래프를 k 개의 유사한 서브 그래프로 나누기
즉, 그래프를 클러스터해야합니다. 그래프에 적합한 클러스터링 알고리즘을 제안하고 (O (n^2)보다 적은) 복잡성이 적은 클러스터를 제안 할 수 있습니까?
클러스터링은 일반적으로 해결할 수있는 어려운 문제입니다. exaclty brute force 만 사용하십시오. 따라서 효율적인 알고리즘의 경우 휴리스틱 접근법에 의존해야합니다. 버텍스 클러스터링 태스크로 문제를 해결할 수있는 경우 k-means과 같은 것을 시도 할 수 있지만 더 큰 데이터 세트에서는 느려질 수 있습니다.
그래프의 경우 특별히 MCL 알고리즘을 사용하는 것이 좋습니다. MCL은 많은 경우 효율적입니다. 무작위 흐름 시뮬레이션을 사용하여 가중치/비가 중 그래프로 클러스터를 탐지합니다. 기본 아이디어는 클러스터 내에서 플로우가 수집되는 반면, 클러스터 간의 링크는 포화가되지 않는 경향이 있다는 것입니다..
왜 "비슷한 노드"가 정확하게 의미합니까? –