그래프 분할

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 분할은 주어진 그래프를 특정 기준에 따라 여러 부분으로 나누는 문제로, 일반적으로 NP-난해 문제에 속한다. 이 문제의 목표는 분할된 구성 요소 간의 간선 용량을 최소화하거나, 균형 잡힌 분할을 수행하는 것이다. 그래프 분할은 지역적 방법과 전역적 방법으로 나뉘며, 스펙트럼 분할과 같은 전역적 방법은 그래프 라플라시안 행렬의 고유값을 활용한다. 그래프 분할은 컨덕턴스, 면역, 소프트웨어 도구 등 다양한 응용 분야에서 활용된다.

그래프 분할

정의	그래프의 정점들을 서로소 집합들로 분할하는 것
목표	분할된 집합들 간의 연결을 최소화하고 각 집합의 크기를 균등하게 유지하는 것

종류

정점 분할	정점들을 분할
에지 분할	에지들을 분할

응용 분야

병렬 컴퓨팅	계산 작업을 여러 프로세서에 분산
데이터 마이닝	데이터 클러스터링 및 패턴 인식
이미지 분할	이미지 내 객체 분리
소셜 네트워크 분석	커뮤니티 구조 발견

알고리즘

Kernighan-Lin 알고리즘	국소 탐색 기반의 휴리스틱 알고리즘
Fiduccia-Mattheyses 알고리즘	Kernighan-Lin 알고리즘의 개선 버전
멀티레벨 분할	그래프를 축소하고 분할한 후 다시 확장하는 방식
스펙트럴 분할	그래프의 라플라시안 행렬의 고유 벡터를 이용하는 방식
균형 컷	그래프를 두 부분으로 나누어 각 부분의 크기를 균형있게 유지
최소 컷	그래프를 두 부분으로 나누어 두 부분 사이의 에지 수를 최소화

평가 기준

컷 크기	분할된 집합들 간의 에지 수
균형도	각 집합의 크기가 얼마나 균등한지
실행 시간	알고리즘의 실행 시간

📚 더 읽어볼만한 페이지

그래프 이론의 계산 문제 - 외판원 문제
그래프 이론의 계산 문제 - 해밀턴 경로
해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩 방문하는 경로로, 해밀턴 순환은 이러한 경로가 순환 형태를 띠는 것을 의미하며, 이들은 그래프 이론에서 중요한 개념으로 NP-완전 문제 및 외판원 문제 등에 응용된다.
NP-완전 문제 - 지뢰 찾기
지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
NP-완전 문제 - 스도쿠
스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.

2. 문제 복잡도

일반적으로 그래프 분할 문제는 NP-난해 문제 범주에 속하며, 이러한 문제에 대한 해는 휴리스틱 및 근사 알고리즘을 사용하여 도출된다.

특정 (k, 1 + ε) 균형 분할 문제의 경우, 각 구성 요소가 최대 (1 + ε)·(n/k)개의 노드를 포함하는 G를 k개의 구성 요소로 분할하는 최소 비용을 찾는다. 이 근사 알고리즘의 비용은 (k, 1) 컷의 비용과 비교하는데, 여기서 각 k개의 구성 요소는 각각 (n/k)개의 동일한 크기의 노드를 가져야 하므로 더 제한적인 문제이다. 따라서,

: $\max_i |V_i| \le (1+\varepsilon) \left\lceil\frac$

👆

좌우로 밀어서 보기

{k}\right\rceil.

(2,1) 컷이 최소 이분 문제이며 NP-완전 문제임을 이미 알고 있다. n = 3k인 3-분할 문제를 평가하는데, 이는 다항 시간 내에 경계가 정해진다. 만약 (k, 1)-균형 분할에 대한 유한 근사 알고리즘을 가지고 있다고 가정하면, 3-분할 인스턴스는 G에서 균형 (k, 1) 분할을 사용하여 해결되거나 해결될 수 없다. 3-분할 인스턴스를 해결할 수 있다면, G의 (k, 1)-균형 분할 문제는 어떤 가장자리도 자르지 않고 해결될 수 있다. 그렇지 않고 3-분할 인스턴스를 해결할 수 없는 경우, G에서 최적의 (k, 1)-균형 분할은 적어도 하나의 가장자리를 자르게 된다. 유한 근사 인수를 가진 근사 알고리즘은 이 두 경우를 구별해야 한다. 따라서, 이는 3-분할 문제를 해결할 수 있는데, 이는 P = NP라는 가정 하에서 모순된다. 결론적으로, P = NP가 아닌 한 (k, 1)-균형 분할 문제는 유한 근사 인수를 가진 다항 시간 근사 알고리즘을 갖지 않는다는 것이 명백하다.

