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

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

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

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

Проблем

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

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

Анализа

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

$\underset{i}{\max }|V_i|\le (1+\epsilon )\lceil \frac{|V|}{k}\rceil .$

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

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

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

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

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

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

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

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

Дат је граф са матрицом повезаности А, где A_ij представља грану између чвора i и чвора j, и матрица степена D, која је дијагонална матрица, где свака вредност дијагонале у колони i, d_ii, представља степен чвора 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) као метричне за оптимизацију балансиране партиције графа. Пример на слици 3 илуструје две инстанце истог графа такве да у (а) модуларност (Q) је метричка партиција и у (b). Међутим, добро је познато да Q трпи ограничење, производи непоуздане резултате када се ради са малим заједницама.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Cite bookШаблон:Мртва веза
• Шаблон:Cite bookИсцрпна анализа проблема из теоријског аспекта.
• Шаблон:Cite journal Један од фундаменталних радова из области. Какогод, слозеност је O(n²), тако да више није у честој употреби.
• Шаблон:Cite conference Каснија варијанта је у линеарном времену, јако често коришћена, обе самостално, и као део вишеслојног партиционисања.
• Шаблон:Cite journal
• Шаблон:Cite journal Партиционисање графа(и конкретније, партиционисање хиперграфа) има много апликација у дизајну електричних кола.
• Шаблон:Cite journal
• Шаблон:Cite journal. Постоји цела класа метода спектралног партиционисања, које користе сопствене векторе Лапласовог графа повезаности. Можете видети демо, користећи Matlab.

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

• Chamberlain, Bradford L. (1998). "Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations"Шаблон:Мртва веза