Partycja wykresu

W matematyce podział grafu to redukcja grafu do mniejszego grafu poprzez podzielenie jego zestawu węzłów na wzajemnie wykluczające się grupy. Krawędzie oryginalnego grafu, które przecinają się między grupami, utworzą krawędzie podzielonego grafu. Jeśli liczba wynikowych krawędzi jest niewielka w porównaniu z oryginalnym wykresem, to podzielony wykres może lepiej nadawać się do analizy i rozwiązywania problemów niż oryginalny. Znalezienie partycji, która upraszcza analizę grafów, jest trudnym problemem, ale ma zastosowanie w obliczeniach naukowych, VLSI między innymi projektowanie obwodów i planowanie zadań w komputerach wieloprocesorowych. Ostatnio problem podziału grafów zyskał na znaczeniu ze względu na jego zastosowanie do grupowania i wykrywania klik w sieciach społecznych, patologicznych i biologicznych. Przegląd najnowszych trendów w metodach i aplikacjach obliczeniowych można znaleźć w artykule Buluc i in. (2013) . Dwa typowe przykłady podziału grafów to problemy z minimalnym cięciem i maksymalnym cięciem .

Złożoność problemu

Zazwyczaj problemy z podziałem grafu należą do kategorii problemów NP-trudnych . Rozwiązania tych problemów są na ogół uzyskiwane przy użyciu algorytmów heurystycznych i aproksymacyjnych. Można jednak wykazać, że jednolity podział grafów lub problem zrównoważonego podziału grafów jest NP-zupełny w celu przybliżenia w ramach dowolnego czynnika skończonego. Nawet dla specjalnych klas grafów, takich jak drzewa i siatki, nie istnieją rozsądne algorytmy aproksymacji, chyba że P=NP . Siatki są szczególnie interesującym przypadkiem, ponieważ modelują grafy wynikające z Modelu Elementów Skończonych (MES) symulacje. Przy przybliżaniu nie tylko liczby krawędzi między składnikami, ale także rozmiarów elementów, można wykazać, że dla tych grafów nie istnieją rozsądne algorytmy w pełni wielomianowe.

Problem

Rozważmy graf G = ( V , E ), gdzie V oznacza zbiór n wierzchołków, a E zbiór krawędzi. W przypadku problemu zrównoważonego podziału ( k , v ) celem jest podzielenie G na k składowych o co najwyżej rozmiarze v · ( n / k ), przy jednoczesnej minimalizacji pojemności krawędzi między oddzielnymi składowymi. Ponadto, biorąc pod uwagę G i liczbę całkowitą k > 1, podziel V na k części (podzbiorów) V ₁ , V ₂ , ..., V _k takich, że części są rozłączne i mają równe rozmiary, a liczba krawędzi z punktami końcowymi w różnych częściach jest zminimalizowana. Takie problemy podziału zostały omówione w literaturze jako podejścia oparte na aproksymacji dwukryterialnej lub zwiększaniu zasobów. Typowym rozszerzeniem są hipergrafy , gdzie krawędź może łączyć więcej niż dwa wierzchołki. Hiperkrawędź nie jest cięta, jeśli wszystkie wierzchołki znajdują się w jednej partycji, aw przeciwnym razie jest cięta dokładnie raz, bez względu na liczbę wierzchołków po każdej stronie. To zastosowanie jest powszechne w automatyzacji projektowania elektronicznego .

Analiza

Dla określonego ( k , 1 + ε ) problemu zrównoważonego podziału szukamy podziału G o minimalnym koszcie na k składników, przy czym każdy składnik zawiera maksymalnie (1 + ε ) · ( n / k ) węzłów. Porównujemy koszt tego algorytmu aproksymacji do kosztu cięcia ( k ,1), gdzie każdy z k elementów musi mieć ten sam rozmiar ( n / k ) węzłów, co stanowi bardziej ograniczony problem. Zatem,

{\ Displaystyle \ max _ {i} | V_ {i} | \ równoważnik (1 + \ varepsilon) \ lewo \ lceil {\ Frac {| V |} {k}} \ prawo \ rceil.}

Wiemy już, że przecięcie (2,1) jest problemem minimalnej bisekcji i jest NP-zupełne. Następnie oceniamy problem 3-częściowy, w którym n = 3 k , który jest również ograniczony w czasie wielomianowym. Teraz, jeśli założymy, że mamy skończony algorytm aproksymacji dla ( k , 1)-zrównoważonego podziału, to albo instancja z 3 podziałami może zostać rozwiązana przy użyciu zrównoważonego podziału ( k , 1) w G , albo nie może zostać rozwiązana. Jeśli można rozwiązać instancję z 3 partycjami, to ( k , 1) - zrównoważony problem partycjonowania w G można rozwiązać bez cięcia krawędzi. W przeciwnym razie, jeśli nie można rozwiązać instancji z 3 partycjami, optymalne ( k , 1)-zrównoważone partycjonowanie w G przetnie co najmniej jedną krawędź. Algorytm aproksymacji ze skończonym współczynnikiem aproksymacji musi rozróżniać te dwa przypadki. W związku z tym może rozwiązać problem 3-partycji, co jest sprzecznością przy założeniu, że P = NP . Jest zatem oczywiste, że ( k ,1)-zrównoważony problem podziału nie ma algorytmu aproksymacji w czasie wielomianowym ze skończonym współczynnikiem aproksymacji, chyba że P = NP .