평면 분할 정리는 모든 n-정점 평면 그래프가 O(

\sqrt{n}

)개의 정점을 제거하여 대략 동일한 부분으로 분할될 수 있다고 명시한다. 이것은 분할 집합이 가장자리가 아닌 정점으로 구성되기 때문에 위에서 설명한 의미의 분할은 아니다. 그러나, 동일한 결과는 또한 유한 차수의 모든 평면 그래프가 O(

\sqrt{n}

)개의 가장자리를 가진 균형 컷을 갖는다는 것을 의미한다.

2.1. 균형 그래프 분할

그래프 분할 문제는 일반적으로 NP-난해 문제에 속한다. 따라서 이러한 문제의 해는 보통 휴리스틱이나 근사 알고리즘을 사용하여 구한다. 그러나 균등 그래프 분할 또는 균형 그래프 분할 문제는 임의의 유한 계수 내에서 근사하는 것이 NP-완전임이 밝혀질 수 있다. P=NP가 아니라면, 트리 및 그리드와 같은 특수한 그래프 종류에 대해서도 합리적인 근사 알고리즘이 존재하지 않는다. 그리드는 유한 요소 모델(FEM) 시뮬레이션에서 생성되는 그래프를 모델링하기 때문에 특히 흥미로운 경우이다. 구성 요소 간의 에지 수뿐만 아니라 구성 요소의 크기도 근사될 때, 이러한 그래프에 대해 합리적인 완전 다항식 시간 알고리즘이 존재하지 않는다는 것을 보일 수 있다.

2.2. 특수 그래프

그래프 분할 문제는 일반적으로 NP-난해 문제에 속하며, 이에 대한 해는 주로 휴리스틱이나 근사 알고리즘을 통해 구해진다. 그러나 균등 그래프 분할 또는 균형 그래프 분할 문제는 임의의 유한 계수 내에서 근사하는 것이 NP-완전임이 밝혀졌다. P=NP가 아니라면, 트리 및 그리드와 같은 특수한 그래프 종류에 대해서도 합리적인 근사 알고리즘이 존재하지 않는다. 그리드는 특히 유한 요소 모델(FEM) 시뮬레이션에서 생성되는 그래프를 모델링하기 때문에 흥미로운 경우이다. 구성 요소 간의 에지 수뿐만 아니라 구성 요소의 크기도 근사될 때, 이러한 그래프에 대해 합리적인 완전 다항식 시간 알고리즘이 존재하지 않는다는 것을 보일 수 있다.

3. 문제 정의

그래프 G = (V, E)가 주어졌을 때, V는 n개의 정점 집합, E는 간선 집합을 나타낸다. (k,v) 균형 분할 문제의 목표는 G를 최대 v · (n/k) 크기를 갖는 k개의 구성 요소로 분할하면서, 서로 다른 구성 요소 간의 간선 용량을 최소화하는 것이다.

또한, G와 정수 k > 1이 주어지면, V를 서로소(공통 원소가 없는)이며 크기가 같은 k개의 부분 집합 V₁, V₂, ..., V_k로 분할하고, 서로 다른 부분 집합에 끝점을 가진 간선의 수를 최소화하는 문제로도 정의할 수 있다. 이러한 분할 문제는 양면성 근사 또는 자원 증강 접근 방식으로 연구되었다.

일반적으로 간선이 두 개 이상의 정점을 연결할 수 있는 하이퍼그래프로 확장할 수 있다. 하이퍼에지는 모든 정점이 하나의 분할에 속하면 잘리지 않고, 그렇지 않으면 각 부분에 있는 정점 수에 관계없이 정확히 한 번 잘린다. 이러한 방식은 전자 설계 자동화 분야에서 널리 사용된다.

3.1. (''k'',''v'') 균형 분할

(k,v) 균형 분할 문제는 그래프 G = (V, E)를 k개의 구성 요소로 분할하는 문제이다. 여기서 V는 n개의 정점 집합, E는 간선 집합을 나타낸다. 목표는 각 구성 요소의 크기가 최대 v · (n/k)가 되도록 하면서, 서로 다른 구성 요소 사이에 있는 간선 용량을 최소화하는 것이다.

