Particionisanje grafa

S Vikipedije, slobodne enciklopedije

U matematici, problem particionisanja grafa je definisan na osnovu podataka predstavljenih u obliku grafa G = (V,E), gde V predstavlja grane grafa a E čvorove, tako da je moguće particionisanje grafa na manje komponente sa specifičnim osobinama. Na primer, k-točlano particionisanje deli grane na k manjih delova. Dobro particionisanje grafa je ono kada je broj čvorova koji se nalaze između odvojenih komponenti mali. Particionisanje homogenog grafa, je vrsta particionisanja grafa, koja se sastoji od problema deljenja grafa na komponente, tako da su komponente iste veličine i da postoji povezanost između komponenti. Podela(particionisanje) grafova ima važnu ulogu u naučnom računanju, podeli različitih faza u VLSI dizajnu strujnih kola i podeli poslova u više-procesorskom sistemu.[1] U skorije vreme, problem podele grafa je dobilo na značenju zbog njegove uloge u grupisanju i otkrivanju grupe ljudi u društvenim, patološkim i biološkim mrežama. Buluc et al. 2013.[2]

Kompleksnost problema[uredi | uredi izvor]

Uglavnom, problem podele grafa spada pod kategoriju NP-teških problema. Rešenja ovih problema su uglavnom izvedena pomoću heuristike i aproksimirajućih algoritama.[3] Međutim, može se pokazati da homogeno particionisanje grafa spada pod NP-kompletne probleme.[1] Čak i za posebne klase grafova kao što su stabla i mreže, ne postoje validni algoritmi,[4] sem P=NP. Mreže su posebno zanimljiv slučaj, pošto su model grafova koje proizilaze iz simulacija metode konačnih elemenata. Kada nije samo broj grana između komponenti određen, ali takođe i veličina komponenti, može se pokazati da ne postoje validni polinomijalni algoritmi za ovakve grafove.[4]

Problem[uredi | uredi izvor]

Posmatrajmo graf G = (V, E), gde je V broj grana, a E broj čvorova. Za problem ravnomerne podele (k,v), cilj je da se podeli graf G na k delova veličine v·(n/k), dok se umanjuje broj čvorova [1]. Takođe, dati graf i broj k > 1, podela V u k delova V1, V2, .. Vk tako da su delovi odvojeni i imaju istu veličinu, isti broj čvorova sa krajevima koji su u različitim delovima minimalizovni.

Zajedničko proširenje je hipergraf, gde čvor može da sadrži dve grane. Hipergraf se ne seče ako su sve grane u jednoj particiji, presečene tačno jedanput, bez obzira na broj grana sa obe strane.

Analiza[uredi | uredi izvor]

Za specifičan (k, 1 + ε) balansiran problem particionisanja, tragamo za najmanjom cenom particionisanja grafa G na k delova, tako da svaki deo sadrži maksimum (1 + ε)·(n/k)) čvorova. Poredimo cenu ovog algoritma sa cenom (k,1) sečenja, gde se u svakoj k komponenti mora naći tačno ista veličina od (n/k) čvorova, stoga je ovo više ograničen algoritam.

Već znamo da (2,1) presek NP kompletan. [5] Sledeće ćemo proceniti troparcijalan problem gde je n = 3k, koji je takođe polinomijalne složenosti.[1] Sada, ako pretpostavimo da imamo konačnu aproksimaciju algoritma za (k, 1) ravnomernu particiju, ili troparcijalna instanca se može rešiti pomoću ravnomernog (k,1) particionisanja u grafu ili se ne može rešiti. Ako se troparcijalna instanca može rešiti, onda problem (k, 1) ravnomernog particionisanja u grafu se može rešiti bez sečenja bilo koje grane. Inače, ako se troparcijalna instanca ne može rešiti, optimalno (k, 1) ravnomerno particionisanje u grafu će iseći barem jednu granu. Aproksimacioni algoritam sa konačnim aproksimacionim faktorom treba da diferencira između ova dva slučaja. Stoga, može da reši troparcijalan problem, koji je u kontradikciji sa pretpostavkom P = NP. Očigledno je da (k,1) ravnomerno particionisanje nema algoritam koji se može rešiti u polinomijalnom vremenu sa konačnom aproksimacijom faktora, osim P = NP.[1]