Twierdzenie o separatorze planarnym stwierdza, że dowolny planarny wykres n -wierzchołków można podzielić na mniej więcej równe części przez usunięcie wierzchołków O ( √ n ). To nie jest partycja w sensie opisanym powyżej, ponieważ zbiór partycji składa się z wierzchołków, a nie krawędzi. Jednak ten sam wynik implikuje również, że każdy graf planarny o ograniczonym stopniu ma zrównoważone cięcie z krawędziami O ( √ n ).

Metody podziału grafów

Ponieważ partycjonowanie grafów jest trudnym problemem, praktyczne rozwiązania opierają się na heurystyce. Istnieją dwie szerokie kategorie metod, lokalne i globalne. Dobrze znane metody lokalne to algorytm Kernighana – Lin i algorytmy Fiduccia-Mattheyses , które były pierwszymi skutecznymi dwukierunkowymi cięciami w lokalnych strategiach wyszukiwania. Ich główną wadą jest arbitralne początkowe dzielenie zbioru wierzchołków, co może mieć wpływ na końcową jakość rozwiązania. Podejścia globalne opierają się na właściwościach całego grafu i nie opierają się na dowolnym podziale początkowym. Najczęstszym przykładem jest podział widmowy, w którym podział jest wyprowadzany z przybliżonych wektorów własnych macierzy sąsiedztwa lub grupowanie widmowe , które grupuje wierzchołki wykresu przy użyciu rozkładu własnego macierzy Laplaca .

Metody wielopoziomowe

Algorytm wielopoziomowego podziału grafu działa na zasadzie stosowania jednego lub większej liczby etapów. Każdy etap zmniejsza rozmiar grafu poprzez zwijanie wierzchołków i krawędzi, dzieli mniejszy graf, a następnie odwzorowuje i udoskonala ten podział oryginalnego grafu. W ogólnym schemacie wielopoziomowym można zastosować szeroką gamę metod partycjonowania i udoskonalania. W wielu przypadkach takie podejście może zapewnić zarówno szybkie czasy realizacji, jak i bardzo wysoką jakość wyników. Jednym z szeroko stosowanych przykładów takiego podejścia jest METIS , narzędzie do partycjonowania grafów i hMETIS , odpowiednie narzędzie do partycjonowania dla hipergrafów. Alternatywne podejście wywodzi się i jest wdrażane m.in scikit-learn to grupowanie widmowe z podziałem określonym na podstawie wektorów własnych macierzy Laplace'a grafu dla oryginalnego grafu obliczonego przez solver LOBPCG z wielosiatkowym uwarunkowaniem wstępnym .

Podział widmowy i bisekcja widmowa

