Разделение графа

Подразделение вершин на непересекающиеся множества

В математике разбиение графа — это сведение графа к меньшему графу путем разбиения его набора узлов на взаимоисключающие группы. Ребра исходного графа, которые пересекаются между группами, будут создавать ребра в разбиенном графе. Если количество результирующих ребер мало по сравнению с исходным графом, то разбиенный граф может лучше подходить для анализа и решения задач, чем исходный. Нахождение разбиения, которое упрощает анализ графа, является сложной задачей, но оно имеет приложения к научным вычислениям, проектированию схем VLSI и планированию задач на многопроцессорных компьютерах, среди прочего. ^[1] В последнее время проблема разбиения графа приобрела важность из-за ее применения для кластеризации и обнаружения клик в социальных, патологических и биологических сетях. Обзор последних тенденций в вычислительных методах и приложениях см. в работе Buluc et al. (2013). ^[2] Двумя распространенными примерами разбиения графа являются задачи минимального разреза и максимального разреза .

Сложность проблемы

Обычно задачи разбиения графа попадают в категорию NP-трудных задач. Решения этих задач обычно выводятся с использованием эвристик и алгоритмов аппроксимации. ^[3] Однако можно показать, что задача равномерного разбиения графа или сбалансированного разбиения графа является NP-полной для аппроксимации в пределах любого конечного множителя. ^[1] Даже для специальных классов графов, таких как деревья и сетки, не существует разумных алгоритмов аппроксимации, ^[4] если только P=NP . Сетки представляют собой особенно интересный случай, поскольку они моделируют графы, полученные в результате моделирования модели конечных элементов (FEM) . Когда аппроксимируется не только количество ребер между компонентами, но и размеры компонентов, можно показать, что для этих графов не существует разумных полностью полиномиальных алгоритмов. ^[4]

Проблема

Рассмотрим граф G = ( V , E ), где V обозначает множество из n вершин, а E — множество ребер. Для задачи сбалансированного разбиения ( k , v ) целью является разбиение G на k компонентов не более чем размером v · ( n / k ), при этом минимизируя емкость ребер между отдельными компонентами. ^[1] Также, учитывая G и целое число k > 1, разбейте V на k частей (подмножеств) V ₁ , V ₂ , ..., V _k таким образом, чтобы части были непересекающимися и имели одинаковый размер, а количество ребер с конечными точками в разных частях было минимизировано. Такие задачи разбиения обсуждались в литературе как подходы бикритериальной аппроксимации или увеличения ресурсов. Распространенным расширением является гиперграфы , где ребро может соединять более двух вершин. Гиперребро не разрезается, если все вершины находятся в одном разбиении, и разрезается ровно один раз в противном случае, независимо от того, сколько вершин находится на каждой стороне. Такое использование распространено в автоматизации электронного проектирования .

Анализ

Для конкретной ( k , 1 +  ε ) сбалансированной задачи разбиения мы стремимся найти минимальное по стоимости разбиение G на k компонентов, где каждый компонент содержит максимум (1 +  ε )·( n / k ) узлов. Мы сравниваем стоимость этого алгоритма приближения со стоимостью разреза ( k ,1), где каждый из k компонентов должен иметь одинаковый размер ( n / k ) узлов каждый, таким образом, являясь более ограниченной задачей. Таким образом,

${\displaystyle \max _{i}|V_{i}|\leq (1+\varepsilon )\left\lceil {\frac {|V|}{k}}\right\rceil .}$

Мы уже знаем, что разрез (2,1) является минимальной задачей деления пополам и является NP-полной. ^[5] Далее мы оцениваем задачу 3-разбиения, где n  = 3 k , которая также ограничена полиномиальным временем. ^[1] Теперь, если мы предположим, что у нас есть конечный алгоритм приближения для ( k , 1)-сбалансированного разбиения, то либо пример 3-разбиения может быть решен с использованием сбалансированного ( k , 1) разбиения в G, либо он не может быть решен. Если пример 3-разбиения может быть решен, то задача ( k , 1)-сбалансированного разбиения в G может быть решена без разрезания какого-либо ребра. В противном случае, если пример 3-разбиения не может быть решен, оптимальное ( k , 1)-сбалансированное разбиение в G разрежет по крайней мере одно ребро. Алгоритм приближения с конечным коэффициентом приближения должен различать эти два случая. Следовательно, он может решить задачу 3-разбиения, что является противоречием при предположении, что P  =  NP . Таким образом, очевидно, что ( k ,1)-сбалансированная задача разбиения не имеет полиномиального алгоритма аппроксимации с конечным коэффициентом аппроксимации, если только P  =  NP . ^[1]

