Раздел графа - Graph partition

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

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

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

Проблема

Рассмотрим график грамм = (V, E), куда V обозначает набор п вершины и E набор граней. Для (k,v) задача сбалансированного разбиения, цель - разбить грамм в k компоненты максимального размера v · (п/k), минимизируя пропускную способность краев между отдельными компонентами.[1] Кроме того, учитывая грамм и целое число k > 1, раздел V в k части (подмножества) V1, V2, ..., Vk таким образом, чтобы части не пересекались и имели одинаковый размер, а количество ребер с конечными точками в разных частях было минимальным. Такие проблемы разделения обсуждались в литературе как подходы бикритериальной аппроксимации или увеличения ресурсов. Обычное расширение - это гиперграфы, где ребро может соединять более двух вершин. Гиперребро не разрезается, если все вершины находятся в одном разделе, и разрезается ровно один раз в противном случае, независимо от количества вершин на каждой стороне. Это использование распространено в автоматизация проектирования электроники.

Анализ

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

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

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

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

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

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

Основная статья: Многоуровневая техника

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

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

Учитывая график с матрица смежности , где запись подразумевает край между узлами и , и матрица степеней , которая представляет собой диагональную матрицу, где каждый диагональный элемент строки , , представляет степень узла узла . В Матрица лапласа определяется как . Теперь разделение по соотношению для графа определяется как раздел в непересекающийся , и , минимизируя соотношение

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

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

В таком сценарии второе наименьшее собственное значение () из , дает нижняя граница по оптимальной стоимости () пропорционального разделения с . Собственный вектор () соответствующий , называется Вектор Фидлера, делит график пополам только на два сообщества на основе знак соответствующей записи вектора. Разделение на большее количество сообществ может быть достигнуто повторным деление пополам или используя несколько собственных векторов соответствующие наименьшим собственным значениям.[11] Примеры на рисунках 1,2 иллюстрируют подход деления спектра пополам.

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

Модульность и соотношение сторон

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

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

Приложения

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

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

Иммунизация

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

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

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

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

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

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

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

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

Scikit-Learn орудия спектральная кластеризация с разбиением, определяемым из собственные векторы из граф лапласиан матрица для исходного графа, вычисленная ARPACK, или LOBPCG решатель с многосеточный предварительная подготовка.[9]

Чако,[17] благодаря Hendrickson и Leland реализует описанный выше многоуровневый подход и базовые алгоритмы локального поиска. Кроме того, они реализуют методы спектрального разделения.

МЕТИС[7] - семейство разбиений графов Кариписа и Кумара. Среди этого семейства kMetis стремится к большей скорости разделения, hMetis,[8] применяется к гиперграфам и стремится к качеству разбиения, а ParMetis[7] представляет собой параллельную реализацию алгоритма разбиения графа Метиса.

PaToH[18] - еще один разделитель гиперграфа.

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

Скотч[22] фреймворк для разбиения графов от Пеллегрини. Он использует рекурсивное многоуровневое деление пополам и включает в себя как последовательные, так и параллельные методы разделения.

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

Партия[24] реализует платформу, оптимизированную для пузырьков / форм, и алгоритм полезных наборов.

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

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

Инструменты Parkway[28] от Trifunovic и Knottenbelt, а также от Zoltan[29] Автор: Devine et al. сосредоточиться на разбиении гиперграфа.

Список бесплатных фреймворков с открытым исходным кодом:

ИмяЛицензияКраткая информация
Scikit-LearnBSDспектральное разбиение с алгебраической многосеточной предварительной подготовкой
ЧакоGPLпрограммный комплекс, реализующий спектральные методы и многоуровневый подход
DiBaP*разбиение графа на основе многоуровневых методов, алгебраической многосеточной системы, а также диффузии на основе графа
Jostle*многоуровневые методы секционирования и диффузная балансировка нагрузки, последовательная и параллельная
KaHIPМассачусетский технологический институтнесколько параллельных и последовательных метаэвристик, гарантирует ограничение баланса
KaHyParGPLмногоуровневая структура разделения гиперграфа на основе прямого k-пути и рекурсивного деления пополам
kMetisApache 2.0пакет разбиения графа, основанный на многоуровневых методах и локальном поиске k-way
МондрианLGPLразделитель матриц для разделения разреженных прямоугольных матриц
PaToHBSDмногоуровневое разбиение гиперграфа
Бульвар*параллельное многоуровневое разбиение гиперграфа
СкотчCeCILL-Cреализует многоуровневую рекурсивную деление пополам, а также методы диффузии, последовательные и параллельные
ЗолтанBSDразбиение гиперграфа