$}$ uwagę wykres $macierzą$ sąsiedztwa , wpis implikuje krawędź między węzłem $Displaystyle A_$ ${\ displaystyle i}$ i $j}$ $displaystyle$ i macierz stopni , która jest macierzą diagonalną, gdzie każdy przekątny wpis w rzędzie ${\ displaystyle i$ re ${\ displaystyle d_ {ii}}$ , reprezentuje stopień węzła węzła ${\ displaystyle i$ . Macierz Laplace'a jest $zdefiniowana$ jako ${\ displaystyle L = DA$ . Teraz podział z podziałem proporcjonalnym dla wykresu jest definiowany jako podział na rozłączne $(V, E)}$ $Displaystyle G$ ${\ displaystyle U$ $minimalizując$ i współczynnik

{\ Displaystyle {\ Frac {| E (G) \ cap (U \ razy W) |} {| U | \ cdot | W|}}}

liczby krawędzi, które faktycznie przecinają to cięcie, do liczby par wierzchołków, które mogłyby wspierać takie krawędzie. Podział grafów widmowych może być motywowany analogią do podziału wibrującej struny lub układu masa-sprężyna i podobnie rozszerzony na przypadek ujemnych wag grafu.

Wartość własna Fiedlera i wektor własny

$)$ takim scenariuszu druga najmniejsza wartość własna ( ) z $L}$ $displaystyle$ daje dolną granicę optymalnego stosunku- wytnij partycję za pomocą do $\ Displaystyle c \ geq {\ Frac {\ lambda _ {2}} {n}}}$ . Wektor własny ( ) odpowiadający $_$ ${\ Displaystyle \ lambda$ , zwany wektorem Fiedlera , dzieli wykres na dwie połowy w oparciu o znak odpowiedniego wpisu wektora . Podział na większą liczbę społeczności można osiągnąć przez wielokrotne przepołowienie lub użycie wielu wektorów własnych odpowiadających najmniejszym wartościom własnym. Przykłady na rysunkach 1 i 2 ilustrują podejście polegające na bisekcji widmowej.

Rysunek 1: Wykres G = (5,4) jest analizowany pod kątem bisekcji widmowej. Liniowa kombinacja najmniejszych dwóch wektorów własnych prowadzi do tego, że [1 1 1 1 1]' ma wartość własną = 0.

Rysunek 2: Wykres G = (5,5) ilustruje, że wektor Fiedlera zaznaczony na czerwono dzieli wykres na dwie społeczności, jedną z wierzchołkami {1,2,3} z dodatnimi wpisami w przestrzeni wektorowej, a drugą społeczność z wierzchołkami {4,5} z ujemnymi wpisami w przestrzeni wektorowej.

Modułowość i proporcjonalne cięcie

Partycjonowanie z minimalnym cięciem kończy się jednak niepowodzeniem, gdy liczba społeczności do partycjonowania lub rozmiary partycji są nieznane. Na przykład optymalizacja rozmiaru cięcia dla dowolnych rozmiarów grup umieszcza wszystkie wierzchołki w tej samej społeczności. Ponadto wielkość cięcia może być niewłaściwą rzeczą do minimalizowania, ponieważ dobry podział to nie tylko podział z niewielką liczbą krawędzi między społecznościami. To zmotywowało do wykorzystania modułowości (Q) jako metryki do optymalizacji zrównoważonego podziału grafu. Przykład na rysunku 3 ilustruje 2 przypadki tego samego wykresu, tak że w (a) modułowość (Q) jest metryką podziału, aw (b) , proporcja cięcia jest metryką podziału.

Rysunek 3: Graf ważony G można podzielić, aby zmaksymalizować Q w (a) lub zminimalizować stosunek podziału w (b). Widzimy, że (a) jest lepiej zrównoważonym podziałem, motywując w ten sposób znaczenie modułowości w problemach z podziałem grafów.

Aplikacje

Przewodnictwo

Inną funkcją celu stosowaną do podziału wykresów jest przewodność , która jest stosunkiem liczby ciętych krawędzi do objętości najmniejszej części. Przewodnictwo jest związane z przepływami elektrycznymi i błądzeniem losowym. Wiązanie Cheegera gwarantuje , że bisekcja widmowa zapewnia przegrody o prawie optymalnym przewodnictwie. Jakość tego przybliżenia zależy od drugiej najmniejszej wartości własnej Laplace'a λ ₂ .

Immunizacja

Podział wykresu może być przydatny do identyfikacji minimalnego zestawu węzłów lub połączeń, które należy zaszczepić, aby powstrzymać epidemie.

Inne metody podziału grafów

Modele spinowe zostały wykorzystane do grupowania danych wielowymiarowych, w których podobieństwa przekładają się na siłę sprzężenia. Właściwości konfiguracji spinu stanu podstawowego można bezpośrednio interpretować jako społeczności. W ten sposób graf jest dzielony, aby zminimalizować hamiltonian podzielonego grafu. Hamiltonian (H) uzyskuje się, przypisując następujące nagrody i kary za partycje .

Nagradzaj wewnętrzne krawędzie między węzłami tej samej grupy (ten sam spin)
Karaj brakujące krawędzie w tej samej grupie
Penalizuj istniejące krawędzie między różnymi grupami
Nagradzaj brak powiązań między różnymi grupami.

Dodatkowo klastrowanie spektralne oparte na jądrze-PCA przybiera formę struktury maszyny wektorów nośnych najmniejszych kwadratów, dzięki czemu możliwe staje się rzutowanie wpisów danych na przestrzeń cech indukowaną przez jądro, która ma maksymalną wariancję, co implikuje dużą separację między projektowanymi społecznościami .

Niektóre metody wyrażają podział grafu jako problem optymalizacji wielokryterialnej, który można rozwiązać za pomocą lokalnych metod wyrażonych w ramach teorii gier, w których każdy węzeł podejmuje decyzję o wybranym przez siebie podziale.

W przypadku grafów rozproszonych o bardzo dużej skali klasyczne metody podziału mogą nie mieć zastosowania (np. partycjonowanie widmowe , Metis), ponieważ wymagają pełnego dostępu do danych grafu w celu wykonywania operacji globalnych. W przypadku takich scenariuszy na dużą skalę partycjonowanie grafu rozproszonego jest używane do partycjonowania tylko za pomocą asynchronicznych operacji lokalnych.

Narzędzia programowe

scikit-learn implementuje spektralne klastrowanie z podziałem określonym na podstawie wektorów własnych macierzy Laplace'a grafu dla oryginalnego grafu obliczonego przez ARPACK lub solver LOBPCG z wielosiatkowym uwarunkowaniem wstępnym .

Chaco, dzięki Hendricksonowi i Lelandowi, wdraża opisane powyżej podejście wielopoziomowe oraz podstawowe algorytmy wyszukiwania lokalnego. Ponadto implementują techniki partycjonowania widmowego.

METIS to rodzina podziału grafów autorstwa Karypisa i Kumara. Wśród tej rodziny kMetis ma na celu większą szybkość partycjonowania, hMetis dotyczy hipergrafów i ma na celu jakość partycji, a ParMetis jest równoległą implementacją algorytmu partycjonowania grafu Metis.

PaToH to kolejny partycjoner hipergrafów.

KaHyPar to wielopoziomowa struktura partycjonowania hipergrafów, zapewniająca bezpośrednie algorytmy partycjonowania oparte na k-way i rekurencyjnym bisekcji. Urzeczywistnia podejście wielopoziomowe w jego najbardziej ekstremalnej wersji, usuwając tylko jeden wierzchołek na każdym poziomie hierarchii. Wykorzystując to bardzo precyzyjne n -poziomowe podejście w połączeniu z silną heurystyką wyszukiwania lokalnego, oblicza rozwiązania o bardzo wysokiej jakości.

Scotch to platforma do partycjonowania grafów autorstwa Pellegriniego. Wykorzystuje rekurencyjne wielopoziomowe przecinanie i obejmuje sekwencyjne oraz równoległe techniki partycjonowania.

Jostle to rozwiązanie do sekwencyjnego i równoległego partycjonowania grafów opracowane przez Chrisa Walshawa. Skomercjalizowana wersja tego programu do partycjonowania nosi nazwę NetWorks.

Party implementuje platformę zoptymalizowaną pod kątem Bubble/Shape oraz algorytm Helpful Sets.

Pakiety oprogramowania DibaP i jego równoległy wariant MPI PDibaP firmy Meyerhenke implementują strukturę Bubble za pomocą dyfuzji; DibaP wykorzystuje również techniki oparte na AMG do zgrubnego i rozwiązywania układów liniowych powstających w podejściu dyfuzyjnym.

Sanders i Schulz wydali pakiet do partycjonowania grafów KaHIP (Karlsruhe High Quality Partitioning), który implementuje na przykład metody oparte na przepływie, bardziej zlokalizowane wyszukiwania lokalne oraz kilka równoległych i sekwencyjnych metaheurystyk.

Narzędzia Parkway autorstwa Trifunovic i Knottenbelt oraz Zoltan autorstwa Devine i in. skoncentruj się na partycjonowaniu hipergrafów.

Lista darmowych frameworków open source:

Nazwa	Licencja	Krótka informacja
Chaco	GPL	pakiet oprogramowania wdrażający techniki spektralne i podejście wielopoziomowe
DiBaP	*	partycjonowanie grafów w oparciu o techniki wielopoziomowe, multigrid algebraiczny oraz dyfuzję opartą na grafach
Popchnąć	*	wielopoziomowe techniki partycjonowania i dyfuzyjne równoważenie obciążenia, sekwencyjne i równoległe
KaHIP	MIT	kilka równoległych i sekwencyjnych metaheurystyk, gwarantuje ograniczenie równowagi, wsparcie dla Pythona
KaHyPar	GPL	bezpośredni wielopoziomowy schemat partycjonowania hipergrafów oparty na k-way i rekurencyjnym bisekcji
kMetis	Apache 2.0	pakiet partycjonowania grafów oparty na technikach wielopoziomowych i lokalnym wyszukiwaniu k-way
Mondriaan	LGPL	partycjoner macierzy do partycjonowania prostokątnych rzadkich macierzy
PaToH	BSD	wielopoziomowe partycjonowanie hipergrafów
Parkowa	*	równoległe wielopoziomowe partycjonowanie hipergrafów
nauka scikit	BSD	partycjonowanie widmowe z algebraicznym uwarunkowaniem wielosiatkowym
Szkocka	CeCILL-C	implementuje wielopoziomową rekurencyjną bisekcję oraz techniki dyfuzyjne, sekwencyjne i równoległe
Zoltana	BSD	partycjonowanie hipergrafów

^ ^a ^b ^c ^d ^e Andreev, Konstantin; Racke, Harald (2004). Zrównoważone partycjonowanie grafu . Materiały z szesnastego dorocznego sympozjum ACM na temat równoległości w algorytmach i architekturach . Barcelona, Hiszpania. s. 120–124. CiteSeerX 10.1.1.417.8592 . doi : 10.1145/1007912.1007931 . ISBN 978-1-58113-840-5 .
Bibliografia _ Meyerhenke, Henning; Safro, Ilya; Sanders, Piotr ; Schulz, Chrześcijanin (2013). „Najnowsze postępy w partycjonowaniu grafów”. arXiv : 1311.3144 [ cs.DS ].
^ Feldmann, Andreas Emil; Foschini, Luca (2012). „Zrównoważone partycje drzew i aplikacji”. Materiały z 29. Międzynarodowego Sympozjum poświęconego teoretycznym aspektom informatyki : 100–111.
^ ^a ^b Feldmann, Andreas Emil (2012). „Szybkie, zrównoważone partycjonowanie jest trudne, nawet w przypadku siatek i drzew” . Materiały z 37. Międzynarodowego Sympozjum Matematyczne Podstawy Informatyki . ar Xiv : 1111.6745 . Bibcode : 2011arXiv1111.6745F .
Bibliografia _ Johnson, David S. (1979). Komputery i trudność: przewodnik po teorii NP-zupełności . WH Freeman & Co. ISBN 978-0-7167-1044-8 .
Bibliografia _ Leland, R. (1995). Wielopoziomowy algorytm podziału grafów . Materiały z konferencji ACM/IEEE z 1995 r. poświęconej superkomputerom. ACM. P. 28.
^ ^abcd ^Karypis ^,^G .; Kumar, V. (1999). „Szybki i wysokiej jakości wielopoziomowy schemat partycjonowania nieregularnych wykresów”. SIAM Journal o obliczeniach naukowych . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137/S1064827595287997 . S2CID 3628209 .
^ ^ab ^Karypis , G.; Aggarwal R.; Kumar, V.; Shekhar, S. (1997). Wielopoziomowe partycjonowanie hipergrafów: zastosowanie w domenie VLSI . Materiały z 34. dorocznej konferencji Design Automation. s. 526–529.
^ ^a ^b Knyazev, Andrew V. (2006). Wieloskalowe partycjonowanie grafów widmowych i segmentacja obrazu . Warsztaty na temat algorytmów dla nowoczesnych masowych zbiorów danych Uniwersytet Stanforda i Yahoo! Badania.
^ J. Demmel, [1] , CS267: Uwagi do wykładu 23, 9 kwietnia 1999, Partycjonowanie wykresów, część 2
^ Kniazew, Andrzej (2018). O partycjonowaniu widmowym grafów ze znakiem . Ósme warsztaty SIAM dotyczące Combinatorial Scientific Computing, CSC 2018, Bergen, Norwegia, 6-8 czerwca. doi : 10.1137/1.9781611975215.2 .
Bibliografia _ Księżyc, T. (2016). „Równoległe partycjonowanie grafów widmowych” . Raport techniczny NVIDIA . nvr-2016-001.
^ Newman, MEJ (2006). „Modułowość i struktura społeczności w sieciach” . PNAS . 103 (23): 8577–8696. arXiv : fizyka/0602124 . Bibcode : 2006PNAS..103.8577N . doi : 10.1073/pnas.0601602103 . PMC 1482622 . PMID 16723398 .
^ Y. Chen, G. Paul, S. Havlin, F. Liljeros, JE Stanley (2009). „Znalezienie lepszej strategii szczepień” . fizyka Wielebny Lett . 101 (5): 058701. doi : 10.1103/PhysRevLett.101.058701 . PMID 18764435 . {{ cite journal }} : CS1 maint: wiele nazwisk: lista autorów ( link )
Bibliografia _ Bornholdt, Stefan (lipiec 2006). „Mechanika statystyczna wykrywania społeczności”. fizyka Wielebny 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 AK (2010). „Wielokierunkowe klastrowanie widmowe z rozszerzeniami poza próbką przez PCA ważonego jądra” . Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej . 32 (2): 335–347. doi : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462 . S2CID 200488 .
^ Krzywa, A .; Griffin, C.; Kesidis G. (2011) „Gra z podziałem grafów do rozproszonej symulacji sieci”, Proceedings of the International Workshop on 2011 on Modeling, Analysis, and Control of Complex Networks : 9–16
Bibliografia _ „Chaco: oprogramowanie do partycjonowania wykresów”. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
^ Catalyürek, Ü .; Aykanat, C. (2011). PaToH: narzędzie do partycjonowania hipergrafów .
Bibliografia _ Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). „K-kierunkowe partycjonowanie hipergrafu za pomocą rekurencyjnego bisekcji na poziomie n”. 2016 Materiały z XVIII Warsztatów Inżynierii Algorytmów i Eksperymentów (ALENEX) . Obrady. Towarzystwo Matematyki Przemysłowej i Stosowanej. s. 53–67. ar Xiv : 1511.03137 . doi : 10.1137/1.9781611974317.5 . ISBN 978-1-61197-431-7 . S2CID 1674598 .
^ Achremcew, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). „Inżynieria bezpośredniego algorytmu partycjonowania hipergrafu k-way” . 2017 Materiały z XIX Warsztatów Inżynierii Algorytmów i Eksperymentów (ALENEX) . Obrady. Towarzystwo Matematyki Przemysłowej i Stosowanej. s. 28–42. doi : 10.1137/1.9781611974768.3 . ISBN 978-1-61197-476-8 .
^ Heuer, Tobiasz; Schlag, Sebastian (2017). Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (red.). Udoskonalanie schematów zgrubnych partycjonowania hipergrafów przez wykorzystanie struktury społeczności . 16. Międzynarodowe Sympozjum Algorytmów Eksperymentalnych (SEA 2017) . Leibniz International Proceedings in Informatics (LIPIcs). Tom. 75. Dagstuhl, Niemcy: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. s. 21:1–21:19. doi : 10.4230/LIPIcs.SEA.2017.21 . ISBN 9783959770361 .
^ Chevalier, C .; Pellegrini, F. (2008). „PT-Scotch: narzędzie do wydajnego porządkowania wykresów równoległych”. Obliczenia równoległe . 34 (6): 318–331. ar Xiv : 0907.1375 . doi : 10.1016/j.parco.2007.12.001 . S2CID 10433524 .
Bibliografia _ Krzyż, M. (2000). „Podział siatki: wielopoziomowy algorytm równoważenia i udoskonalania”. Czasopismo o obliczeniach naukowych . 22 (1): 63–80. Bibcode : 2000SJSC...22...63W . CiteSeerX 10.1.1.19.1836 . doi : 10.1137/s1064827598337373 .
Bibliografia _ Preis, R.; Schlimbach, F.; Walshaw, C. (2000). „Podział siatki zoptymalizowany pod kątem kształtu i równoważenie obciążenia dla równoległego adaptacyjnego MES” . Obliczenia równoległe . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . doi : 10.1016/s0167-8191(00)00043-0 .
Bibliografia _ Monien, B.; Sauerwald, T. (2008). „Nowy wielopoziomowy algorytm oparty na dyfuzji do obliczania partycji grafów”. Journal of Parallel Computing i Distributed Computing . 69 (9): 750–761. doi : 10.1016/j.jpdc.2009.04.005 . S2CID 9755877 .
^ Meyerhenke, H. (2013). Równoważenie obciążenia z optymalizacją kształtu dla adaptacyjnych symulacji numerycznych MPI-Parallel . 10. wyzwanie wdrożeniowe DIMACS dotyczące partycjonowania grafów i grupowania grafów. s. 67–82.
Bibliografia _ _ Schulz, C. (2011). Inżynieria wielopoziomowych algorytmów partycjonowania grafów . Materiały z 19. Europejskiego Sympozjum Algorytmów (ESA). Tom. 6942. s. 469–480.
Bibliografia _ Wiązany pas, WJ (2008). „Równoległe algorytmy wielopoziomowe do partycjonowania hipergrafów”. Dziennik obliczeń równoległych i rozproszonych . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . doi : 10.1016/j.jpdc.2007.11.002 .
Bibliografia _ Boman, E.; Gruby, R.; Bisseling, R.; Catalyurek, Ü. (2006). Równoległe partycjonowanie hipergrafów w obliczeniach naukowych . Materiały z 20. Międzynarodowej Konferencji na temat Przetwarzania Równoległego i Rozproszonego. P. 124.

