그래프 파티션

수학에서 그래프 분할은 노드 집합을 서로 배타적인 그룹으로 분할함으로써 그래프를 더 작은 그래프로 줄이는 것입니다.그룹 간에 교차하는 원래 그래프의 가장자리는 분할된 그래프에 가장자리를 생성합니다.원래 그래프에 비해 결과 모서리의 수가 작을 경우 분할된 그래프가 원래 그래프보다 분석 및 문제 해결에 더 적합할 수 있습니다.그래프 분석을 단순화하는 파티션을 찾는 것은 어려운 문제이지만,^[1] 특히 멀티프로세서 컴퓨터에서 과학 컴퓨팅, VLSI 회로 설계, 작업 스케줄링 등에 응용할 수 있습니다.최근 그래프 분할 문제는 사회, 병리, 생물 네트워크에서의 집단화 및 검출을 위한 응용으로 인해 중요해지고 있다.계산 방법 및 응용 분야의 최근 동향에 대한 조사는 Buluc 등(2013)[2]을 참조한다.그래프 분할의 두 가지 일반적인 예로는 최소 절단 문제와 최대 절단 문제가 있습니다.

문제의 복잡성

일반적으로 그래프 분할 문제는 NP-하드 문제의 범주에 속합니다.이러한 문제에 대한 해결책은 일반적으로 휴리스틱스와 근사 ^[3]알고리즘을 사용하여 도출됩니다.그러나 균일한 그래프 분할 또는 균형 그래프 분할 문제는 NP-완전한 것으로 나타나 유한 요인 ^[1]내에서 근사할 수 있습니다.나무 및 그리드와 같은 특수 그래프 클래스의 경우에도 P=NP가 아닌 한 합리적인 근사 알고리즘은 ^[4]존재하지 않는다. 그리드는 유한 요소 모델(FEM) 시뮬레이션에서 생성된 그래프를 모델링하기 때문에 특히 흥미로운 경우이다.성분들 사이의 가장자리 수뿐만 아니라 성분들의 크기까지 대략적으로 계산하면,^[4] 이러한 그래프에 합리적인 완전 다항식 알고리즘이 존재하지 않는다는 것을 알 수 있다.

문제

그래프 G = (V, E)를 고려합니다. 여기서 V는 n개의 꼭지점 집합을 나타내고 E는 모서리 집합을 나타냅니다.(k,v)균형 파티션 문제의 목적은 G를 최대 크기 v · (n/k)의 k개의 컴포넌트로 분할하는 동시에 개별 ^[1]컴포넌트 간의 가장자리 용량을 최소화하는 것입니다.또, G와 정수 k>1이 주어졌을 때, V를 k개의 부분(부분 집합₁) V₂, V, …, V로_k 분할해, 각 부분이 서로 다른 부분에서의 끝점과의 엣지수를 최소한으로 한다.그러한 분할 문제는 바이리테리어의 근사 또는 자원 증강 접근법과 같은 문헌에서 논의되었다.일반적인 확장 기능은 하이퍼그래프이며, 여기서 가장자리는 두 개 이상의 정점을 연결할 수 있습니다.모든 정점이 1개의 파티션에 있는 경우에는 하이퍼지(hyperedge)가 절단되지 않고, 그렇지 않은 경우에는 각 측면에 몇 개의 정점이 있는지에 관계없이 정확히 한 번 절단됩니다.이 사용법은 전자 설계 자동화에서 흔히 볼 수 있습니다.

분석.

특정 (k, 1 + ))균형 파티션 문제에 대해서는 각 컴포넌트가 최대 (1 + ))·(n/k) 노드를 포함하는 k개의 컴포넌트로 G의 최소 비용 파티션을 찾습니다.우리는 이 근사 알고리즘의 비용을 (k,1) 삭감 비용과 비교한다.여기서 k개의 구성요소는 각각 (n/k) 노드의 크기가 같아야 하므로 더 제한적인 문제가 된다.따라서,

\displaystyle \max _{i} V_leq (1+\varepsilon)\left\lceil {\frac { V }{k}\right\rceil .}