그래프 G와 정수 k > 1이 주어지면, V를 서로소이며 크기가 같은 k개의 부분 집합 V₁, V₂, ..., V_k로 분할하고, 서로 다른 부분 집합에 끝점을 가진 간선의 수를 최소화하는 문제로도 볼 수 있다. 이 문제는 양면성 근사 또는 자원 증강 접근 방식으로 연구되었다.

일반적으로 간선이 두 개 이상의 정점을 연결할 수 있는 하이퍼그래프로 확장할 수 있다. 하이퍼에지는 모든 정점이 하나의 분할에 있으면 잘리지 않고, 그렇지 않으면 각 측면에 있는 정점 수에 관계없이 정확히 한 번 잘린다. 이러한 방식은 전자 설계 자동화에서 흔히 사용된다.

특정 (k, 1+ε) 균형 분할 문제는 각 구성 요소가 최대 (1+ε)·(n/k)개의 노드를 포함하는 G를 k개의 구성 요소로 분할하는 최소 비용을 찾는 문제이다. 이 근사 알고리즘의 비용은 각 k개의 구성 요소가 각각 (n/k)개의 동일한 크기의 노드를 가져야 하는 (k,1) 컷의 비용과 비교되는데, 이는 더 제한적인 문제이다. 따라서,

: $\max_i |V_i| \le (1+\varepsilon) \left\lceil\frac$

👆

좌우로 밀어서 보기

{k}\right\rceil.

(2,1) 컷은 최소 이분 문제이며 NP-완전 문제임을 이미 알고 있다. n = 3k인 3-분할 문제는 다항 시간 내에 경계가 정해진다. (k, 1)-균형 분할에 대한 유한 근사 알고리즘이 있다고 가정하면, 3-분할 인스턴스는 G에서 균형 (k,1) 분할을 사용하여 해결되거나 해결될 수 없다. 3-분할 인스턴스를 해결할 수 있다면, G의 (k, 1)-균형 분할 문제는 어떤 가장자리도 자르지 않고 해결될 수 있다. 그렇지 않으면, 3-분할 인스턴스를 해결할 수 없는 경우, G에서 최적의 (k, 1)-균형 분할은 적어도 하나의 가장자리를 자르게 된다. 유한 근사 인수를 가진 근사 알고리즘은 이 두 경우를 구별해야 한다. 따라서, 이는 3-분할 문제를 해결할 수 있는데, 이는 P = NP라는 가정 하에서 모순된다. 따라서, P = NP가 아닌 한 (k,1)-균형 분할 문제는 유한 근사 인수를 가진 다항 시간 근사 알고리즘을 갖지 않는다는 것이 명백하다.

평면 분할 정리는 모든 n-정점 평면 그래프가 O(

\sqrt{n}

\sqrt{n}

)개의 가장자리를 가진 균형 컷을 갖는다는 것을 의미한다.

3.2. 균등 분할

(k,v) 균형 분할 문제의 목표는 그래프 G = (V, E)를 크기가 최대 v · (n/k)인 k개의 구성 요소로 분할하면서, 별개의 구성 요소 간의 간선 용량을 최소화하는 것이다. 여기서 V는 n개의 정점 집합을 나타내고, E는 간선 집합을 나타낸다. 또한, G와 정수 k > 1이 주어졌을 때, V를 서로소이며 크기가 같은 k개의 부분(부분 집합) V₁, V₂, ..., V_k로 분할하고, 서로 다른 부분에 끝점을 가진 간선의 수를 최소화한다. 이러한 분할 문제는 양면성 근사 또는 자원 증강 접근 방식으로 문헌에서 논의되었다. 일반적인 확장은 간선이 두 개 이상의 정점을 연결할 수 있는 하이퍼그래프로의 확장이다. 하이퍼에지는 모든 정점이 하나의 분할에 있는 경우 잘리지 않으며, 그렇지 않으면 각 측면에 있는 정점 수에 관계없이 정확히 한 번 잘린다. 이러한 사용법은 전자 설계 자동화에서 흔히 볼 수 있다.

특정 (k, 1 + ε) 균형 분할 문제의 경우, 각 구성 요소가 최대 (1 + ε)·(n/k)개의 노드를 포함하는 G를 k개의 구성 요소로 분할하는 최소 비용을 찾고자 한다. 이 근사 알고리즘의 비용은 (k,1) 컷의 비용과 비교하는데, 여기서 각 k개의 구성 요소는 각각 (n/k)개의 동일한 크기의 노드를 가져야 하므로 더 제한적인 문제이다. 따라서,