Linki zewnętrzne

Szambelan, Bradford L. (1998). „Algorytmy partycjonowania wykresów do dystrybucji obciążeń obliczeń równoległych” ^{[ stały martwy link ]}

Bibliografia

Bichot, Charles-Edmond; Siarry, Patrick (2011). Partycjonowanie grafów: optymalizacja i aplikacje . ISTE – Wiley. P. 384. ISBN 978-1848212336 .
Feldmann, Andreas Emil (2012). Zrównoważone partycjonowanie siatek i powiązanych grafów: teoretyczne badanie dystrybucji danych w równoległych symulacjach modelu elementów skończonych . Goettingen, Niemcy: Cuvillier Verlag. P. 218. ISBN 978-3954041251 . Wyczerpująca analiza problemu z teoretycznego punktu widzenia.
Kernighan, BW; Lin, S. (1970). „Wydajna heurystyczna procedura podziału wykresów” (PDF) . Dziennik techniczny systemu Bell . 49 (2): 291–307. doi : 10.1002/j.1538-7305.1970.tb01770.x . Jedna z pierwszych fundamentalnych prac w tej dziedzinie. Jednak wydajność to O(n ² ), więc nie jest już powszechnie używana.
Fiduccia, CM; Mattheyses, RM (1982). Heurystyka czasu liniowego do ulepszania partycji sieciowych . Konferencja o automatyzacji projektowania. doi : 10.1109/DAC.1982.1585498 . Późniejszy wariant, czyli czas liniowy, bardzo często używany, zarówno samodzielnie, jak i jako część partycjonowania wielopoziomowego, patrz poniżej.
Karypis, G.; Kumar, V. (1999). „Szybki i wysokiej jakości wielopoziomowy schemat podziału nieregularnych wykresów” . SIAM Journal o obliczeniach naukowych . Partycjonowanie wielopoziomowe to aktualny stan techniki. Ten artykuł zawiera również dobre wyjaśnienia wielu innych metod i porównania różnych metod w odniesieniu do wielu różnych problemów.
Karypis, G.; Aggarwal R.; Kumar, V.; Shekhar, S. (marzec 1999). „Wielopoziomowe partycjonowanie hipergrafów: aplikacje w domenie VLSI”. Transakcje IEEE w systemach integracji na bardzo dużą skalę (VLSI) . 7 (1): 69–79. CiteSeerX 10.1.1.553.2367 . doi : 10.1109/92.748202 . Partycjonowanie grafów (aw szczególności partycjonowanie hipergrafów) ma wiele zastosowań w projektowaniu układów scalonych.
Kirkpatrick, S.; Gelatt, CD Jr.; Vecchi, poseł (13 maja 1983). „Optymalizacja przez symulowane wyżarzanie”. nauka . 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 . Można również zastosować symulowane wyżarzanie.
Hagen, L.; Kahng, AB (wrzesień 1992). „Nowe metody widmowe do partycjonowania i grupowania z cięciem proporcji”. Transakcje IEEE dotyczące wspomaganego komputerowo projektowania układów scalonych i systemów . 11 (9): 1074–1085. doi : 10.1109/43.159993 . . Istnieje cała klasa podziału widmowego , które wykorzystują wektory własne Laplace'a grafu łączności. Możesz zobaczyć demo tego , używając Matlaba.