Теорема о плоском разделителе утверждает, что любой n -вершинный планарный граф может быть разделен на примерно равные части путем удаления O( √ n ) вершин. Это не является разделением в описанном выше смысле, поскольку множество разделов состоит из вершин, а не ребер. Однако тот же результат также подразумевает, что каждый планарный граф ограниченной степени имеет сбалансированный разрез с O( √ n ) ребрами.

Методы разбиения графа

Поскольку разбиение графа является сложной задачей, практические решения основаны на эвристике. Существует две широкие категории методов: локальные и глобальные. Известные локальные методы — это алгоритм Кернигана–Лина и алгоритмы Фидуччи–Маттейсеса , которые были первыми эффективными двухсторонними разрезами с помощью стратегий локального поиска. Их основным недостатком является произвольное начальное разбиение множества вершин, что может повлиять на качество конечного решения. Глобальные подходы опираются на свойства всего графа и не опираются на произвольное начальное разбиение. Наиболее распространенным примером является спектральное разбиение, где разбиение выводится из приближенных собственных векторов матрицы смежности, или спектральная кластеризация , которая группирует вершины графа с помощью собственного разложения матрицы Лапласа графа .

Многоуровневые методы

Многоуровневый алгоритм разбиения графа работает, применяя один или несколько этапов. Каждый этап уменьшает размер графа, сворачивая вершины и ребра, разбивает меньший граф, затем отображает обратно и уточняет это разбиение исходного графа. ^[6] В общей многоуровневой схеме может применяться широкий спектр методов разбиения и уточнения. Во многих случаях этот подход может дать как быстрое время выполнения, так и очень качественные результаты. Одним из широко используемых примеров такого подхода является METIS , ^[7] разбиение графа, и hMETIS, соответствующий разбиение для гиперграфов. ^[8] Альтернативный подход, возникший из ^[9] и реализованный, например, в scikit-learn, представляет собой спектральную кластеризацию с разбиением, определенным из собственных векторов матрицы Лапласа графа для исходного графа, вычисленного решателем LOBPCG с многосеточным предобусловливанием .

Спектральное разбиение и спектральное деление пополам

Дан граф с матрицей смежности , где запись подразумевает ребро между узлом и , и матрицей степеней , которая является диагональной матрицей, где каждая диагональная запись строки , , представляет степень узла узла . Матрица Лапласа определяется как . Теперь разбиение с разрезом по отношению для графа определяется как разбиение на непересекающиеся , и , минимизирующее отношение ${\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=D-A}$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle W}$

${\displaystyle {\frac {|E(G)\cap (U\times W)|}{|U|\cdot |W|}}}$

числа ребер, которые фактически пересекают этот разрез, к числу пар вершин, которые могли бы поддерживать такие ребра. Спектральное разбиение графа может быть мотивировано ^[10] по аналогии с разбиением вибрирующей струны или системы масса-пружина и аналогичным образом распространено на случай отрицательных весов графа. ^[11]

Собственное значение и собственный вектор Фидлера

В таком сценарии второе наименьшее собственное значение ( ) из , дает нижнюю границу оптимальной стоимости ( ) разбиения с пропорциональным разрезом с . Собственный вектор ( ), соответствующий , называемый вектором Фидлера , делит граф пополам только на два сообщества на основе знака соответствующего элемента вектора . Разделение на большее количество сообществ может быть достигнуто путем повторного деления пополам или путем использования нескольких собственных векторов, соответствующих наименьшим собственным значениям. ^[12] Примеры на рисунках 1,2 иллюстрируют подход спектрального деления пополам. ${\displaystyle \lambda _{2}}$ ${\displaystyle L}$ ${\displaystyle c}$ ${\displaystyle c\geq {\frac {\lambda _{2}}{n}}}$ ${\displaystyle V_{2}}$ ${\displaystyle \lambda _{2}}$

Рисунок 1: Граф G  = (5,4) анализируется для спектральной бисекции. Линейная комбинация наименьших двух собственных векторов приводит к [1 1 1 1 1]', имеющему собственное значение = 0.

Рисунок 2: Граф G  = (5,5) иллюстрирует, что вектор Фидлера, выделенный красным цветом, делит граф на два сообщества, одно из которых имеет вершины {1,2,3} с положительными элементами векторного пространства, а другое сообщество имеет вершины {4,5} с отрицательными элементами векторного пространства.

Модульность и пропорциональный разрез