: $\max_i |V_i| \le (1+\varepsilon) \left\lceil\frac$

👆

좌우로 밀어서 보기

\sqrt{n}

)개의 정점을 제거하여 대략 동일한 부분으로 분할될 수 있다고 명시한다. 이것은 위에서 설명한 의미의 분할이 아닌데, 분할 집합이 가장자리가 아닌 정점으로 구성되기 때문이다. 그러나, 동일한 결과는 또한 유한 차수의 모든 평면 그래프가 O(

\sqrt{n}

)개의 가장자리를 가진 균형 컷을 갖는다는 것을 의미한다.

3.3. 하이퍼그래프 분할

그래프 G = (V, E)를 고려해 보자. 여기서 V는 n개의 정점 집합을 나타내고, E는 간선 집합을 나타낸다. 일반적인 확장은 간선이 두 개 이상의 정점을 연결할 수 있는 하이퍼그래프로의 확장이다. 하이퍼에지는 모든 정점이 하나의 분할에 있는 경우 잘리지 않으며, 그렇지 않으면 각 측면에 있는 정점 수에 관계없이 정확히 한 번 잘린다. 이러한 사용법은 전자 설계 자동화에서 흔히 볼 수 있다.

4. 그래프 분할 방법

그래프 분할은 어려운 문제이므로, 실용적인 해결책은 휴리스틱에 기반한다. 그래프 분할 방법에는 크게 지역적 방법과 전역적 방법이 있다. 지역적 방법으로는 케르니건-린 알고리즘과 피두시아-매테이세스 알고리즘이 잘 알려져 있다. 전역적 방법의 대표적인 예로는 스펙트럼 분할이 있으며, 이는 스펙트럼 클러스터링을 활용한다.

4.1. 지역적 방법

그래프 분할은 어려운 문제이므로, 실용적인 해결책은 휴리스틱에 기반한다. 그래프 분할 방법에는 지역적 방법과 전역적 방법의 두 가지 광범위한 범주가 있다. 잘 알려진 지역적 방법으로는 케르니건-린 알고리즘과 피두시아-매테이세스 알고리즘이 있으며, 이들은 지역 탐색 전략을 통해 처음으로 효과적인 2-way 컷을 수행했다. 이러한 방법의 주요 단점은 정점 집합의 임의적인 초기 분할인데, 이는 최종 솔루션의 품질에 영향을 미칠 수 있다.

4.2. 전역적 방법

그래프 분할은 어려운 문제이므로, 실용적인 해결책은 휴리스틱에 기반한다. 그래프 분할 방법에는 지역적 방법과 전역적 방법의 두 가지 범주가 있다. 전역적 접근 방식은 전체 그래프의 속성에 의존하며 임의적인 초기 분할에 의존하지 않는다. 가장 일반적인 예는 스펙트럼 분할인데, 스펙트럼 분할은 인접 행렬의 근사 고유 벡터 또는 스펙트럼 클러스터링을 사용하여 분할을 얻는다. 스펙트럼 클러스터링은 그래프 라플라시안 행렬의 고유값 분해를 사용하여 그래프 정점을 그룹화한다.

5. 다단계 방법

다단계 그래프 분할 알고리즘은 하나 이상의 단계를 적용하여 작동한다. 각 단계는 정점과 변을 축소하여 그래프의 크기를 줄이고, 더 작은 그래프를 분할한 다음, 원래 그래프의 이 분할을 다시 매핑하고 개선한다. 전반적인 다단계 방식 내에서 다양한 분할 및 개선 방법을 적용할 수 있다. 많은 경우 이 접근 방식은 빠른 실행 시간과 매우 높은 품질의 결과를 제공할 수 있다.

이러한 접근 방식의 널리 사용되는 예는 그래프 분할기인 METIS와 이에 상응하는 하이퍼그래프 분할기인 hMETIS이다.

또 다른 접근 방식은 에서 시작되었으며, 예를 들어 scikit-learn에서 구현되었으며, 그래프 라플라시안 행렬의 고유벡터에서 결정된 분할을 사용하는 스펙트럼 군집화이다. 이 행렬은 멀티 그리드 전처리를 사용하여 LOBPCG 솔버로 계산된다.

6. 스펙트럼 분할 및 스펙트럼 이분

