Википедија

Партиционисање графа

У математици, проблем партиционисања графа је дефинисан на основу података представљених у облику графа G = (V,E), где V представља гране графа а E чворове, тако да је могуће партиционисање графа на мање компоненте са специфичним особинама. На пример, к-точлано партиционисање дели гране на k мањих делова. Добро партиционисање графа је оно када је број чворова који се налазе између одвојених компоненти мали. Партиционисање хомогеног графа, је врста партиционисања графа, која се састоји од проблема дељења графа на компоненте, тако да су компоненте исте величине и да постоји повезаност између компоненти. Подела(партиционисање) графова има важну улогу у научном рачунању, подели различитих фаза у VLSI дизајну струјних кола и подели послова у више-процесорском систему.[1] У скорије време, проблем поделе графа је добило на значењу због његове улоге у груписању и откривању групе људи у друштвеним, патолошким и биолошким мрежама. Buluc et al. 2013.[2]

Комплексност проблема

уреди

Углавном, проблем поделе графа спада под категорију НП-тешких проблема. Решења ових проблема су углавном изведена помоћу хеуристике и апроксимирајућих алгоритама.[3] Међутим, може се показати да хомогено партиционисање графа спада под НП-комплетне проблеме.[1] Чак и за посебне класе графова као што су стабла и мреже, не постоје валидни алгоритми,[4] сем П=НП. Мреже су посебно занимљив случај, пошто су модел графова које произилазе из симулација методе коначних елемената. Када није само број грана између компоненти одређен, али такође и величина компоненти, може се показати да не постоје валидни полиномијални алгоритми за овакве графове.[4]

Проблем

уреди

Посматрајмо граф G = (V, E), где је V број грана, а E број чворова. За проблем равномерне поделе (k,v), циљ је да се подели граф G на k делова величине v·(n/k), док се умањује број чворова[1]. Такође, дати граф и број k > 1, подела V у k делова V1, V2, .. Vk тако да су делови одвојени и имају исту величину, исти број чворова са крајевима који су у различитим деловима минимализовни.

Заједничко проширење је хиперграф, где чвор може да садржи две гране. Хиперграф се не сече ако су све гране у једној партицији, пресечене тачно једанпут, без обзира на број грана са обе стране.

Анализа

уреди

За специфичан (k, 1 + ε) балансиран проблем партиционисања, трагамо за најмањом ценом партиционисања графа G на k делова, тако да сваки део садржи максимум (1 + ε)·(n/k)) чворова. Поредимо цену овог алгоритма са ценом (k,1) сечења, где се у свакој k компоненти мора наћи тачно иста величина од (n/k) чворова, стога је ово више ограничен алгоритам.

 

Већ знамо да (2,1) пресек НП комплетан. [5] Следеће ћемо проценити тропарцијалан проблем где је n = 3k, који је такође полиномијалне сложености.[1] Сада, ако претпоставимо да имамо коначну апроксимацију алгоритма за (k, 1) равномерну партицију, или тропарцијална инстанца се може решити помоћу равномерног (k,1) партиционисања у графу или се не може решити. Ако се тропарцијална инстанца може решити, онда проблем (k, 1) равномерног партиционисања у графу се може решити без сечења било које гране. Иначе, ако се тропарцијална инстанца не може решити, оптимално (k, 1) равномерно партиционисање у графу ће исећи барем једну грану. Апроксимациони алгоритам са коначним апроксимационим фактором треба да диференцира између ова два случаја. Стога, може да реши тропарцијалан проблем, који је у контрадикцији са претпоставком П = НП. Очигледно је да (k,1) равномерно партиционисање нема алгоритам који се може решити у полиномијалном времену са коначном апроксимацијом фактора, осим П = НП.[1]

Теорема о планарности графова тврди да било који планарни граф са n грана, може бити партиционисан у исте делове, уклањањем O(√n) грана. Ово није партиционисање у том смислу, зато што се партиционисан скуп састоји од грана, а не од чворова.

Међутим, то исто говори да сваки планаран граф ограниченог степена има и избалансиран део са O(√n) чворова.