Однако разбиение по минимальному разрезу не работает, когда количество сообществ, которые необходимо разбить, или размеры разделов неизвестны. Например, оптимизация размера разреза для свободных размеров групп помещает все вершины в одно и то же сообщество. Кроме того, размер разреза может быть неправильным для минимизации, поскольку хорошее разделение — это не просто разделение с небольшим количеством ребер между сообществами. Это побудило использовать модульность (Q) ^[13] в качестве метрики для оптимизации сбалансированного разбиения графа. Пример на рисунке 3 иллюстрирует 2 экземпляра одного и того же графа, так что в (a) модульность (Q) является метрикой разбиения, а в (b) метрикой разбиения является отношение-разрезание.

Рисунок 3: Взвешенный граф G может быть разделен для максимизации Q в (a) или для минимизации разреза отношения в (b). Мы видим, что (a) является более сбалансированным разделением, тем самым мотивируя важность модульности в задачах разбиения графа.

Приложения

Проводимость

Другая целевая функция, используемая для разбиения графа, — это Проводимость , которая является отношением между количеством граней разреза и объемом наименьшей части. Проводимость связана с электрическими потоками и случайными блужданиями. Граница Чигера гарантирует, что спектральное бисекция обеспечивает разбиения с почти оптимальной проводимостью. Качество этого приближения зависит от второго наименьшего собственного значения лапласиана λ ₂ .

Иммунизация

Разделение графа может быть полезным для определения минимального набора узлов или связей, которые следует иммунизировать, чтобы остановить эпидемии. ^[14]

Другие методы разбиения графа

Спиновые модели использовались для кластеризации многомерных данных, в которых сходства переводятся в силу связи. ^[15] Свойства конфигурации спина основного состояния могут быть напрямую интерпретированы как сообщества. Таким образом, граф разделяется для минимизации гамильтониана разделенного графа. Гамильтониан (H) выводится путем назначения следующих вознаграждений и штрафов за разделение.

• Вознаграждение внутренних ребер между узлами одной группы (одинаковый спин)
• Штрафовать за отсутствующие края в одной группе
• Оштрафовать существующие границы между различными группами
• Поощряйте отсутствие связей между различными группами.

Кроме того, спектральная кластеризация на основе Kernel-PCA принимает форму фреймворка опорных векторных машин наименьших квадратов, и, следовательно, становится возможным проецировать записи данных в пространство признаков, индуцированное ядром, которое имеет максимальную дисперсию, что подразумевает высокое разделение между спроецированными сообществами. ^[16]

Некоторые методы выражают разбиение графа как многокритериальную задачу оптимизации, которая может быть решена с использованием локальных методов, выраженных в теоретико-игровой структуре, где каждый узел принимает решение о разбиении, которое он выбирает. ^[17]

Для очень крупномасштабных распределенных графов классические методы разбиения могут не применяться (например, спектральное разбиение, Metis ^[7] ), поскольку они требуют полного доступа к данным графа для выполнения глобальных операций. Для таких крупномасштабных сценариев распределенное разбиение графа используется для выполнения разбиения только через асинхронные локальные операции.

Программные инструменты

scikit-learn реализует спектральную кластеризацию с разбиением, определяемым из собственных векторов матрицы Лапласа графа для исходного графа, вычисленного с помощью ARPACK или решателя LOBPCG с многосеточным предобусловливанием . ^[9]

METIS ^[7] — семейство алгоритмов разбиения графов Кариписа и Кумара. В этом семействе алгоритмов kMetis нацелен на большую скорость разбиения, hMetis ^[8] применяется к гиперграфам и нацелен на качество разбиения, а ParMetis ^[7] — параллельная реализация алгоритма разбиения графов Metis.

KaHyPar ^{[18] [19] [20]} — это многоуровневая структура разбиения гиперграфа, предоставляющая прямые алгоритмы разбиения на основе k-way и рекурсивного деления пополам. Она реализует многоуровневый подход в его самой экстремальной версии, удаляя только одну вершину на каждом уровне иерархии. Используя этот очень мелкозернистый подход n -уровня в сочетании с сильной локальной эвристикой поиска, она вычисляет решения очень высокого качества.

Scotch ^[21] — это фреймворк для разбиения графов от Pellegrini. Он использует рекурсивную многоуровневую бисекцию и включает последовательные и параллельные методы разбиения.

Jostle ^[22] — это последовательный и параллельный решатель разбиения графа, разработанный Крисом Уолшоу. Коммерческая версия этого разбиения известна как NetWorks.

Party ^[23] реализует оптимизированную для пузырьков/форм структуру и алгоритм полезных наборов.

