Partycja wykresu - Graph partition

W matematyce podział grafu polega na redukcji grafu do mniejszego grafu poprzez podzielenie jego zbioru węzłów na wzajemnie wykluczające się grupy. Krawędzie oryginalnego grafu, które przecinają się między grupami, spowodują powstanie krawędzi w grafie podzielonym. Jeśli liczba otrzymanych krawędzi jest niewielka w porównaniu z oryginalnym wykresem, wówczas wykres podzielony na partycje może być lepiej dostosowany do analizy i rozwiązywania problemów niż oryginalny. Znalezienie partycji, która upraszcza analizę grafów, jest trudnym problemem, ale ma zastosowanie między innymi do obliczeń naukowych, projektowania obwodów VLSI i planowania 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 obliczeniowych i zastosowaniach można znaleźć w Buluc et al. (2013) . Dwoma typowymi przykładami podziału wykresów są problemy z minimalnym i maksymalnym cięciem .

Złożoność problemu

Zazwyczaj problemy podziału grafów należą do kategorii problemów NP-trudnych . Rozwiązania tych problemów są zazwyczaj wyprowadzane przy użyciu algorytmów heurystycznych i aproksymacyjnych. Jednak równomierny podział grafów lub zrównoważony problem podziału grafów można wykazać jako NP-zupełny w przybliżeniu w ramach dowolnego współczynnika skończonego. Nawet dla specjalnych klas grafów, takich jak drzewa i siatki, nie istnieją żadne rozsądne algorytmy aproksymacyjne, chyba że P=NP . Siatki są szczególnie interesującym przypadkiem, ponieważ modelują wykresy wynikające z symulacji modelu elementów skończonych (MES) . Aproksymując nie tylko liczbę krawędzi pomiędzy składowymi, ale także rozmiary składowych, można wykazać, że dla tych grafów nie istnieją żadne 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ładników o co najwyżej wielkości v · ( n / k ), przy jednoczesnym zminimalizowaniu pojemności krawędzi między oddzielnymi składnikami. Również, mając dane G i liczbę całkowitą k > 1, podziel V na k części (podzbiorów) V ₁ , V ₂ , ..., V _k tak, że części są rozłączne i mają jednakowy rozmiar oraz liczbę krawędzi z punktami końcowymi w różne części są zminimalizowane. Takie problemy z podziałem zostały omówione w literaturze jako podejścia do aproksymacji dwukryterialnych lub do zwiększania zasobów. Powszechnym rozszerzeniem są hipergrafy , w których krawędź może łączyć więcej niż dwa wierzchołki. Hiperedge nie jest wycinany, jeśli wszystkie wierzchołki znajdują się w jednej partycji, aw przeciwnym razie wycinany jest dokładnie raz, bez względu na to, ile wierzchołków znajduje się po każdej stronie. To zastosowanie jest powszechne w automatyzacji projektowania elektronicznego .

Analiza

Dla konkretnego problemu zrównoważonego podziału ( k , 1 +  ε ) staramy się znaleźć minimalny koszt podziału G na k składników, przy czym każdy składnik zawiera maksymalnie (1 +  ε )·( n / k ) węzłów. Porównujemy koszt tego algorytmu aproksymacyjnego do kosztu ( k ,1) cięcia, w którym każdy z k składowych musi mieć ten sam rozmiar ( n / k ) węzłów, co stanowi bardziej ograniczony problem. Zatem,

${\ Displaystyle \ max _ {i} | V_ {i} | \ leq (1+ \ varepsilon) \ lewo \ lceil {\ Frac {| V |} {k}} \ prawo \ rceil.}$

Wiemy już, że cięcie (2,1) jest problemem minimalnej bisekcji i jest NP-zupełne. Następnie oceniamy problem trzech partycji, w którym n  = 3 k , który jest również ograniczony w czasie wielomianowym. Teraz, jeśli założymy, że mamy algorytm aproksymacji skończonej dla ( k , 1)-zrównoważonego podziału, to albo instancja z trzema partycjami może być rozwiązana przy użyciu zrównoważonego ( k ,1) podziału w G, albo nie może być rozwiązana. Jeśli wystąpienie 3-partycjonowania może zostać rozwiązane, to ( k , 1)-zrównoważony problem partycjonowania w G może zostać rozwiązany bez obcinania krawędzi. W przeciwnym razie, jeśli nie można rozwiązać wystąpienia 3-partycjonowania, optymalnie ( k , 1) zrównoważone partycjonowanie w G spowoduje wycięcie co najmniej jednej krawędzi. Algorytm aproksymacyjny ze skończonym współczynnikiem aproksymacji musi rozróżniać te dwa przypadki. W związku z tym może rozwiązać problem trzech podziałów, który jest sprzecznością przy założeniu, że P  =  NP . Zatem jest oczywiste, że ( k ,1)-zrównoważony problem partycjonowania nie ma algorytmu aproksymacji wielomianowej ze skończonym współczynnikiem aproksymacji, chyba że P  =  NP .