그래프 분할 방법 중 하나인 스펙트럼 분할은 그래프의 라플라시안 행렬을 이용한다. 그래프 $G=(V,E)$ 에서 $A$ 는 인접 행렬이고, $D$ 는 각 노드의 차수를 대각선 요소로 갖는 차수 행렬일 때, 라플라시안 행렬 $L$ 은 $L = D - A$ 로 정의된다.

그래프 $G = (V, E)$ 에 대한 비율-컷(ratio-cut) 분할은 $V$ 를 서로소(공통 원소가 없는) 집합 $U$ 와 $W$ 로 분할하여 다음 비율을 최소화하는 것이다.
: $\frac$

👆

좌우로 밀어서 보기

👆

좌우로 밀어서 보기

이는 컷을 가로지르는 에지의 수와 가능한 정점 쌍의 수의 비율을 나타낸다.

스펙트럼 그래프 분할은 진동하는 현이나 질량-스프링 시스템의 분할과 유사하게 동기를 부여받을 수 있으며, 그래프의 음수 가중치 경우로 확장될 수 있다.

6.1. 피들러 고유값 및 고유벡터

$L$ 의 두 번째로 작은 고유값( $\lambda_2$ )은 $c\geq \frac{\lambda_2}{n}$ 인 비율 컷 분할의 최적 비용( $c$ )에 대한 하한을 제공한다. $\lambda_2$ 에 해당하는 고유 벡터( $V_2$ )는 피들러 벡터라고 불리며, 해당 벡터 항목의 부호에 따라 그래프를 두 개의 커뮤니티로 분할한다. 더 많은 수의 커뮤니티로 분할하는 것은 반복적인 이분법 또는 가장 작은 고유값에 해당하는 여러 고유 벡터를 사용하여 달성할 수 있다.

6.2. 모듈성 및 비율-컷

최소 컷 분할은 분할할 커뮤니티의 수나 분할 크기를 알 수 없는 경우 실패한다. 예를 들어, 자유로운 그룹 크기에 대해 컷 크기를 최적화하면 모든 정점이 동일한 커뮤니티에 속하게 된다. 또한, 컷 크기는 최소화해야 할 대상이 아닐 수 있다. 왜냐하면 좋은 분할은 커뮤니티 간의 적은 수의 에지만을 갖는 것이 아니기 때문이다. 이는 균형 잡힌 그래프 분할을 최적화하기 위한 지표로 모듈성(Q)의 사용을 유도했다.

그림 3: 가중치 그래프 G는 (a)에서 Q를 최대화하거나 (b)에서 비율 컷을 최소화하도록 분할될 수 있다. (a)가 더 균형 잡힌 분할임을 알 수 있으며, 이는 그래프 분할 문제에서 모듈성의 중요성을 강조한다.

그림 3의 예는 동일한 그래프의 두 가지 예를 보여준다. 여기서 (a)는 모듈성(Q)이 분할 지표이고, (b)는 비율 컷이 분할 지표이다.

7. 응용 분야

그래프 분할은 유행병 확산을 막기 위해 면역해야 하는 노드나 링크의 최소 집합을 식별하는 데 활용될 수 있다.

7.1. 컨덕턴스

그래프 분할에 사용되는 또 다른 목적 함수는 잘린 엣지 수와 가장 작은 부분의 볼륨 간의 비율인 컨덕턴스이다. 컨덕턴스는 전기 흐름과 임의 보행과 관련이 있다. 치거 경계는 스펙트럼 이분법이 거의 최적의 컨덕턴스를 가진 파티션을 제공함을 보장한다. 이 근사의 품질은 라플라시안의 두 번째로 작은 고유값 λ₂에 따라 달라진다.

7.2. 면역

그래프 분할은 유행병을 막기 위해 면역해야 하는 노드나 링크의 최소 집합을 식별하는 데 유용할 수 있다.

7.3. 기타 응용 분야

스핀 모델은 유사성이 결합 강도로 변환되는 다변량 데이터의 클러스터링에 사용되어 왔다. 바닥 상태 스핀 구성의 속성은 커뮤니티로 직접 해석될 수 있다. 따라서 그래프는 분할된 그래프의 해밀토니안을 최소화하도록 분할된다.

커널 PCA 기반 스펙트럼 클러스터링은 최소 제곱 서포트 벡터 머신 프레임워크 형태를 취하므로, 데이터 항목을 최대 분산을 갖는 커널 유도 특징 공간에 투영하여 투영된 커뮤니티 간의 높은 분리를 의미하게 된다.