Пакеты программного обеспечения DibaP ^[24] и его параллельный MPI вариант PDibaP ^[25] от Мейерхенке реализуют структуру Bubble с использованием диффузии; DibaP также использует основанные на AMG методы для огрубления и решения линейных систем, возникающих при диффузионном подходе.

Сандерс и Шульц выпустили пакет для разбиения графов KaHIP ^[26] (Karlsruhe High Quality Partitioning), который реализует, например, методы, основанные на потоках, более локализованные локальные поиски и несколько параллельных и последовательных метаэвристик.

Инструменты Parkway ^[27] Трифуновича и Кноттенбельта, а также Zoltan ^[28] Девайна и др. фокусируются на разбиении гиперграфов.

Ссылки

1. Андреев, Константин; Раке, Харальд (2004). "Сбалансированное разбиение графа". Труды шестнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах . Барселона, Испания. стр. 120–124. CiteSeerX 10.1.1.417.8592 . doi :10.1145/1007912.1007931. ISBN  978-1-58113-840-5.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
2. Булук, Айдын; Мейерхенке, Хеннинг; Сафро, Илья; Сандерс, Питер ; Шульц, Кристиан (2013). «Последние достижения в области разбиения графов». arXiv : 1311.3144 [cs.DS].
3. Фельдманн, Андреас Эмиль; Фоскини, Лука (2012). «Сбалансированные разбиения деревьев и приложения». Труды 29-го Международного симпозиума по теоретическим аспектам компьютерной науки : 100–111.
4. Feldmann, Andreas Emil (2012). "Быстрое сбалансированное разбиение сложно, даже на сетках и деревьях". Труды 37-го Международного симпозиума по математическим основам компьютерных наук . arXiv : 1111.6745 . Bibcode : 2011arXiv1111.6745F.
5. Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и неподатливость: руководство по теории NP-полноты . WH Freeman & Co. ISBN 978-0-7167-1044-8.
6. Хендриксон, Б.; Леланд, Р. (1995). Многоуровневый алгоритм разбиения графов . Труды конференции ACM/IEEE 1995 года по суперкомпьютерам. ACM. стр. 28.
7. Карипис, Г.; Кумар, В. (1999). «Быстрая и высококачественная многоуровневая схема для разбиения нерегулярных графов». Журнал SIAM по научным вычислениям . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . doi :10.1137/S1064827595287997. S2CID  3628209. 
8. Карипис, Г.; Аггарвал, Р.; Кумар, В.; Шехар, С. (1997). Многоуровневое разбиение гиперграфа: применение в области СБИС . Труды 34-й ежегодной конференции по автоматизации проектирования. С. 526–529.
9. Князев, Эндрю В. (2006). Многомасштабное спектральное разбиение графа и сегментация изображения . Семинар по алгоритмам для современных массивных наборов данных Стэнфордского университета и Yahoo! Research.
10. J. Demmel, [1], CS267: Заметки к лекции 23, 9 апреля 1999 г., Разбиение графа, часть 2
11. Князев, Эндрю (2018). О спектральном разбиении знаковых графов . Восьмой семинар SIAM по комбинаторным научным вычислениям, CSC 2018, Берген, Норвегия, 6–8 июня. arXiv : 1701.01394 . doi : 10.1137/1.9781611975215.2 .
12. Наумов, М.; Мун, Т. (2016). «Параллельное разбиение спектрального графа». Технический отчет NVIDIA . nvr-2016-001.
13. Newman, MEJ (2006). «Модульность и структура сообщества в сетях». PNAS . 103 (23): 8577–8696. arXiv : physics/0602124 . Bibcode : 2006PNAS..103.8577N. doi : 10.1073/pnas.0601602103 . PMC 1482622. PMID  16723398 . 
14. Y. Chen, G. Paul, S. Havlin, F. Liljeros, HE Stanley (2009). «Поиск лучшей стратегии иммунизации». Phys. Rev. Lett . 101 (5): 058701. doi :10.1103/PhysRevLett.101.058701. PMID  18764435.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
15. Райхардт, Йорг; Борнхольдт, Стефан (июль 2006 г.). "Статистическая механика обнаружения сообществ". Phys. Rev. E . 74 (1): 016110. arXiv : cond-mat/0603718 . Bibcode :2006PhRvE..74a6110R. doi :10.1103/PhysRevE.74.016110. PMID  16907154. S2CID  792965.
16. Alzate, Carlos; Suykens, Johan AK (2010). «Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA». Труды IEEE по анализу шаблонов и машинному интеллекту . 32 (2): 335–347. doi :10.1109/TPAMI.2008.292. ISSN  0162-8828. PMID  20075462. S2CID  200488.
17. Курве, А.; Гриффин, К.; Кесидис Г. (2011) «Игра с разбиением графа для распределенного моделирования сетей», Труды Международного семинара 2011 года по моделированию, анализу и управлению сложными сетями : 9–16
18. Шлаг, С.; Хенне, В.; Хойер, Т.; Мейерхенке, Х.; Сандерс, П.; Шульц, К. (2015-12-30). "K-way Hypergraph Partitioning via n-Level Recursive Bisection". Труды Восемнадцатого семинара по разработке алгоритмов и экспериментам (ALENEX) 2016 года . Общество промышленной и прикладной математики. стр. 53–67. arXiv : 1511.03137 . doi :10.1137/1.9781611974317.5. ISBN 978-1-61197-431-7. S2CID  1674598.
19. Ахремцев, Ю.; Хойер, Т.; Сандерс, П.; Шлаг, С. (2017-01-01). "Разработка прямого алгоритма разбиения гиперграфа k-way". Труды девятнадцатого семинара по разработке алгоритмов и экспериментам (ALENEX) 2017 г. Общество промышленной и прикладной математики. стр. 28–42. doi :10.1137/1.9781611974768.3. ISBN 978-1-61197-476-8.
20. Хойер, Тобиас; Шлаг, Себастьян (2017). «Улучшение схем огрубления для разбиения гиперграфа путем использования структуры сообщества». В Iliopoulos, Costas S.; Pissis, Solon P.; Puglisi, Simon J.; Raman, Rajeev (ред.). 16-й Международный симпозиум по экспериментальным алгоритмам (SEA 2017) . Leibniz International Proceedings in Informatics (LIPIcs). Том 75. Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. С. 21:1–21:19. doi : 10.4230/LIPIcs.SEA.2017.21 . ISBN 978-3-95977-036-1.
21. Шевалье, К.; Пеллегрини, Ф. (2008). «PT-Scotch: инструмент для эффективного параллельного упорядочения графов». Параллельные вычисления . 34 (6): 318–331. arXiv : 0907.1375 . doi : 10.1016/j.parco.2007.12.001. S2CID  10433524.
22. Уолшоу, К.; Кросс, М. (2000). «Разбиение сетки: многоуровневый алгоритм балансировки и уточнения». Журнал научных вычислений . 22 (1): 63–80. Bibcode : 2000SJSC...22...63W. CiteSeerX 10.1.1.19.1836 . doi : 10.1137/s1064827598337373. 
23. Diekmann, R.; Preis, R.; Schlimbach, F.; Walshaw, C. (2000). «Разбиение сетки с оптимизацией по форме и балансировка нагрузки для параллельного адаптивного метода конечных элементов». Параллельные вычисления . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . doi :10.1016/s0167-8191(00)00043-0. 
24. Мейерхенке, Х.; Моньен, Б.; Зауэрвальд, Т. (2008). «Новый многоуровневый алгоритм на основе диффузии для вычисления разделов графа». Журнал параллельных вычислений и распределенных вычислений . 69 (9): 750–761. CiteSeerX 10.1.1.702.7275 . doi :10.1016/j.jpdc.2009.04.005. S2CID  9755877. 
25. Мейерхенке, Х. (2013). Оптимизация балансировки нагрузки для адаптивного численного моделирования с параллельным MPI . 10-е соревнование по внедрению DIMACS по графовому разделению и графовой кластеризации. С. 67–82.
26. Сандерс, П .; Шульц, К. (2011). Разработка алгоритмов многоуровневого разбиения графов . Труды 19-го Европейского симпозиума по алгоритмам (ESA). Т. 6942. С. 469–480.
27. Трифунович, А.; Кноттенбельт, В. Дж. (2008). «Параллельные многоуровневые алгоритмы для разбиения гиперграфов». Журнал параллельных и распределенных вычислений . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . doi :10.1016/j.jpdc.2007.11.002. 
28. Devine, K.; Boman, E.; Heaphy, R.; Bisseling, R.; Catalyurek, Ü. (2006). Параллельное разбиение гиперграфа для научных вычислений . Труды 20-й Международной конференции по параллельной и распределенной обработке. стр. 124.

Дальнейшее чтение

• Бишо, Шарль-Эдмонд; Сиарри, Патрик (2011). Графовое разбиение: оптимизация и приложения . ISTE – Wiley. ISBN 978-1-84821-233-6.