Te płaskie separatora twierdzenie stanowi, że każdy n -Vertex płaska wykres może być podzielona w przybliżeniu równe części usunięciu O ( √ n ) wierzchołków. Nie jest to przegroda w sensie opisanym powyżej, ponieważ zestaw przegród składa się z wierzchołków, a nie z krawędzi. Jednak ten sam wynik sugeruje również, że każdy płaski graf 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, lokalna i globalna. Znane metody lokalne są Kernighan-Lin algorytm i Fiduccia-Mattheyses algorytmy , które były pierwszymi skutecznymi 2-drożne cięć według lokalnych strategii wyszukiwania. Ich główną wadą jest arbitralny początkowy podział zbioru wierzchołków, który może wpłynąć na końcową jakość rozwiązania. Podejścia globalne opierają się na właściwościach całego grafu i nie polegają na dowolnym początkowym podziale. Najczęstszym przykładem jest podział widmowy, w którym podział pochodzi z przybliżonych wektorów własnych macierzy sąsiedztwa lub grupowanie widmowe, które grupuje wierzchołki grafu przy użyciu rozkładu własnego macierzy Laplace'a grafu .

Metody wielopoziomowe

Algorytm partycjonowania wykresu wielopoziomowego działa przez zastosowanie jednego lub więcej etapów. Każdy etap zmniejsza rozmiar wykresu poprzez zwijanie wierzchołków i krawędzi, dzieli mniejszy wykres, a następnie odwzorowuje i poprawia ten podział oryginalnego wykresu. W ramach ogólnego schematu wielopoziomowego można zastosować szeroką gamę metod partycjonowania i udoskonalania. W wielu przypadkach takie podejście może dać zarówno szybkie czasy realizacji, jak i bardzo wysoką jakość wyników. Jednym z powszechnie stosowanych przykładów takiego podejścia jest METIS , partycjonujący grafy i hMETIS, odpowiadający mu partycjonujący hipergrafy. Alternatywnym podejściem pochodzi z i realizowane, na przykład, w scikit-learn jest widmową klastrów z podziałem ustalonej z wektorów własnych o wykres Laplace'a matrycy do pierwotnego wykres obliczonej przez LOBPCG Solver z multigrid wstępnego kondycjonowania .

Podział spektralny i bisekcja spektralna

Biorąc pod uwagę wykres z matrycy przylegania , gdzie pozycja implikuje krawędź między węzłem i i matrycę stopnia , która jest macierzą diagonalną, której każdy ukośne wprowadzenie rzędu , reprezentuje poziom węzła węzła . Laplace'a matrycę określa się jako . Teraz podział na wykres jest zdefiniowany jako podział na rozłączny i , minimalizując stosunek ${\ Displaystyle G = (V, E)}$ ${\ Displaystyle A}$${\ Displaystyle A_ {ij}}$${\displaystyle i}$${\displaystyle j}$ ${\ Displaystyle D}$${\displaystyle i}$${\displaystyle d_{ii}}$${\displaystyle i}$ ${\ Displaystyle L}$${\ Displaystyle L = DA}$${\ Displaystyle G = (V, E)}$${\ Displaystyle V}$${\ Displaystyle U}$${\ Displaystyle W}$