일부 방법은 그래프 분할을 각 노드가 선택한 분할에 대한 결정을 내리는 게임 이론적 프레임워크로 표현된 국소적 방법을 사용하여 해결할 수 있는 다중 기준 최적화 문제로 표현한다.

매우 대규모 분산 그래프의 경우, 스펙트럼 분할, Metis 같은 고전적 분할 방법은 전역 작업을 수행하기 위해 그래프 데이터에 대한 전체 액세스가 필요하므로 적용되지 않을 수 있다. 이러한 대규모 시나리오의 경우 분산 그래프 분할을 사용하여 비동기식 국소 작업만을 통해 분할을 수행한다.

8. 소프트웨어 도구

scikit-learn은 고유 벡터로 결정된 분할을 사용하여 스펙트럼 클러스터링을 구현하며, 원본 그래프의 그래프 라플라시안 행렬은 ARPACK 또는 멀티 그리드 전처리가 적용된 LOBPCG 솔버로 계산된다.

METIS는 Karypis와 Kumar가 개발한 그래프 분할 제품군이다. 이 제품군 중 kMetis는 더 빠른 분할 속도를 목표로 하며, hMetis는 하이퍼그래프에 적용되어 분할 품질을 목표로 하고, ParMetis는 Metis 그래프 분할 알고리즘의 병렬 구현이다.

KaHyPar는 직접적인 k-way 및 재귀적인 이분할 기반 분할 알고리즘을 제공하는 다단계 하이퍼그래프 분할 프레임워크이다. 이 프레임워크는 계층의 각 레벨에서 단일 정점만 제거하는 가장 극단적인 버전으로 다단계 접근 방식을 인스턴스화한다. 이 매우 세분화된 n-레벨 접근 방식과 강력한 지역 검색 휴리스틱을 결합하여 매우 높은 품질의 솔루션을 계산한다.

Scotch는 Pellegrini가 개발한 그래프 분할 프레임워크이다. 이 프레임워크는 재귀적인 다단계 이분할을 사용하며 순차적 및 병렬 분할 기술을 포함한다.

Jostle은 Chris Walshaw가 개발한 순차적 및 병렬 그래프 분할 솔버이다. 이 분할기의 상용 버전은 NetWorks로 알려져 있다.

Party는 Bubble/shape-optimized 프레임워크와 Helpful Sets 알고리즘을 구현한다.

Meyerhenke의 소프트웨어 패키지 DibaP와 MPI 병렬 변형 PDibaP는 확산을 사용하여 Bubble 프레임워크를 구현한다. DibaP는 또한 확산 접근 방식에서 발생하는 선형 시스템의 조대화 및 해결을 위해 AMG 기반 기술을 사용한다.

Sanders와 Schulz는 예를 들어 흐름 기반 방법, 보다 지역화된 지역 검색 및 여러 병렬 및 순차적 메타 휴리스틱을 구현하는 그래프 분할 패키지 KaHIP(Karlsruhe High Quality Partitioning)를 출시했다.

Trifunovic과 Knottenbelt의 도구 Parkway와 Devine 등이 개발한 Zoltan은 하이퍼그래프 분할에 중점을 둔다.

정의	그래프의 정점들을 서로소 집합들로 분할하는 것
목표	분할된 집합들 간의 연결을 최소화하고 각 집합의 크기를 균등하게 유지하는 것

종류

정점 분할	정점들을 분할
에지 분할	에지들을 분할

응용 분야

병렬 컴퓨팅	계산 작업을 여러 프로세서에 분산
데이터 마이닝	데이터 클러스터링 및 패턴 인식
이미지 분할	이미지 내 객체 분리
소셜 네트워크 분석	커뮤니티 구조 발견

알고리즘

Kernighan-Lin 알고리즘	국소 탐색 기반의 휴리스틱 알고리즘
Fiduccia-Mattheyses 알고리즘	Kernighan-Lin 알고리즘의 개선 버전
멀티레벨 분할	그래프를 축소하고 분할한 후 다시 확장하는 방식
스펙트럴 분할	그래프의 라플라시안 행렬의 고유 벡터를 이용하는 방식
균형 컷	그래프를 두 부분으로 나누어 각 부분의 크기를 균형있게 유지
최소 컷	그래프를 두 부분으로 나누어 두 부분 사이의 에지 수를 최소화

평가 기준

컷 크기	분할된 집합들 간의 에지 수
균형도	각 집합의 크기가 얼마나 균등한지
실행 시간	알고리즘의 실행 시간