우리는 (2,1) 절단이 최소 이등분 문제이며 NP-완전이라는 것을 ^[5]이미 알고 있다.다음으로, n = 3k인 3차원 문제를 평가하며, 이 문제도 다항 시간으로 ^[1]제한된다.(k, 1)균형 분할에 대한 유한한 근사 알고리즘을 가지고 있다고 가정하면, 3분할 인스턴스는 G의 균형 분할(k, 1)을 사용하여 해결하거나 해결할 수 없습니다.3분할 인스턴스를 해결할 수 있으면 G의 (k, 1)균형 분할 문제를 엣지 없이 해결할 수 있다.그렇지 않으면 3-파티션 인스턴스를 해결할 수 없는 경우 G에서 최적의 (k, 1)-균형 분할로 인해 적어도1개의 에지가 절단됩니다.유한한 근사 계수를 가진 근사 알고리즘은 이 두 경우를 구별해야 한다.따라서, P = NP라는 가정 하에 모순인 3차원 문제를 해결할 수 있다.따라서, (k,1) 균형 분할 문제는 P = ^[1]NP가 아닌 한 유한 근사 계수를 갖는 다항 시간 근사 알고리즘이 없다는 것이 명백하다.

평면 분리기 정리는 어떤 n-vertex 평면 그래프도 O(nn) 정점의 제거에 의해 거의 동일한 부분으로 분할될 수 있음을 나타냅니다.파티션 세트는 가장자리가 아닌 정점으로 구성되므로 위에서 설명한 의미의 파티션이 아닙니다.그러나, 같은 결과는 또한 유계도의 모든 평면 그래프가 O(µn) 모서리와 균형 잡힌 절단을 가지고 있다는 것을 암시합니다.

그래프 분할 방식

그래프 분할은 어려운 문제이기 때문에 실용적인 해결책은 휴리스틱스를 기반으로 합니다.방법에는 로컬과 글로벌의 두 가지 범주가 있습니다.잘 알려진 로컬 방법은 Kernighan-Lin 알고리즘과 Fiduccia-Mattheyses 알고리즘으로 로컬 검색 전략에 의한 최초의 효과적인 양방향 컷이다.이들의 주요 단점은 정점 집합의 임의의 초기 분할이며, 이는 최종 솔루션 품질에 영향을 미칠 수 있습니다.글로벌 접근 방식은 전체 그래프의 속성에 의존하며 임의의 초기 파티션에 의존하지 않습니다.가장 일반적인 예는 스펙트럼 분할이며, 여기서 파티션은 인접 행렬의 대략적인 고유 벡터에서 파생되거나 그래프 라플라시안 행렬의 에이젠데콤포지션을 사용하여 그래프 정점을 그룹화하는 스펙트럼 클러스터링이다.

다단계 방식

다단계 그래프 분할 알고리즘은 하나 이상의 단계를 적용하여 작동합니다.각 스테이지에서는 정점과 모서리를 접고 작은 그래프를 분할한 ^[6]다음 원래 그래프의 이 분할을 다시 매핑하고 조정합니다.전체 다단계 체계 내에서 다양한 분할 및 세분화 방법을 적용할 수 있습니다.대부분의 경우, 이 접근방식을 통해 실행 시간이 단축되고 매우 높은 품질의 결과를 얻을 수 있습니다.이러한 접근법의 한 가지 널리 사용되는 예는 그래프 분할기인 METIS와 ^[7]하이퍼그래프에 ^[8]대응하는 분할기인 hMETIS입니다.예를 들어 skit-learn에서 유래하고 구현되는 대체 접근법은 다중 그리드 사전 조건을 가진 LOBPCG 솔버에 의해 계산된 원래 그래프 라플라시안 행렬의 고유 벡터로부터 결정되는 분할을 사용한 스펙트럼 클러스터링이다.

스펙트럼 분할 및 스펙트럼 이등분