Методе партиционисања графа

уреди

С обзиром да је партиционисање графа тежак проблем, практична решења су базирана на хеуристикама. Постоје две категорије метода, локалне и глобалне. Добро познате локалне методе су Kernighan–Lin алгоритам, и Fiduccia-Mattheyses алгоритми, који су били први алгоритми који су радили дворсмерне резове. Глобални приступ зависи од својства целог графа и не зависи од произвољности почетног партиционисања. Најчешћи пример је спектрално партиционисање, где је партиционисање изведено из матрице повезаности.

Вишеслојне методе

уреди

Алгоритам за партиционисање вишеслојног графа, ради тако што се примени више фаза. У свакој фази смањује се величина графа, урушавањем грана и чворова, партиција мањег графа, затим се враћа назад прерађује ту партицију оригиналног графа.[6] Широк спектар партиционисања и прерађивачких метода се могу применити у оквиру шеме вишег нивоа. У великом броју случајева, овај приступ може да за кратко време извршавања да тачне резултате. Један од веома честих примера таквог приступа је МЕТИС,[7] за партиционисање графа и хМетис, за партиционисање хомогеног графа.[8]

Спектрално партиционисање и спектрална подела интервала

уреди

Дат је граф са матрицом повезаности А, где Aij представља грану између чвора i и чвора j, и матрица степена D, која је дијагонална матрица, где свака вредност дијагонале у колони i, dii, представља степен чвора i. Лапласова матрица L = D − A. Сада однос партиција графа G = (V, E) је дефинисана као партиција од V у одвојеном U, и W тако да је цена пресека (U,W)/(|U|·|W|) минимална.

У таквом случају, друга најмања сопствена вредност (λ) из L, даје доњу границу на оптималну цену (с) односа партиције са c ≥ λ/n. Сопствена вредност (V) која одговара λ, се назива Фидлеров вектор, који полови интервал графа на два дела заснованих на знаку одговарајућих улазних вектора. Подела на већи број заједница се обично постиже понављањем половљења интервала, али ово не даје задовољавајуће резултате. Примери на сликама 1,2 илуструју приступ спектралне поделе интервала.

 
Слика 1: Граф G = (5,4) је анализиран за спектрално половљење интервала. Линеарна комбинација најмања два сопствена вектора води до [1 1 1 1 1]' имајући сопствену вредност = 0.
 
Слика 2: Граф G = (5,5) илуструје да Фидлеров вектор полови интервале графа на две заједнице, једна са теменима {1,2,3} и позитивним улазним вредностима, и друга заједница са теменима {4,5} и негативним улазним вредностима.

Минимални рез партиционисања не ваља када је број заједница, које требају да буду партиционисане, или величина партиције, непознат. На пример, оптимизујући величину реза за слободне величине заједница, ставља све гране у једну заједницу. Додатно, величина реза би могла да буде погрешна ствар за минимализацију, пошто добра подела, није само једна заједница са малим бројем чворова између заједница. Ово је мотивисало коришћење Модуларности (Q)[9] као метричне за оптимизацију балансиране партиције графа. Пример на слици 3 илуструје две инстанце истог графа такве да у (а) модуларност (Q) је метричка партиција и у (b). Међутим, добро је познато да Q трпи ограничење, производи непоуздане резултате када се ради са малим заједницама.

У овом контексту, Surprise[10] је предложен као алтернативни приступ за процену квалитета партиције.

 
Figure 3: Тежински граф G може бити партиционисан тако да увећа Q из (a) или умањи однос у (b). Видимо да је (a) боље балансирана партиција, указујући на важност модуларности проблема партиционисања графа.

Друге методе партиционисања графа

уреди

Спин модел се користи за груписање вишеваријативних података, где су сличности транслиране у coupling strengths[11] . Особине основног стања spin конфигурације се може интерпретирати као заједница. Стога, граф је партиционисан да минимизира Хамилтонијан партиционисаног графа.Хамилтонијан (Х) је изведен додељивањем следећих награда за партиционисање и казни.

  • Награде унутрашње ивице између чворова истих група (исти спин)
  • Казне нестале ивице у истој групи
  • Казне постојеће ивице између различитих група
  • Награде непостојеће везе између различитих група