Teorema o planarnosti grafova tvrdi da bilo koji planarni graf sa n grana, može biti particionisan u iste delove, uklanjanjem O(√n) grana. Ovo nije particionisanje u tom smislu, zato što se particionisan skup sastoji od grana, a ne od čvorova.

Međutim, to isto govori da svaki planaran graf ograničenog stepena ima i izbalansiran deo sa O(√n) čvorova.

Metode particionisanja grafa[uredi | uredi izvor]

S obzirom da je particionisanje grafa težak problem, praktična rešenja su bazirana na heuristikama. Postoje dve kategorije metoda, lokalne i globalne. Dobro poznate lokalne metode su Kernighan–Lin algoritam, i Fiduccia-Mattheyses algoritmi, koji su bili prvi algoritmi koji su radili dvorsmerne rezove. Globalni pristup zavisi od svojstva celog grafa i ne zavisi od proizvoljnosti početnog particionisanja. Najčešći primer je spektralno particionisanje, gde je particionisanje izvedeno iz matrice povezanosti.

Višeslojne metode[uredi | uredi izvor]

Algoritam za particionisanje višeslojnog grafa, radi tako što se primeni više faza. U svakoj fazi smanjuje se veličina grafa, urušavanjem grana i čvorova, particija manjeg grafa, zatim se vraća nazad prerađuje tu particiju originalnog grafa.[6] Širok spektar particionisanja i prerađivačkih metoda se mogu primeniti u okviru šeme višeg nivoa. U velikom broju slučajeva, ovaj pristup može da za kratko vreme izvršavanja da tačne rezultate. Jedan od veoma čestih primera takvog pristupa je METIS,[7] za particionisanje grafa i hMetis, za particionisanje homogenog grafa.[8]

Spektralno particionisanje i spektralna podela intervala[uredi | uredi izvor]

Dat je graf sa matricom povezanosti A, gde Aij predstavlja granu između čvora i i čvora j, i matrica stepena D, koja je dijagonalna matrica, gde svaka vrednost dijagonale u koloni i, dii, predstavlja stepen čvora i. Laplasova matrica L = D − A. Sada odnos particija grafa G = (V, E) je definisana kao particija od V u odvojenom U, i W tako da je cena preseka (U,W)/(|U|·|W|) minimalna.

U takvom slučaju, druga najmanja sopstvena vrednost (λ) iz L, daje donju granicu na optimalnu cenu (s) odnosa particije sa c ≥ λ/n. Sopstvena vrednost (V) koja odgovara λ, se naziva Fidlerov vektor, koji polovi interval grafa na dva dela zasnovanih na znaku odgovarajućih ulaznih vektora. Podela na veći broj zajednica se obično postiže ponavljanjem polovljenja intervala, ali ovo ne daje zadovoljavajuće rezultate. Primeri na slikama 1,2 ilustruju pristup spektralne podele intervala.

Slika 1: Graf G = (5,4) je analiziran za spektralno polovljenje intervala. Linearna kombinacija najmanja dva sopstvena vektora vodi do [1 1 1 1 1]' imajući sopstvenu vrednost = 0.
Slika 2: Graf G = (5,5) ilustruje da Fidlerov vektor polovi intervale grafa na dve zajednice, jedna sa temenima {1,2,3} i pozitivnim ulaznim vrednostima, i druga zajednica sa temenima {4,5} i negativnim ulaznim vrednostima.

Minimalni rez particionisanja ne valja kada je broj zajednica, koje trebaju da budu particionisane, ili veličina particije, nepoznat. Na primer, optimizujući veličinu reza za slobodne veličine zajednica, stavlja sve grane u jednu zajednicu. Dodatno, veličina reza bi mogla da bude pogrešna stvar za minimalizaciju, pošto dobra podela, nije samo jedna zajednica sa malim brojem čvorova između zajednica. Ovo je motivisalo korišćenje Modularnosti (Q) [9] kao metrične za optimizaciju balansirane particije grafa. Primer na slici 3 ilustruje dve instance istog grafa takve da u (a) modularnost (Q) je metrička particija i u (b). Međutim, dobro je poznato da Q trpi ograničenje, proizvodi nepouzdane rezultate kada se radi sa malim zajednicama.