[balgraph-1] Andreev, Konstantin; Racke, Harald (2004). Zrównoważone partycjonowanie grafu . Materiały z szesnastego dorocznego sympozjum ACM na temat równoległości w algorytmach i architekturach . Barcelona, Hiszpania. s. 120–124. CiteSeerX 10.1.1.417.8592 . doi : 10.1145/1007912.1007931 . ISBN 978-1-58113-840-5 .

[recentadvances-2] Bibliografia _ Meyerhenke, Henning; Safro, Ilya; Sanders, Piotr ; Schulz, Chrześcijanin (2013). „Najnowsze postępy w partycjonowaniu grafów”. arXiv : 1311.3144 [ cs.DS ].

[baltrees-3] Feldmann, Andreas Emil; Foschini, Luca (2012). „Zrównoważone partycje drzew i aplikacji”. Materiały z 29. Międzynarodowego Sympozjum poświęconego teoretycznym aspektom informatyki : 100–111.

[fastpartition-4] Feldmann, Andreas Emil (2012). „Szybkie, zrównoważone partycjonowanie jest trudne, nawet w przypadku siatek i drzew” . Materiały z 37. Międzynarodowego Sympozjum Matematyczne Podstawy Informatyki . ar Xiv : 1111.6745 . Bibcode : 2011arXiv1111.6745F .

