[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]
Force-Directed Graph Drawing는 그래프 시각화 중 한 방법으로써 노드들끼리는 척력을, 에지로 연결된 노드에는 인력을 적용시키는 방법입니다.
보통 노드끼리의 반발력은 전하(쿨롱의 법칙) 형태로 적용시키고, 에지로 연결된 노드끼리의 인력은 용수철(훅의 법칙) 형태로 적용시키게 됩니다.
Force-Directed Graph Drawing의 장점은 다음과 같습니다.
- 좋은 결과 : 중간 크기 정도의 그래프(50~100개의 노드)에서 통일성 있는 에지 길이와 노드 분산, 대칭성의 세 가지 기준을 굉장히 잘 만족하는 결과를 보여줍니다.
- 유연성 : 확장하기 쉽습니다. Force-Directed Graph Drawing을 확장해서 방향 그래프, 3D 그래프, 클러스터 드로잉, 동적 그래프 드로잉 등 다양한 분야에 적용시킬 수 있습니다.
- 직관성 : 용수철 등과 같은 물리 법칙을 사용하기 때문에 결과를 예상하고 이해하기 쉽습니다.
- 단순성 : 전형적인 Force-Directd Graph Drawing은 다른 그래프 시각화 방법에 비해 쉽게 구현할 수 있습니다.
- 유동성 : 알고리즘 적용 중간 과정을 보여줌으로써 사용자는 그래프가 어떻게 진화해 나가는지 관찰할 수 있습니다.
- 강력한 이론적 토대
단점은 다음과 같습니다.
- 낮은 퍼포먼스 : 전형적인 구현에서는 n을 그래프의 노드 개수라 할 때,
의 시간복잡도를 가집니다. 물리학의 N-body problem과 관련있습니다. N-body problem과 관련된 알고리즘을 사용해 시간복잡도를 낮출 수 있지만, 구현이 복잡해집니다.
- 나쁜 지역 최적해 : Force-Directed Graph Drawing은 종종 전역 최적해가 아닌 지역 최적해를 생성합니다. 이는 낮은 품질의 결과를 가져오게 됩니다. 그래프를 구성하는 노드 개수가 많아질수록 초기 상태에 더 큰 영향을 받게 됩니다.