U ovom kontekstu, Surprise [10] je predložen kao alternativni pristup za procenu kvaliteta particije.

Figure 3: Težinski graf G može biti particionisan tako da uveća Q iz (a) ili umanji odnos u (b). Vidimo da je (a) bolje balansirana particija, ukazujući na važnost modularnosti problema particionisanja grafa.

Druge metode particionisanja grafa[uredi | uredi izvor]

Spin model se koristi za grupisanje viševarijativnih podataka, gde su sličnosti translirane u coupling strengths[11] . Osobine osnovnog stanja spin konfiguracije se može interpretirati kao zajednica. Stoga, graf je particionisan da minimizira Hamiltonijan particionisanog grafa.Hamiltonijan (H) je izveden dodeljivanjem sledećih nagrada za particionisanje i kazni.

  • Nagrade unutrašnje ivice između čvorova istih grupa (isti spin)
  • Kazne nestale ivice u istoj grupi
  • Kazne postojeće ivice između različitih grupa
  • Nagrade nepostojeće veze između različitih grupa

Neke metode izražavaju particionisanje grafa kao višekriterijumski optimizacioni problem koji se može rešiti korišćenjem metoda izraženih u igri teoretskog okvira gde svaki čvor donosi odluku o podeli koju sam odabere.[12]

Softverski alati[uredi | uredi izvor]

Čako,[13] zbog Hendriksona i Lelanda, implementira pristup više nivoa koji je gore izdvojen i osnovne lokalne potrage algoritma. Implementiraju i spektralne tehnike za podelu.

METIS[7] je skup podela grafova Karipisa i Kumara. U ovom skupu kMetis ima za cilj veću brzinu podele, hMetis,[8] se primenjuje na homogene grafove i ima za cilj kvalitet podela, i ParMetis[7] koji je paralelna implementacija grafikona podela Metis grafa.

PaToH[14] je još jedan delilac homogenih grafova.

Skoč je[15] okvir podele grafova Pelegrina. Koristi rekurzivne višeslojne podele intervala i uključuje sekvencijalne kao i paralelne tehnike particionisanja.

Jostle[16] je sekvencijalni i paralelni rešavač, kojeg je razvio Kris Valšav. Komercijalizovana verzija ovog rešavača je NetVorks.

Parti[17] implementira Bubble/shape – optimizovan okvir i Helpful Sets algoritme.

Softverski paket DibaP[18] i njegov MPI-paralelna varijanta PDibaP[19] koje je razvio Mejerhenk implementira Babl okvir koristeći difuziju; DibaP takođe koristi i AMG-zasnovane tehnike i rešavanje linearnh sistema koji proizilaze iz difuzionog pristupa.

Sanders i Šulc su objavili paket KaHIP[20] (Karlsruhe High Quality Particioning) koji implementira na primer metode protoka na bazi, više-lokalizovane lokalne pretrage i nekoliko paralelnih i sekvencijalnih meta-heurističnih. Alati Parkway[21] od Trifunovića i Knotenbelta poznati kao Zoltan[22] od Deviana se fokusiraju na particionisanje homogenog grafa.

Lista slobodnih okruženja otvorenog koda:

Ime Licence Kratak opis
Chaco GPL softverski paket koji implementira spektralne tehnike i višeslojni pristup
DiBaP * particionisanje grafa bazirano na višeslojnim tehnikama
Jostle * tehnike višeslojnog particionisanja
KaHIP GPL nekoliko paralelnih i sekvencijalnih meta-heuristika - garantuju balansiranje
kMetis Apache 2.0 Paket particionisanja grafa baziran na višeslojnim tehnikama, i k-put lokalne pretrage
Mondriaan LGPL Matrica particionisanja za particionisanje kvadratnih retkih matrica
PaToH BSD Particionisanje višeslojnih hipergrafova
Parkway * Paralelno particionisanje višeslojnih hipergrafova
Scotch CeCILL-C Implementira višeslojnu rekurzivnu podelu intervala
Zoltan BSD Particionisanje hipergrafova