[minbisect-5] Bibliografia _ Johnson, David S. (1979). Komputery i trudność: przewodnik po teorii NP-zupełności . WH Freeman & Co. ISBN 978-0-7167-1044-8 .

[6] Bibliografia _ Leland, R. (1995). Wielopoziomowy algorytm podziału grafów . Materiały z konferencji ACM/IEEE z 1995 r. poświęconej superkomputerom. ACM. P. 28.

[:0-7] Karypis ^,^G .; Kumar, V. (1999). „Szybki i wysokiej jakości wielopoziomowy schemat partycjonowania nieregularnych wykresów”. SIAM Journal o obliczeniach naukowych . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi : 10.1137/S1064827595287997 . S2CID 3628209 .

[hmetis-8] Karypis , G.; Aggarwal R.; Kumar, V.; Shekhar, S. (1997). Wielopoziomowe partycjonowanie hipergrafów: zastosowanie w domenie VLSI . Materiały z 34. dorocznej konferencji Design Automation. s. 526–529.

[spectralmultigrid2006-9] Knyazev, Andrew V. (2006). Wieloskalowe partycjonowanie grafów widmowych i segmentacja obrazu . Warsztaty na temat algorytmów dla nowoczesnych masowych zbiorów danych Uniwersytet Stanforda i Yahoo! Badania.