${\ Displaystyle {\ Frac {| E (G) \ czapka (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ł grafu widmowego można uzasadnić analogicznie do podziału drgającej struny lub układu masa-sprężyna i podobnie rozszerzyć na przypadek ujemnych wag grafu.

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

W takim scenariuszu druga najmniejsza wartość własna ( ) z , daje dolną granicę kosztu optymalnego ( ) podziału przy redukcji współczynnika z . Wektor własny ( ) odpowiadający , zwany wektorem Fiedlera , dzieli graf na dwie społeczności w oparciu o znak odpowiedniego wpisu wektora . Podział na większą liczbę zbiorowisk można osiągnąć poprzez wielokrotną bisekcję lub przy użyciu wielu wektorów własnych odpowiadających najmniejszym wartościom własnym. Przykłady na rysunkach 1, 2 ilustrują podejście dwusekcji spektralnej. ${\ Displaystyle \ lambda _ {2}}$${\ Displaystyle L}$${\displaystyle c}$${\ Displaystyle c \ geq {\ Frac {\ lambda _ {2}} {n}}}$${\displaystyle V_{2}}$${\ Displaystyle \ lambda _ {2}}$

Rysunek 1: Wykres G  = (5,4) jest analizowany dla dwusekcji spektralnej. Liniowa kombinacja najmniejszych dwóch wektorów własnych prowadzi do [1 1 1 1 1]' o wartości własnej = 0.

Rysunek 2: Wykres G  = (5,5) ilustruje, że wektor Fiedlera zaznaczony na czerwono dzieli wykres na dwie zbiorowiska, jedna z wierzchołkami {1,2,3} z dodatnimi wpisami w przestrzeni wektorowej, a druga zbiorowość ma wierzchołki {4,5} z ujemnymi wpisami w przestrzeni wektorowej.

Modułowość i cięcie proporcjonalne

Jednak partycjonowanie przy minimalnym cięciu nie powiedzie się, gdy liczba społeczności do partycjonowania lub rozmiary partycji są nieznane. Na przykład optymalizacja rozmiaru cięcia dla wolnych rozmiarów grup powoduje umieszczenie wszystkich wierzchołków w tej samej społeczności. Ponadto minimalizowanie rozmiaru cięcia może być niewłaściwe, ponieważ dobry podział to nie tylko taki, który ma małą liczbę krawędzi między społecznościami. To motywowało użycie modułowości (Q) jako metryki do optymalizacji zrównoważonego podziału wykresu. Przykład na rysunku 3 ilustruje 2 wystąpienia tego samego wykresu, tak że w (a) modularność (Q) jest metryką podziału, a w (b) ratio-cut jest metryką podziału.

Rysunek 3: Wykres ważony G może być podzielony w celu maksymalizacji Q w (a) lub w celu zminimalizowania redukcji współczynnika w (b). Widzimy, że (a) jest lepiej zrównoważonym podziałem, co motywuje wagę modularności w problemach z partycjonowaniem grafów.

Aplikacje

Przewodnictwo

Innym celem funkcja służy do podziału wykresu przewodności , który jest stosunkiem między liczbą krawędzi tnących i objętości najmniejszej części. Przewodnictwo jest związane z przepływami elektrycznymi i spacerami losowymi. Cheeger związany gwarancje, że widmowa bisekcji zapewnia partycje z prawie optymalnej przewodności. 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 łączy, które powinny być uodpornione w celu powstrzymania epidemii.

Inne metody podziału grafów

Modele spinowe zostały wykorzystane do grupowania danych wielowymiarowych, w których podobieństwa są przekładane na siłę sprzężenia. Właściwości konfiguracji spinu stanu podstawowego można bezpośrednio interpretować jako zbiorowiska. W ten sposób graf jest podzielony na partycje, aby zminimalizować hamiltonian grafu podzielonego na partycje. Hamiltona (H) jest uzyskiwane przez przyporządkowanie następujące korzyści działowych i kar.

• Nagradzaj wewnętrzne krawędzie między węzłami tej samej grupy (ten sam spin)
• Kara za brakujące krawędzie w tej samej grupie
• Ukarać istniejące krawędzie między różnymi grupami
• Nagradzaj niepowiązania między różnymi grupami.

Dodatkowo klastrowanie widmowe oparte na jądrze PCA przybiera formę struktury najmniejszych kwadratów maszyny wektorów wsparcia, dzięki czemu możliwe staje się rzutowanie wpisów danych na przestrzeń cech wywołaną jądrem, która ma maksymalną wariancję, co oznacza wysoką separację między projektowanymi społecznościami .

Niektóre metody wyrażają partycjonowanie grafów 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 wyborze partycji.

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

Narzędzia programowe

Scikit-learn narzędzi widmowa klastrów z podziałem określone z wektorów własnych o wykres Laplace'a matrycy do pierwotnego wykres obliczonej przez ARPACK lub przez LOBPCG Solver z multigrid wstępnego kondycjonowania .

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

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

PaToH to kolejny program do partycjonowania hipergrafów.

KaHyPar to wielopoziomowa struktura partycjonowania hipergrafów zapewniająca algorytmy partycjonowania oparte na bezpośrednim k-way i rekurencyjnej bisekcji. Przedstawia podejście wielopoziomowe w jego najbardziej ekstremalnej wersji, usuwając tylko jeden wierzchołek na każdym poziomie hierarchii. Korzystając z tego bardzo drobnoziarnistego podejścia n- poziomowego w połączeniu z silną lokalną heurystyką wyszukiwania, oblicza rozwiązania o bardzo wysokiej jakości.

Scotch to framework do partycjonowania grafów stworzony przez Pellegrini. Wykorzystuje rekurencyjną dwupoziomową bisekcję i obejmuje techniki partycjonowania sekwencyjnego i równoległego.

Jostle to solwer do sekwencyjnego i równoległego partycjonowania grafów opracowany przez Chrisa Walshawa. Komercyjna wersja tego partycjonatora jest znana jako NetWorks.

Party implementuje framework zoptymalizowany 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 pogrubiania i rozwiązywania układów liniowych powstających w podejściu dyfuzyjnym.

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

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

Lista darmowych frameworków open-source:

Bibliografia

Zewnętrzne linki

• Chamberlain, Bradford L. (1998). „Algorytmy partycjonowania wykresów do dystrybucji obciążeń obliczeń równoległych”

Bibliografia

• Bichot, Charles-Edmond; Siarry, Patryk (2011). Partycjonowanie wykresów: optymalizacja i aplikacje . ISTE – Wiley. P. 384. Numer ISBN 978-1848212336.
• Feldmann, Andreas Emil (2012). Zrównoważone partycjonowanie siatek i powiązanych wykresów: teoretyczne badanie dystrybucji danych w symulacjach równoległych modeli elementów skończonych . Getynga, Niemcy: Cuvillier Verlag. P. 218. ISBN 978-3954041251. Wyczerpująca analiza problemu z teoretycznego punktu widzenia.
• Kernighana, BW; Lin, S. (1970). „Efektywna procedura heurystyczna dla grafów partycjonowania” (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ść wynosi O(n ² ), więc nie jest już powszechnie stosowana.
• Fiduccia CM; Mateusz, RM (1982). Heurystyka czasu liniowego do ulepszania partycji sieciowych . Konferencja Automatyki Projektowania. doi : 10.1109/DAC.1982.1585498 . Późniejszy wariant, który jest czasem liniowym, bardzo często używany, zarówno sam, jak i jako część partycjonowania wielopoziomowego, patrz poniżej.
• Karypis, G.; Kumar, V. (1999). „Szybki i wysokiej jakości wielopoziomowy schemat partycjonowania nieregularnych wykresów” . SIAM Journal on Scientific Computing . Partycjonowanie wielopoziomowe to obecny stan wiedzy. Artykuł ten zawiera również dobre wyjaśnienia wielu innych metod oraz porównania różnych metod dotyczących szerokiej gamy problemów.
• Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S. (marzec 1999). „Wielopoziomowe partycjonowanie hipergrafów: aplikacje w domenie VLSI”. Transakcje IEEE w systemach VLSI (Very Large Scale Integration) . 7 (1): 69–79. CiteSeerX  10.1.1.553.2367 . doi : 10.1109/92.748202 . Partycjonowanie grafów (w szczególności partycjonowanie hipergrafów) ma wiele zastosowań w projektowaniu układów scalonych.
• Kirkpatrick, S.; Gelatt, CD, Jr.; Vecchi, MP (13 maja 1983). „Optymalizacja przez symulowane wyżarzanie”. Nauka . 220 (4598): 671-680. Kod 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 spektralne do podziału na proporcje i grupowania”. Transakcje IEEE dotyczące komputerowego wspomagania projektowania układów i systemów scalonych . 11 (9): 1074-1085. doi : 10.1109/43.159993 .. Istnieje cała klasa metod podziału widmowego , które wykorzystują wektory własne laplace'a grafu łączności. Możesz zobaczyć demo tego , używając Matlaba.