Reference[uredi | uredi izvor]

  1. ^ a b v g d Andreev, Konstantin & Räcke, Harald, (2004). „Balanced Graph Partitioning”. Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. Barcelona, Spain: 120—124. ISBN 978-1-58113-840-5. doi:10.1145/1007912.1007931. 
  2. ^ Buluc, Aydin; Meyerhenke, Henning; Safro, Ilya; Sanders, Peter; Schulz, Christian (2013). Recent Advances in Graph Partitioning. arXiv:1311.3144 Slobodan pristup. 
  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. Paris, France: 100—111. 
  4. ^ 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. Bratislava, Slovakia. 
  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. str. 28. 
  7. ^ a b v Karypis, G. & Kumar, V. (1999). „A fast and high quality multilevel scheme for partitioning irregular graphs”. SIAM Journal on Scientific Computing. 20 (1): 359. doi:10.1137/S1064827595287997. 
  8. ^ a b Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. str. 526—529. 
  9. ^ Newman, M. E. J. (2006). „Modularity and community structure in networks”. PNAS. 103 (23): 8577—8696. PMC 1482622 Slobodan pristup. PMID 16723398. doi:10.1073/pnas.0601602103. 
  10. ^ Aldecoa, Rodrigo & Ignacio Marín (2011). „Deciphering network community structure by Surprise”. PLoS ONE. 6 (9): e24195. PMC 3164713 Slobodan pristup. PMID 21909420. doi:10.1371/journal.pone.0024195. 
  11. ^ Reichardt, Jörg & Bornholdt, Stefan (jul 2006). „Statistical mechanics of community detection”. Phys. Rev. E. 74 (1): 016110. doi:10.1103/PhysRevE.74.016110. 
  12. ^ Kurve, Griffin, Kesidis (2011) "A graph partitioning game for distributed simulation of networks" Proceedings of the 2011 International Workshop on Modeling, Analysis, and Control of Complex Networks: 9 -16
  13. ^ Bruce Hendrickson. „Chaco: Software for Partitioning Graphs”. 
  14. ^ Catalyürek, Ü. & Aykanat, C. (2011). PaToH: Partitioning Tool for Hypergraphs. 
  15. ^ Chevalier, C. & Pellegrini, F. (2008). „PT-Scotch: A Tool for Efficient Parallel Graph Ordering”. Parallel Computing. 34 (6): 318—331. doi:10.1016/j.parco.2007.12.001. 
  16. ^ Walshaw, C. & Cross, M. (2000). „Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm”. Journal on Scientific Computing. 22 (1): 63—80. doi:10.1137/s1064827598337373. 
  17. ^ R. Diekmann, R. Preis, F. Schlimbach and C. Walshaw (2000). „Shape-optimized Mesh Partitioning and Load Balancing for Parallel Adaptive FEM”. Parallel Computing. 26 (12): 1555—1581. doi:10.1016/s0167-8191(00)00043-0. 
  18. ^ H. Meyerhenke and B. Monien and T. Sauerwald (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. 
  19. ^ H. Meyerhenke (2013). Shape Optimizing Load Balancing for MPI-Parallel Adaptive Numerical Simulations. 10th DIMACS Implementation Challenge on Graph Partitioning and Graph Clustering. str. 67—82. 
  20. ^ P. Sanders; C. Schulz (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceeings of the 19th European Symposium on Algorithms (ESA). 6942. str. 469—480. 
  21. ^ Trifunovic, A. & Knottenbelt, W. J. (2008). „Parallel Multilevel Algorithms for Hypergraph Partitioning”. Journal of Parallel and Distributed Computing. 68 (5): 563—581. doi:10.1016/j.jpdc.2007.11.002. 
  22. ^ K. Devine and E. Boman and R. Heaphy and R. Bisseling and Ü. Catalyurek (2006). Parallel Hypergraph Partitioning for Scientific Computing. Proceedings of the 20th International Conference on Parallel and Distributed Processing. str. 124—124. 

Literatura[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Партиционисање_графа&oldid=26970713”