[10] J. Demmel, [1] , CS267: Uwagi do wykładu 23, 9 kwietnia 1999, Partycjonowanie wykresów, część 2

[11] Kniazew, Andrzej (2018). O partycjonowaniu widmowym grafów ze znakiem . Ósme warsztaty SIAM dotyczące Combinatorial Scientific Computing, CSC 2018, Bergen, Norwegia, 6-8 czerwca. doi : 10.1137/1.9781611975215.2 .

[spectral_nvidia_tr-12] Bibliografia _ Księżyc, T. (2016). „Równoległe partycjonowanie grafów widmowych” . Raport techniczny NVIDIA . nvr-2016-001.

[npnas-13] Newman, MEJ (2006). „Modułowość i struktura społeczności w sieciach” . PNAS . 103 (23): 8577–8696. arXiv : fizyka/0602124 . Bibcode : 2006PNAS..103.8577N . doi : 10.1073/pnas.0601602103 . PMC 1482622 . PMID 16723398 .

[14] Y. Chen, G. Paul, S. Havlin, F. Liljeros, JE Stanley (2009). „Znalezienie lepszej strategii szczepień” . fizyka Wielebny Lett . 101 (5): 058701. doi : 10.1103/PhysRevLett.101.058701 . PMID 18764435 . {{ cite journal }} : CS1 maint: wiele nazwisk: lista autorów ( link )