Неке методе изражавају партиционисање графа као вишекритеријумски оптимизациони проблем који се може решити коришћењем метода изражених у игри теоретског оквира где сваки чвор доноси одлуку о подели коју сам одабере.[12]

Софтверски алати

уреди

Чако,[13] због Хендриксона и Леланда, имплементира приступ више нивоа који је горе издвојен и основне локалне потраге алгоритма. Имплементирају и спектралне технике за поделу.

МЕТИС[7] је скуп подела графова Кариписа и Кумара. У овом скупу кМетис има за циљ већу брзину поделе, хМетис,[8] се примењује на хомогене графове и има за циљ квалитет подела, и ПарМетис[7] који је паралелна имплементација графикона подела Метис графа.

ПаТоХ[14] је још један делилац хомогених графова.

Скоч је[15] оквир поделе графова Пелегрина. Користи рекурзивне вишеслојне поделе интервала и укључује секвенцијалне као и паралелне технике партиционисања.

Јостле[16] је секвенцијални и паралелни решавач, којег је развио Крис Валшав. Комерцијализована верзија овог решавача је НетВоркс.

Парти[17] имплементира Bubble/shape – оптимизован оквир и Helpful Sets алгоритме.

Софтверски пакет DibaP[18] и његов MPI-паралелна варијанта PDibaP[19] које је развио Мејерхенк имплементира Бабл оквир користећи дифузију; DibaP такође користи и AMG-засноване технике и решавање линеарнх система који произилазе из дифузионог приступа.

Сандерс и Шулц су објавили пакет КаHIP[20] (Karlsruhe High Quality Particioning) који имплементира на пример методе протока на бази, више-локализоване локалне претраге и неколико паралелних и секвенцијалних мета-хеуристичних. Алати Parkway[21] од Трифуновића и Кнотенбелта познати као Золтан[22] од Девиана се фокусирају на партиционисање хомогеног графа.

Листа слободних окружења отвореног кода:

Име Лиценце Кратак опис
Chaco GPL софтверски пакет који имплементира спектралне технике и вишеслојни приступ
DiBaP * партиционисање графа базирано на вишеслојним техникама
Jostle * технике вишеслојног партиционисања
KaHIP GPL неколико паралелних и секвенцијалних мета-хеуристика - гарантују балансирање
kMetis Apache 2.0 Пакет партиционисања графа базиран на вишеслојним техникама, и к-пут локалне претраге
Mondriaan LGPL Матрица партиционисања за партиционисање квадратних ретких матрица
PaToH BSD Партиционисање вишеслојних хиперграфова
Parkway * Паралелно партиционисање вишеслојних хиперграфова
Scotch CeCILL-C Имплементира вишеслојну рекурзивну поделу интервала
Zoltan BSD Партиционисање хиперграфова

Референце

уреди
  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: 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  . 
  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. ^ а б 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. стр. 28. 
  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. doi:10.1137/S1064827595287997. 
  8. ^ а б Karypis, G. and Aggarwal, R. and Kumar, V., Shekhar, S. (1997). Multilevel hypergraph partitioning: application in VLSI domain. Proceedings of the 34th annual Design Automation Conference. стр. 526—529. 
  9. ^ Newman, M. E. J. (2006). „Modularity and community structure in networks”. PNAS. 103 (23): 8577—8696. PMC 1482622  . 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  . PMID 21909420. doi:10.1371/journal.pone.0024195. 
  11. ^ Reichardt, Jörg & Bornholdt, Stefan (јул 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. стр. 67—82. 
  20. ^ P. Sanders; C. Schulz (2011). Engineering Multilevel Graph Partitioning Algorithms. Proceeings of the 19th European Symposium on Algorithms (ESA). 6942. стр. 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. стр. 124—124. 

Литература

уреди

Спољашње везе

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