Рекомендации

  1. ^ а б c d е Андреев, Константин; Раке, Харальд (2004). Сбалансированное разбиение графа. Материалы шестнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах. Барселона, Испания. С. 120–124. CiteSeerX  10.1.1.417.8592. Дои:10.1145/1007912.1007931. ISBN  978-1-58113-840-5.
  2. ^ Булук, Айдын; Мейерхенке, Хеннинг; Сафро, Илья; Сандерс, Питер; Шульц, Кристиан (2013). «Последние достижения в области разбиения графов». arXiv:1311.3144 [cs.DS ].CS1 maint: ref = harv (связь)
  3. ^ Фельдманн, Андреас Эмиль; Фоскини, Лука (2012). «Сбалансированное разбиение деревьев и приложений». Материалы 29-го Международного симпозиума по теоретическим аспектам информатики: 100–111.
  4. ^ а б Фельдманн, Андреас Эмиль (2012). «Быстрое сбалансированное разбиение сложно даже на сетках и деревьях». Материалы 37-го Международного симпозиума по математическим основам информатики. arXiv:1111.6745. Bibcode:2011arXiv1111.6745F.
  5. ^ Garey, Michael R .; Джонсон, Дэвид С. (1979). Компьютеры и сложность: руководство по теории NP-полноты. W.H. Freeman & Co. ISBN  978-0-7167-1044-8.
  6. ^ Hendrickson, B .; Леланд, Р. (1995). Многоуровневый алгоритм разбиения графов. Материалы конференции ACM / IEEE 1995 г. по суперкомпьютерам. ACM. п. 28.
  7. ^ а б c d Karypis, G .; Кумар, В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». Журнал SIAM по научным вычислениям. 20 (1): 359. CiteSeerX  10.1.1.39.3415. Дои:10.1137 / S1064827595287997.
  8. ^ а б Karypis, G .; Aggarwal, R .; Кумар, В .; Шехар, С. (1997). Многоуровневое разбиение гиперграфа: приложение в области СБИС. Материалы 34-й ежегодной конференции по автоматизации проектирования. С. 526–529.
  9. ^ а б Князев, Андрей В. (2006). Многоуровневое разбиение спектрального графа и сегментация изображений. Семинар по алгоритмам для современных массивов данных Стэнфордский университет и Yahoo! Исследование.
  10. ^ Дж. Деммель, [1], CS267: Примечания к лекции 23, 9 апреля 1999 г., Graph Partitioning, Part 2
  11. ^ Наумов, М .; Мун, Т. (2016). «Параллельное разбиение спектрального графа». Технический отчет NVIDIA. nvr-2016-001.
  12. ^ Ньюман, М. Э. Дж. (2006). «Модульность и структура сообщества в сетях». PNAS. 103 (23): 8577–8696. arXiv:физика / 0602124. Bibcode:2006ПНАС..103.8577Н. Дои:10.1073 / pnas.0601602103. ЧВК  1482622. PMID  16723398.
  13. ^ Я. Чен, Г. Пол, С. Хэвлин, Ф. Лильерос, Х. Стэнли (2009). «Поиск лучшей стратегии иммунизации». Phys. Rev. Lett. 101: 058701.CS1 maint: несколько имен: список авторов (связь)
  14. ^ Райхардт, Йорг; Борнхольдт, Стефан (июль 2006 г.). «Статистическая механика обнаружения сообществ». Phys. Ред. E. 74 (1): 016110. arXiv:cond-mat / 0603718. Bibcode:2006PhRvE..74a6110R. Дои:10.1103 / PhysRevE.74.016110. PMID  16907154.
  15. ^ Альзате, Карлос; Суйкенс, Йохан А. К. (2010). «Многосторонняя спектральная кластеризация с расширениями вне выборки с помощью взвешенного ядра PCA». IEEE Transactions по анализу шаблонов и машинному анализу. 32 (2): 335–347. Дои:10.1109 / TPAMI.2008.292. ISSN  0162-8828. PMID  20075462.
  16. ^ Курве, А .; Griffin, C .; Кесидис Г. (2011) «Игра с разбиением графа для распределенного моделирования сетей», Материалы Международного семинара 2011 года по моделированию, анализу и управлению сложными сетями: 9–16
  17. ^ Хендриксон, Брюс. "Chaco: Программное обеспечение для разбиения графов". Цитировать журнал требует | журнал = (помощь)
  18. ^ Catalyürek, Ü .; Айканат, К. (2011). PaToH: Инструмент разбиения гиперграфов.
  19. ^ Schlag, S .; Henne, V .; Heuer, T .; Meyerhenke, H .; Sanders, P .; Шульц, К. (30 декабря 2015 г.). «K-образное разбиение гиперграфа с помощью n-уровневого рекурсивного деления пополам». 2016 Материалы восемнадцатого семинара по разработке алгоритмов и экспериментов (ALENEX). Ход работы. Общество промышленной и прикладной математики. С. 53–67. Дои:10.1137/1.9781611974317.5. ISBN  978-1-61197-431-7.
  20. ^ Ахремцев, Ю .; Heuer, T .; Sanders, P .; Шлаг, С. (01.01.2017). "Разработка прямого k-образного алгоритма разбиения гиперграфа". 2017 Труды девятнадцатого семинара по разработке алгоритмов и экспериментов (ALENEX). Ход работы. Общество промышленной и прикладной математики. С. 28–42. Дои:10.1137/1.9781611974768.3. ISBN  978-1-61197-476-8.
  21. ^ Хойер, Тобиас; Шлаг, Себастьян (2017). Iliopoulos, Costas S .; Писсис, Солон П .; Puglisi, Simon J .; Раман, Раджив (ред.). Улучшение схем укрупнения для разбиения гиперграфа за счет использования структуры сообщества. 16-й Международный симпозиум по экспериментальным алгоритмам (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs). 75. Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. С. 21: 1–21: 19. Дои:10.4230 / LIPIcs.SEA.2017.21. ISBN  9783959770361.
  22. ^ Chevalier, C .; Пеллегрини, Ф. (2008). «PT-Scotch: инструмент для эффективного упорядочивания параллельных графов». Параллельные вычисления. 34 (6): 318–331. arXiv:0907.1375. Дои:10.1016 / j.parco.2007.12.001.
  23. ^ Walshaw, C .; Кросс, М. (2000). «Разделение сетки: многоуровневый алгоритм балансировки и уточнения». Журнал по научным вычислениям. 22 (1): 63–80. CiteSeerX  10.1.1.19.1836. Дои:10.1137 / s1064827598337373.
  24. ^ Diekmann, R .; Preis, R .; Schlimbach, F .; Уолшоу, К. (2000). «Оптимизированное по форме разбиение сетки и балансировка нагрузки для параллельного адаптивного FEM». Параллельные вычисления. 26 (12): 1555–1581. CiteSeerX  10.1.1.46.5687. Дои:10.1016 / s0167-8191 (00) 00043-0.
  25. ^ Meyerhenke, H .; Monien, B .; Зауэрвальд, Т. (2008). «Новый многоуровневый алгоритм на основе диффузии для вычисления разбиений графа». Журнал параллельных вычислений и распределенных вычислений. 69 (9): 750–761. Дои:10.1016 / j.jpdc.2009.04.005.
  26. ^ Мейерхенке, Х. (2013). Оптимизация формы балансировки нагрузки для параллельного MPI адаптивного численного моделирования. 10-е задание по внедрению DIMACS в области разбиения графов и кластеризации графов. С. 67–82.
  27. ^ Сандерс, П.; Шульц, К. (2011). Разработка алгоритмов многоуровневого разбиения графов. Труды 19-го Европейского симпозиума по алгоритмам (ESA). 6942. С. 469–480.
  28. ^ Trifunovic, A .; Knottenbelt, W. J. (2008). «Параллельные многоуровневые алгоритмы разбиения гиперграфа». Журнал параллельных и распределенных вычислений. 68 (5): 563–581. CiteSeerX  10.1.1.641.7796. Дои:10.1016 / j.jpdc.2007.11.002.
  29. ^ Devine, K .; Boman, E .; Heaphy, R .; Bisseling, R .; Catalyurek, Ü. (2006). Параллельное разбиение гиперграфа для научных вычислений. Материалы 20-й Международной конференции по параллельной и распределенной обработке. п. 124.

внешняя ссылка

Библиография