[potts-15] Bibliografia _ Bornholdt, Stefan (lipiec 2006). „Mechanika statystyczna wykrywania społeczności”. fizyka Wielebny 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 AK (2010). „Wielokierunkowe klastrowanie widmowe z rozszerzeniami poza próbką przez PCA ważonego jądra” . Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej . 32 (2): 335–347. doi : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462 . S2CID 200488 .

[17] Krzywa, A .; Griffin, C.; Kesidis G. (2011) „Gra z podziałem grafów do rozproszonej symulacji sieci”, Proceedings of the International Workshop on 2011 on Modeling, Analysis, and Control of Complex Networks : 9–16

[chaco-18] Bibliografia _ „Chaco: oprogramowanie do partycjonowania wykresów”. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )

[patoh-19] Catalyürek, Ü .; Aykanat, C. (2011). PaToH: narzędzie do partycjonowania hipergrafów .

[20] Bibliografia _ Henne, V.; Heuer, T.; Meyerhenke, H.; Sanders, P.; Schulz, C. (2015-12-30). „K-kierunkowe partycjonowanie hipergrafu za pomocą rekurencyjnego bisekcji na poziomie n”. 2016 Materiały z XVIII Warsztatów Inżynierii Algorytmów i Eksperymentów (ALENEX) . Obrady. Towarzystwo Matematyki Przemysłowej i Stosowanej. s. 53–67. ar Xiv : 1511.03137 . doi : 10.1137/1.9781611974317.5 . ISBN 978-1-61197-431-7 . S2CID 1674598 .

[21] Achremcew, Y.; Heuer, T.; Sanders, P.; Schlag, S. (2017-01-01). „Inżynieria bezpośredniego algorytmu partycjonowania hipergrafu k-way” . 2017 Materiały z XIX Warsztatów Inżynierii Algorytmów i Eksperymentów (ALENEX) . Obrady. Towarzystwo Matematyki Przemysłowej i Stosowanej. s. 28–42. doi : 10.1137/1.9781611974768.3 . ISBN 978-1-61197-476-8 .

[22] Heuer, Tobiasz; Schlag, Sebastian (2017). Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (red.). Udoskonalanie schematów zgrubnych partycjonowania hipergrafów przez wykorzystanie struktury społeczności . 16. Międzynarodowe Sympozjum Algorytmów Eksperymentalnych (SEA 2017) . Leibniz International Proceedings in Informatics (LIPIcs). Tom. 75. Dagstuhl, Niemcy: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. s. 21:1–21:19. doi : 10.4230/LIPIcs.SEA.2017.21 . ISBN 9783959770361 .

[scotch-23] Chevalier, C .; Pellegrini, F. (2008). „PT-Scotch: narzędzie do wydajnego porządkowania wykresów równoległych”. Obliczenia równoległe . 34 (6): 318–331. ar Xiv : 0907.1375 . doi : 10.1016/j.parco.2007.12.001 . S2CID 10433524 .

[jostle-24] Bibliografia _ Krzyż, M. (2000). „Podział siatki: wielopoziomowy algorytm równoważenia i udoskonalania”. Czasopismo o obliczeniach naukowych . 22 (1): 63–80. Bibcode : 2000SJSC...22...63W . CiteSeerX 10.1.1.19.1836 . doi : 10.1137/s1064827598337373 .

[party-25] Bibliografia _ Preis, R.; Schlimbach, F.; Walshaw, C. (2000). „Podział siatki zoptymalizowany pod kątem kształtu i równoważenie obciążenia dla równoległego adaptacyjnego MES” . Obliczenia równoległe . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . doi : 10.1016/s0167-8191(00)00043-0 .

[dibap-26] Bibliografia _ Monien, B.; Sauerwald, T. (2008). „Nowy wielopoziomowy algorytm oparty na dyfuzji do obliczania partycji grafów”. Journal of Parallel Computing i Distributed Computing . 69 (9): 750–761. doi : 10.1016/j.jpdc.2009.04.005 . S2CID 9755877 .

[pdibap-27] Meyerhenke, H. (2013). Równoważenie obciążenia z optymalizacją kształtu dla adaptacyjnych symulacji numerycznych MPI-Parallel . 10. wyzwanie wdrożeniowe DIMACS dotyczące partycjonowania grafów i grupowania grafów. s. 67–82.

[kahip-28] Bibliografia _ _ Schulz, C. (2011). Inżynieria wielopoziomowych algorytmów partycjonowania grafów . Materiały z 19. Europejskiego Sympozjum Algorytmów (ESA). Tom. 6942. s. 469–480.

[parkway-29] Bibliografia _ Wiązany pas, WJ (2008). „Równoległe algorytmy wielopoziomowe do partycjonowania hipergrafów”. Dziennik obliczeń równoległych i rozproszonych . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . doi : 10.1016/j.jpdc.2007.11.002 .

[zoltan-30] Bibliografia _ Boman, E.; Gruby, R.; Bisseling, R.; Catalyurek, Ü. (2006). Równoległe partycjonowanie hipergrafów w obliczeniach naukowych . Materiały z 20. Międzynarodowej Konferencji na temat Przetwarzania Równoległego i Rozproszonego. P. 124.