그래프 분할
그래프 분할은 그래프 이론 및 컴퓨터 과학 분야에서 중요하게 다루어지는 문제 중 하나이다. 주어진 그래프의 정점(vertex) 집합을 하나 이상의 서로소인(disjoint) 부분 집합(partition)으로 나누는 것을 의미하며, 이 과정에서 특정 기준을 최적화하는 것을 목표로 한다.
가장 일반적인 목표는 분할된 부분 집합들 간의 연결(간선, edge) 수를 최소화하는 동시에, 각 부분 집합에 속한 정점의 수나 가중치 합이 특정 제약 조건(예: 각 부분의 크기가 거의 같거나 특정 크기 이하)을 만족하도록 하는 것이다. 이렇게 부분들 사이의 연결(이를 '컷(cut)'이라고 한다)을 최소화함으로써, 각 부분 내에서의 계산이나 상호작용은 많고 부분들 간의 상호작용은 적게 만들 수 있다.
그래프 분할 문제는 병렬 컴퓨팅에서의 작업 분배, VLSI(초고밀도 집적회로) 설계, 스파스 행렬 계산, 네트워크 분석(커뮤니티 검출 등), 데이터베이스 분산 등 다양한 분야에서 핵심적인 역할을 한다. 예를 들어, 병렬 컴퓨팅에서는 전체 계산 작업을 그래프로 표현하고, 각 프로세서에 할당할 부분 집합으로 분할하여 프로세서 간 통신량을 최소화하는 방식으로 활용된다.
문제 정의
일반적으로 그래프 분할 문제는 그래프 G=(V, E)가 주어졌을 때, 정점 집합 V를 k개의 서로소인 부분 집합 V₁, V₂, ..., Vk로 나누는 것으로 정의된다. 이때 V = V₁ ∪ V₂ ∪ ... ∪ Vk 이고, 임의의 i ≠ j에 대해 Vi ∩ Vj = ∅ 이다. 목표는 이러한 분할 중에서 다음 조건을 만족하는 것을 찾는 것이다:
- 컷 최소화: 서로 다른 부분 집합에 속한 두 정점을 연결하는 간선들의 집합(컷)의 크기(간선의 수 또는 가중치 합)를 최소화한다.
- 균형 제약: 각 부분 집합 Vi의 크기(|Vi|) 또는 정점 가중치의 합이 특정 제약 조건(예: 전체 정점 수/k ± 허용 오차)을 만족한다.
가장 흔하게 다루어지는 경우는 k=2인 이등분(bisection) 문제이다.
응용 분야
- 병렬 컴퓨팅: 대규모 과학 계산, 시뮬레이션 등에서 계산 부하를 여러 프로세서에 효율적으로 분배하고 프로세서 간 통신량을 줄이기 위해 사용된다.
- VLSI 설계: 집적 회로 레이아웃에서 회로를 여러 블록으로 분할하여 칩 영역에 배치하고 배선 길이를 최적화하는 데 사용된다.
- 네트워크 분석: 소셜 네트워크, 웹 그래프, 생물학적 네트워크 등에서 자연스러운 그룹(커뮤니티 또는 클러스터)을 식별하는 데 활용될 수 있다.
- 데이터베이스 분산: 대규모 데이터를 여러 서버에 저장할 때 데이터 접근 패턴을 그래프로 모델링하여 효율적인 데이터 분산 전략을 수립하는 데 사용된다.
알고리즘
그래프 분할 문제는 균형 제약을 만족하면서 컷을 최소화하는 것은 일반적으로 NP-난해(NP-hard) 문제임이 알려져 있다. 따라서 최적해를 찾기보다는 효율적인 휴리스틱 또는 근사 알고리즘이 주로 사용된다.
- 커니핸-린 알고리즘 (Kernighan-Lin algorithm): 초기 분할에서 시작하여 반복적으로 정점 쌍을 교환하며 컷 크기를 줄이는 지역 탐색 기반의 휴리스틱 알고리즘이다.
- 피두시아-마테이제스 알고리즘 (Fiduccia-Mattheyses algorithm): 커니핸-린 알고리즘을 개량하여 한 번에 하나의 정점만 이동시키고 게인(gain) 값을 활용하여 효율성을 높인 알고리즘이다.
- 스펙트럼 분할 (Spectral partitioning): 그래프의 라플라시안 행렬의 고유 벡터(특히 두 번째로 작은 고유값에 해당하는 고유 벡터)를 사용하여 정점을 실수 공간에 임베딩한 후 분할하는 방법이다.
- 멀티레벨 분할 (Multilevel partitioning): 그래프를 순차적으로 단순화(coarsening)하여 더 작은 그래프를 만든 뒤, 작은 그래프를 분할하고 이를 원래 그래프로 되돌리면서(refinement) 분할을 개선하는 방식의 알고리즘군이다. METIS, Scotch 등의 라이브러리가 이러한 접근 방식을 사용한다.
관련 문제
그래프 분할과 밀접하게 관련된 문제로는 크기 제약이 없는 최소 컷 문제나 데이터의 자연스러운 그룹을 찾는 클러스터링 문제가 있다. 특히, 이등분 문제는 크기 제약이 있는 최소 컷 문제로 간주될 수 있다.
그래프 분할은 이론적인 연구와 실제 응용 모두에서 활발히 연구되는 중요한 분야이다.