$그래프$ $G=(V,E)$ $G=(V,E)$ ( $G=(V,E)$ , $G=(V,E)$ ) \ $displaystyle$ G = ( $G=(V,E)$ $V$ , $E$ ) \ displaystyle $A$ \ $style$ A _ $A_{ij}$ { $A_{ij}$ $A$ $a$ $A_{ij}$ a $A_{ij}$ i given i、A \ $displaystyle$ A _ { $i$ j $i$ $A_{ij}$ $j$ $matrix$ matrix matrix matrix matrix matrix matrix d d 、 $대각선행렬$ D \ $displaystyle$ D $、$ l 행 $(displaystyle$ i $i$ $($ $displaystyle$ $d_{ii$ 의 엔트리는 노드 i $(node$ i $i$ 의 노드 수준을 나타냅니다. $라플라시안$ 행렬 L $({displaystyle$ L})은 $L$ L $G=(V,E)$ $L=D-A$ - $({displaystyle$ L $=$ $D-A$ 로 정의됩니다. 이제 $G=(V,E)$ G $G=(V,E)$ E $)$ 의 비율 컷 파티션은 V $({$ $displaystyle$ V $,$ $E)$ 의 $G=(V,E)$ $V$ $U$ 로 정의됩니다 $.$

{\frac { E(G)\cap (U\times W)}{ U \cdot W }

이러한 모서리를 지원할 수 있는 꼭지점 쌍 수에 대해 이 절단 부분을 실제로 교차하는 모서리 수를 지정합니다.스펙트럼 그래프 분할은 진동 스트링 또는 매스 스프링 시스템의 분할과 유사하게 동기 부여될^[10] 수 있으며 그래프의 ^[11]음의 가중치인 경우에도 마찬가지로 확장된다.

피들러 고유값 및 고유 벡터

이러한 시나리오에서는 $L의$ 번째 최소 고유값(< $displaystyle$ $\$ $lambda$ $_$ { $c\geq {\frac {\lambda _{2}}{n}}$ $\lambda _{2}$ $L$ )은 c $c\geq {\frac {\lambda _{2}}{n}}$ n의 $c\geq {\frac {\lambda _{2}}{n}}$ 컷 파티션의 최적 $(<$ $displaystyle$ c $c$ })의 하한(< $displaystyle c$ 을 산출합니다.피들러 벡터라고 불리는 § $({$ displaystyle $\lambda$ _ ${2$ 에 대응하는 고유 벡터( $V_{2}$ 2 { $style$ V_ ${2$ 는 대응하는 벡터 엔트리의 부호에 근거해 그래프를 2개의 커뮤니티만으로 나눕니다.더 많은 수의 커뮤니티로 분할하는 것은 반복적인 이등분 또는 최소 ^[12]고유값에 대응하는 복수의 고유 벡터를 사용함으로써 달성할 수 있다.그림 1.2의 예는 스펙트럼 이등분 접근방식을 보여준다.

그림 1: 스펙트럼 이등분 시 그래프 G = (5,4)를 분석하였다.가장 작은 두 고유 벡터의 선형 조합은 고유값 = 0인 [1 1 1 1 1]'로 이어집니다.

그림 2: 그래프 G = (5,5)는 빨간색의 피들러 벡터가 그래프를 두 개의 커뮤니티로 나눕니다. 하나는 벡터 공간에 양의 엔트리가 있는 정점 {1,2,3}이 있고 다른 하나는 음의 벡터 공간 엔트리가 있는 정점 {4,5}이 있습니다.

모듈러형 및 비율 삭감

그러나 분할할 커뮤니티의 수 또는 파티션 크기를 알 수 없는 경우에는 최소 컷 파티셔닝이 실패합니다.예를 들어, 자유 그룹 크기에 맞게 절단 크기를 최적화하면 모든 정점이 동일한 커뮤니티에 배치됩니다.또, 적절한 분할은 커뮤니티간의 엣지수가 적은 것만이 아니기 때문에, 컷 사이즈는 최소한으로 억제하는 것이 잘못된 것일 수 있습니다.이를 통해 균형 잡힌 그래프 파티션을 최적화하기 위한 메트릭으로 모듈성(^[13]Q)을 사용할 수 있게 되었습니다.그림 3의 예는 (a) 모듈러성(Q)이 분할 메트릭이고 (b)에서 비율 컷이 분할 메트릭인 동일한 그래프의 두 인스턴스를 보여준다.

그림 3: 가중 그래프 G는 (a)의 Q를 최대화하거나 (b)의 비율 절단을 최소화하기 위해 분할할 수 있다.우리는 (a)가 더 나은 균형 분할이며, 따라서 그래프 분할 문제에서 모듈화의 중요성에 동기를 부여한다는 것을 안다.

적용들

컨덕턴스

그래프 분할에 사용되는 또 다른 목적 함수는 커팅 에지 수와 최소 부품의 볼륨 사이의 비율인 컨덕턴스입니다.컨덕턴스는 전기적 흐름과 랜덤 워크와 관련이 있습니다.Cheeger bound는 스펙트럼 이등분할이 거의 최적의 컨덕턴스로 파티션을 제공하는 것을 보증한다.이 근사치의 품질은 Laplacian θ의₂ 두 번째로 작은 고유값에 따라 달라집니다.

예방접종

그래프 파티션은 ^[14]전염병을 막기 위해 면역해야 하는 최소 노드 또는 링크 세트를 식별하는 데 유용합니다.

기타 그래프 분할 방법

스핀 모델은 유사성이 결합 ^[15]강도로 변환되는 다변량 데이터의 클러스터링에 사용되어 왔다.접지 상태 스핀 구성의 속성은 커뮤니티로 직접 해석할 수 있습니다.따라서 그래프는 분할된 그래프의 해밀턴을 최소화하기 위해 분할됩니다.Hamiltonian(H)은 다음과 같은 파티션 보상 및 패널티를 할당하여 도출됩니다.

동일한 그룹의 노드 간 내부 에지 보상(동일한 스핀)
같은 그룹의 결측 모서리 패널티
서로 다른 그룹 간에 기존 모서리 패널티 적용
다른 그룹 간의 비연계에 대한 보상을 제공합니다.

또한 커널-PCA 기반 스펙트럼 클러스터링은 최소 제곱 지원 벡터 머신 프레임워크의 형태를 취하므로 데이터 엔트리를 최대 분산을 갖는 커널 유도 피쳐 공간에 투영할 수 있게 되어 투영된 커뮤니티 ^[16]간의 높은 분리를 의미한다.

어떤 방법들은 그래프 분할을 다중 기준 최적화 문제로 표현하며, 이는 각 노드가 ^[17]선택한 분할에 대해 결정을 내리는 게임 이론 프레임워크에서 표현되는 로컬 방법을 사용하여 해결할 수 있다.

매우 대규모 분산 그래프의 경우 전역 연산을 수행하기 위해 그래프 데이터에 대한 전체 액세스가 필요하기 때문에 고전 분할 방법(예: 스펙트럼 분할, Metis^[7])이 적용되지 않을 수 있다.이러한 대규모 시나리오에서는 분산 그래프 파티셔닝을 사용하여 비동기 로컬 작업을 통해서만 파티셔닝을 수행합니다.

소프트웨어 도구

Scikit-learn은 ARPACK에 의해 계산된 원래 그래프에 대한 그래프 ^[9]라플라시안 행렬의 고유 벡터 또는 다중 그리드 사전 조건이 있는 LOBPCG 솔버에서 결정된 분할로 스펙트럼 클러스터링을 구현한다.

Chaco는 ^[18]Hendrickson과 Leland에 의해 위에서 설명한 다단계 접근법과 기본적인 로컬 검색 알고리즘을 구현합니다.또한 스펙트럼 분할 기법을 구현한다.

METIS는^[7] Karypis와 Kumar에 의한 그래프 분할 패밀리입니다.이 제품군 중 kMetis는 ^[8]보다 빠른 분할 속도를 목표로 하며, hMetis는 하이퍼그래프에 적용되어 파티션 품질을 목표로 하며, ParMetis는^[7] Metis 그래프 분할 알고리즘의 병렬 구현입니다.

PaToH는^[19] 또 다른 하이퍼그래프 파티션입니다.

KaHyPar는^[20]^[21]^[22] 직접 k-way 및 재귀적 분할 기반의 분할 알고리즘을 제공하는 다단계 하이퍼그래프 분할 프레임워크입니다.이는 계층의 모든 레벨에서 하나의 정점만 제거하여 가장 극단적인 버전에서 다단계 접근 방식을 인스턴스화합니다.이 매우 미세한 n-level 접근법을 강력한 로컬 검색 휴리스틱과 결합하여 매우 고품질의 솔루션을 계산합니다.

스카치는^[23] Pellegrini의 그래프 분할 프레임워크입니다.이것은 재귀적 다단계 이등분할을 사용하며 순차적 분할 기술 및 병렬 분할 기술을 포함합니다.

Jostle은^[24] Chris Walshaw가 개발한 순차 및 병렬 그래프 분할 솔버입니다.이 파티션의 상용화된 버전은 NetWorks로 알려져 있습니다.

파티는^[25] 버블/쉐이핑 최적화 프레임워크와 도움말 세트 알고리즘을 구현합니다.

소프트웨어 패키지^[26] DibaP와 MPI-parallel variant^[27] PDibaP by Meyerenke는 확산을 사용하여 버블 프레임워크를 구현합니다. DibaP는 또한 확산 접근에서 발생하는 선형 시스템을 조밀하게 만들고 해결하기 위해 AMG 기반 기술을 사용합니다.

Sanders와 Schulz는 흐름 기반의 메서드, 보다 로컬화된 로컬 검색 및 여러 병렬 및 순차적 메타 휴리스틱스를 구현하는 그래프 분할 패키지^[28] KaHIP(Karlsruhe High Quality Partitioning)를 출시했습니다.

Tripunovic과 Nottenbelt의 Parkway와^[29] Devine 등의 Zoltan^[30] 툴은 하이퍼그래프 분할에 초점을 맞추고 있습니다.

무료 오픈 소스 프레임워크 목록:

이름.	면허증.	간단한 정보
차코	GPL	스펙트럼 기술과 다단계 접근법을 구현하는 소프트웨어 패키지
DiBaP	*	다단계 기술, 대수적 다지표 및 그래프 기반 확산에 기초한 그래프 분할
밀다	*	멀티레벨 파티셔닝 기술 및 분산 로드 밸런싱, 순차 및 병렬
KaHIP	MIT	여러 병렬 및 순차 메타 휴리스틱을 통해 균형 제약, Python 지원 보장
KaHyPar	GPL	직접 k방향 및 재귀적 이등분 기반 다단계 하이퍼그래프 분할 프레임워크
kMetis	아파치 2.0	다단계 기술 및 k-way 로컬 검색을 기반으로 한 그래프 분할 패키지
몬드리안	LGPL	직사각형 스파스 행렬을 분할하는 행렬 분할기
PaToH	BSD	다단계 하이퍼그래프 분할
파크웨이	*	병렬 다단계 하이퍼그래프 분할
Scikit-learn	BSD	대수적 멀티그리드 전제조건에 의한 스펙트럼 분할
스카치	CeCIL-C	확산 기법, 순차적 및 병렬뿐만 아니라 다단계 재귀적 이등분 구현
졸탄	BSD	하이퍼그래프 분할

레퍼런스

^ ^a ^b ^c ^d ^e Andreev, Konstantin; Räcke, Harald (2004). Balanced Graph Partitioning. Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.
^ Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter; Schulz, Christian (2013). "Recent Advances in Graph Partitioning". arXiv:1311.3144 [cs.DS].
^ Feldmann, Andreas Emil; Foschini, Luca (2012). "Balanced Partitions of Trees and Applications". Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science: 100–111.
^ ^a ^b Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F.
^ Garey, Michael R.; Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 978-0-7167-1044-8.
^ Hendrickson, B.; Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. p. 28.
^ ^a ^b ^c ^d Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997.
^ ^a ^b Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. pp. 526–529.
^ ^a ^b Knyazev, Andrew V. (2006). Multiscale Spectral Graph Partitioning and Image Segmentation. Workshop on Algorithms for Modern Massive Data Sets Stanford University and Yahoo! Research.
^ J. Demmel, [1], CS267: 강의 23, 1999년 4월 9일 그래프 분할, 파트 2
^ Knyazev, Andrew (2018). On spectral partitioning of signed graphs. Eighth SIAM Workshop on Combinatorial Scientific Computing, CSC 2018, Bergen, Norway, June 6-8. doi:10.1137/1.9781611975215.2.
^ Naumov, M.; Moon, T. (2016). "Parallel Spectral Graph Partitioning". NVIDIA Technical Report. nvr-2016-001.
^ Newman, M. E. J. (2006). "Modularity and community structure in networks". PNAS. 103 (23): 8577–8696. arXiv:physics/0602124. Bibcode:2006PNAS..103.8577N. doi:10.1073/pnas.0601602103. PMC 1482622. PMID 16723398.
^ Y. Chen, G. Paul, S. Havlin, F. Liljeros, H.E. Stanley (2009). "Finding a Better Immunization Strategy". Phys. Rev. Lett. 101 (5): 058701. doi:10.1103/PhysRevLett.101.058701. PMID 18764435.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
^ Reichardt, Jörg; Bornholdt, Stefan (July 2006). "Statistical mechanics of community detection". Phys. Rev. E. 74 (1): 016110. arXiv:cond-mat/0603718. Bibcode:2006PhRvE..74a6110R. doi:10.1103/PhysRevE.74.016110. PMID 16907154. S2CID 792965.
^ Alzate, Carlos; Suykens, Johan A. K. (2010). "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 335–347. doi:10.1109/TPAMI.2008.292. ISSN 0162-8828. PMID 20075462. S2CID 200488.
^ Kurve, C.; Griffin, C.; Kesidis G. (2011) "네트워크 분산 시뮬레이션을 위한 그래프 분할 게임", 2011년 복합 네트워크 모델링, 분석 및 제어에 관한 국제 워크숍 진행: 9~16
^ Hendrickson, Bruce. "Chaco: Software for Partitioning Graphs". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Catalyürek, Ü.; Aykanat, C. (2011). PaToH: Partitioning Tool for Hypergraphs.
^ Schlag, S.; Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). "K-way Hypergraph Partitioning via n-Level Recursive Bisection". 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Proceedings. Society for Industrial and Applied Mathematics. pp. 53–67. doi:10.1137/1.9781611974317.5. ISBN 978-1-61197-431-7. S2CID 1674598.
^ Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). "Engineering a direct k-way Hypergraph Partitioning Algorithm". 2017 Proceedings of the Nineteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Proceedings. Society for Industrial and Applied Mathematics. pp. 28–42. doi:10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.
^ Heuer, Tobias; Schlag, Sebastian (2017). Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (eds.). Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 75. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 21:1–21:19. doi:10.4230/LIPIcs.SEA.2017.21. ISBN 9783959770361.
^ Chevalier, C.; Pellegrini, F. (2008). "PT-Scotch: A Tool for Efficient Parallel Graph Ordering". Parallel Computing. 34 (6): 318–331. arXiv:0907.1375. doi:10.1016/j.parco.2007.12.001. S2CID 10433524.
^ Walshaw, C.; Cross, M. (2000). "Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm". Journal on Scientific Computing. 22 (1): 63–80. CiteSeerX 10.1.1.19.1836. doi:10.1137/s1064827598337373.
^ Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM". Parallel Computing. 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687. doi:10.1016/s0167-8191(00)00043-0.
^ Meyerhenke, H.; Monien, B.; Sauerwald, T. (2008). "A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions". Journal of Parallel Computing and Distributed Computing. 69 (9): 750–761. doi:10.1016/j.jpdc.2009.04.005. S2CID 9755877.
^ Meyerhenke, H. (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67–82.
^ Sanders, P.; Schulz, C. (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceedings of the 19th European Symposium on Algorithms (ESA). Vol. 6942. pp. 469–480.
^ Trifunovic, A.; Knottenbelt, W. J. (2008). "Parallel Multilevel Algorithms for Hypergraph Partitioning". Journal of Parallel and Distributed Computing. 68 (5): 563–581. CiteSeerX 10.1.1.641.7796. doi:10.1016/j.jpdc.2007.11.002.
^ Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Parallel Hypergraph Partitioning for Scientific Computing. Proceedings of the 20th International Conference on Parallel and Distributed Processing. p. 124.

외부 링크

체임벌린, 브래드포드 L.(1998)."병렬 ^[permanent dead link]연산 워크로드를 분산하기 위한 그래프 분할 알고리즘"

참고 문헌

Bichot, Charles-Edmond; Siarry, Patrick (2011). Graph Partitioning: Optimisation and Applications. ISTE – Wiley. p. 384. ISBN 978-1848212336.
Feldmann, Andreas Emil (2012). Balanced Partitioning of Grids and Related Graphs: A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations. Goettingen, Germany: Cuvillier Verlag. p. 218. ISBN 978-3954041251. 이론적인 관점에서 문제의 철저한 분석.
Kernighan, B. W.; Lin, S. (1970). "An Efficient Heuristic Procedure for Partitioning Graphs" (PDF). Bell System Technical Journal. 49 (2): 291–307. doi:10.1002/j.1538-7305.1970.tb01770.x. 이 분야의 초기 기본 작업 중 하나입니다.그러나 성능은 O(n²)이므로 더 이상 일반적으로 사용되지 않습니다.
Fiduccia, C. M.; Mattheyses, R. M. (1982). A Linear-Time Heuristic for Improving Network Partitions. Design Automation Conference. doi:10.1109/DAC.1982.1585498. 그 자체와 다단계 파티션의 일부로 자주 사용되는 선형 시간 이후의 변형은 다음을 참조하십시오.
Karypis, G.; Kumar, V. (1999). "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs". SIAM Journal on Scientific Computing. 멀티 레벨 파티셔닝은 최신 기술입니다.이 문서에는 다른 많은 방법에 대한 좋은 설명과 다양한 문제에 대한 다양한 방법의 비교도 포함되어 있습니다.
Karypis, G;Aggarwal, R.;쿠마르는 V;Shekhar, S(1999년 3월)."다단계 하이퍼 그래프 분할:VLSI도메인에 응용".초대형 규모 통합(VLSI)시스템에 IEEETransactions이. 7(1):69–79.CiteSeerX 10.1.1.553.2367. doi:10.1109/92.748202.그래프 분할(그리고 특히, 분할hypergraph)IC설계에 많은 적용시킬 수 있습니다.
Kirkpatrick, S.; Gelatt, C. D., Jr.; Vecchi, M. P. (13 May 1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. Bibcode:1983Sci...220..671K. CiteSeerX 10.1.1.123.7607. doi:10.1126/science.220.4598.671. PMID 17813860. S2CID 205939. 모의 어닐링도 사용할 수 있습니다.
헤이건, L.;Kahng, 기능주의(9월 1992년)."비율에 대해 새로운 파장 방법 인하 분할과 군집화".컴퓨터에 의한 설계 통합 Circuits의 장비 및 시스템에 IEEETransactions이. 11(9):1074–1085. doi:10.1109/43.159993..있습니다. 그것은 Laplacian 연결 장치를 그래프의 Eigenvectors을 사용하는 주파수 분할 방법을 전체 수업이 있습니다.Matlab을 사용하여 데모를 볼 수 있습니다.

[balgraph-1] Andreev, Konstantin; Räcke, Harald (2004). Balanced Graph Partitioning. Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. Barcelona, Spain. pp. 120–124. CiteSeerX 10.1.1.417.8592. doi:10.1145/1007912.1007931. ISBN 978-1-58113-840-5.

[recentadvances-2] Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter; Schulz, Christian (2013). "Recent Advances in Graph Partitioning". arXiv:1311.3144 [cs.DS].

[baltrees-3] Feldmann, Andreas Emil; Foschini, Luca (2012). "Balanced Partitions of Trees and Applications". Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science: 100–111.

[fastpartition-4] Feldmann, Andreas Emil (2012). "Fast Balanced Partitioning is Hard, Even on Grids and Trees". Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F.

[minbisect-5] Garey, Michael R.; Johnson, David S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co. ISBN 978-0-7167-1044-8.

[6] Hendrickson, B.; Leland, R. (1995). A multilevel algorithm for partitioning graphs. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM. p. 28.

[:0-7] Karypis, G.; Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997.

[hmetis-8] Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. pp. 526–529.

[spectralmultigrid2006-9] Knyazev, Andrew V. (2006). Multiscale Spectral Graph Partitioning and Image Segmentation. Workshop on Algorithms for Modern Massive Data Sets Stanford University and Yahoo! Research.

[10] J. Demmel, [1], CS267: 강의 23, 1999년 4월 9일 그래프 분할, 파트 2

[11] Knyazev, Andrew (2018). On spectral partitioning of signed graphs. Eighth SIAM Workshop on Combinatorial Scientific Computing, CSC 2018, Bergen, Norway, June 6-8. doi:10.1137/1.9781611975215.2.

[spectral_nvidia_tr-12] Naumov, M.; Moon, T. (2016). "Parallel Spectral Graph Partitioning". NVIDIA Technical Report. nvr-2016-001.

[npnas-13] Newman, M. E. J. (2006). "Modularity and community structure in networks". PNAS. 103 (23): 8577–8696. arXiv:physics/0602124. Bibcode:2006PNAS..103.8577N. doi:10.1073/pnas.0601602103. PMC 1482622. PMID 16723398.

[14] Y. Chen, G. Paul, S. Havlin, F. Liljeros, H.E. Stanley (2009). "Finding a Better Immunization Strategy". Phys. Rev. Lett. 101 (5): 058701. doi:10.1103/PhysRevLett.101.058701. PMID 18764435.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)

[potts-15] Reichardt, Jörg; Bornholdt, Stefan (July 2006). "Statistical mechanics of community detection". Phys. Rev. E. 74 (1): 016110. arXiv:cond-mat/0603718. Bibcode:2006PhRvE..74a6110R. doi:10.1103/PhysRevE.74.016110. PMID 16907154. S2CID 792965.

[pami-16] Alzate, Carlos; Suykens, Johan A. K. (2010). "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (2): 335–347. doi:10.1109/TPAMI.2008.292. ISSN 0162-8828. PMID 20075462. S2CID 200488.

[17] Kurve, C.; Griffin, C.; Kesidis G. (2011) "네트워크 분산 시뮬레이션을 위한 그래프 분할 게임", 2011년 복합 네트워크 모델링, 분석 및 제어에 관한 국제 워크숍 진행: 9~16

[chaco-18] Hendrickson, Bruce. "Chaco: Software for Partitioning Graphs". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[patoh-19] Catalyürek, Ü.; Aykanat, C. (2011). PaToH: Partitioning Tool for Hypergraphs.

[20] Schlag, S.; Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). "K-way Hypergraph Partitioning via n-Level Recursive Bisection". 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Proceedings. Society for Industrial and Applied Mathematics. pp. 53–67. doi:10.1137/1.9781611974317.5. ISBN 978-1-61197-431-7. S2CID 1674598.

[21] Akhremtsev, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). "Engineering a direct k-way Hypergraph Partitioning Algorithm". 2017 Proceedings of the Nineteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Proceedings. Society for Industrial and Applied Mathematics. pp. 28–42. doi:10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.

[22] Heuer, Tobias; Schlag, Sebastian (2017). Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (eds.). Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure. 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 75. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 21:1–21:19. doi:10.4230/LIPIcs.SEA.2017.21. ISBN 9783959770361.

[scotch-23] Chevalier, C.; Pellegrini, F. (2008). "PT-Scotch: A Tool for Efficient Parallel Graph Ordering". Parallel Computing. 34 (6): 318–331. arXiv:0907.1375. doi:10.1016/j.parco.2007.12.001. S2CID 10433524.

[jostle-24] Walshaw, C.; Cross, M. (2000). "Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm". Journal on Scientific Computing. 22 (1): 63–80. CiteSeerX 10.1.1.19.1836. doi:10.1137/s1064827598337373.

[party-25] Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). "Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM". Parallel Computing. 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687. doi:10.1016/s0167-8191(00)00043-0.

[dibap-26] Meyerhenke, H.; Monien, B.; Sauerwald, T. (2008). "A New Diffusion-Based Multilevel Algorithm for Computing Graph Partitions". Journal of Parallel Computing and Distributed Computing. 69 (9): 750–761. doi:10.1016/j.jpdc.2009.04.005. S2CID 9755877.

[pdibap-27] Meyerhenke, H. (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. pp. 67–82.

[kahip-28] Sanders, P.; Schulz, C. (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceedings of the 19th European Symposium on Algorithms (ESA). Vol. 6942. pp. 469–480.

[parkway-29] Trifunovic, A.; Knottenbelt, W. J. (2008). "Parallel Multilevel Algorithms for Hypergraph Partitioning". Journal of Parallel and Distributed Computing. 68 (5): 563–581. CiteSeerX 10.1.1.641.7796. doi:10.1016/j.jpdc.2007.11.002.

[zoltan-30] Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Parallel Hypergraph Partitioning for Scientific Computing. Proceedings of the 20th International Conference on Parallel and Distributed Processing. p. 124.

[1]

[3]

[4]

[5]

[6]

[7]

[8]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[9]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

Search