Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Graph partitioning )
Перейти к навигации Перейти к поиску

В математике разбиение графа - это сокращение графа до меньшего графа путем разделения его множества узлов на взаимоисключающие группы. Ребра исходного графа, которые пересекаются между группами, образуют ребра в разбитом графе. Если количество результирующих ребер мало по сравнению с исходным графом, то разбитый граф может лучше подходить для анализа и решения проблем, чем исходный. Найти раздел, упрощающий анализ графов, - сложная задача, но она имеет приложения, в частности, для научных вычислений, проектирования схем СБИС и планирования задач на многопроцессорных компьютерах. [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.1 , V 2 , ..., V k такие, что части не пересекаются и имеют одинаковый размер, а количество ребер с концами в разных частях минимизировано. Такие проблемы разделения обсуждались в литературе как подходы бикритериальной аппроксимации или увеличения ресурсов. Распространенным расширением являются гиперграфы , где ребро может соединять более двух вершин. Гиперребро не разрезается, если все вершины находятся в одном разделе, и разрезается ровно один раз в противном случае, независимо от количества вершин на каждой стороне. Это обычное использование в автоматизации проектирования электроники .

Анализ [ править ]

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

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

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

Методы разбиения графа [ править ]

Поскольку разбиение графа - сложная проблема, практические решения основаны на эвристике. Есть две широкие категории методов: локальные и глобальные. Хорошо известные местные методы являются Керниган-Lin алгоритм , и Fiduccia-Mattheyses алгоритмов , которые были первые эффективные порезы 2-полосных местными стратегиями поиска. Их главный недостаток - произвольное начальное разбиение множества вершин, что может повлиять на качество окончательного решения. Глобальные подходы полагаются на свойства всего графа и не полагаются на произвольное начальное разбиение. Наиболее распространенным примером является спектральное разбиение, когда разбиение получается из приближенных собственных векторов матрицы смежности, или спектральная кластеризация, при которой вершины графа группируются с использованиемeigendecomposition из графа лапласиана матрицы.

Многоуровневые методы [ править ]

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

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

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

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

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

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

В таком сценарии второе наименьшее собственное значение ( ) для дает нижнюю границу оптимальной стоимости ( ) разделения с пропорциональным сокращением . Собственный вектор ( ), соответствующий , называемый вектором Фидлера , делит граф пополам только на два сообщества в зависимости от знака соответствующей записи вектора . Разделение на большее количество сообществ может быть достигнуто повторным делением пополам или использованием нескольких собственных векторов, соответствующих наименьшим собственным значениям. [12] Примеры на рисунках 1,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) , ratio-cut - метрика разделения.

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

Приложения [ править ]

Поведение [ править ]

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

Иммунизация [ править ]

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

Другие методы разбиения графа [ править ]

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

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

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

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

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

Программные инструменты [ править ]

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

Chaco, [18], созданный Хендриксоном и Лиландом, реализует многоуровневый подход, описанный выше, и основные алгоритмы локального поиска. Кроме того, они реализуют методы спектрального разделения.

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

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

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

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

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

Party [25] реализует структуру, оптимизированную для пузырьков / форм, и алгоритм Helpful Sets.

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

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

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

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

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

Ссылки [ править ]

  1. ^ a b c d e Андреев Константин; Раке, Харальд (2004). Сбалансированное разбиение графа . Материалы шестнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах . Барселона, Испания. С. 120–124. CiteSeerX 10.1.1.417.8592 . DOI : 10.1145 / 1007912.1007931 . ISBN  978-1-58113-840-5.
  2. ^ Булук, Айдын; Мейерхенке, Хеннинг; Сафро, Илья; Сандерс, Питер ; Шульц, Кристиан (2013). «Последние достижения в области разбиения графов». arXiv : 1311.3144 [ cs.DS ].
  3. ^ Фельдманн, Андреас Эмиль; Фоскини, Лука (2012). «Сбалансированное разбиение деревьев и приложений». Материалы 29-го Международного симпозиума по теоретическим аспектам информатики : 100–111.
  4. ^ a b Фельдманн, Андреас Эмиль (2012). «Быстрое сбалансированное разбиение сложно даже на сетках и деревьях». Материалы 37-го Международного симпозиума по математическим основам информатики . arXiv : 1111.6745 . Bibcode : 2011arXiv1111.6745F .
  5. ^ Garey, Michael R .; Джонсон, Дэвид С. (1979). Компьютеры и непрактичность: руководство по теории NP-полноты . ISBN WH Freeman & Co. 978-0-7167-1044-8.
  6. ^ Хендриксон, B .; Леланд, Р. (1995). Многоуровневый алгоритм разбиения графов . Материалы конференции ACM / IEEE 1995 г. по суперкомпьютерам. ACM. п. 28.
  7. ^ a b c d Karypis, G .; Кумар, В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». Журнал СИАМ по научным вычислениям . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . DOI : 10,1137 / S1064827595287997 . 
  8. ^ a b Karypis, G .; Aggarwal, R .; Кумар, В .; Шехар, С. (1997). Многоуровневое разбиение гиперграфа: приложение в области СБИС . Материалы 34-й ежегодной конференции по автоматизации проектирования. С. 526–529.
  9. ^ a b Князев, Андрей В. (2006). Многомасштабное разбиение спектрального графа и сегментация изображений . Семинар по алгоритмам для современных массивов данных Стэнфордский университет и Yahoo! Исследовать.
  10. ^ Дж. Деммель, [1] , CS267: Заметки к лекции 23, 9 апреля 1999 г., разделение графа, часть 2
  11. ^ Князев, Андрей (2018). О спектральном разбиении знаковых графов . Восьмой семинар SIAM по комбинаторным научным вычислениям, CSC 2018, Берген, Норвегия, 6-8 июня. DOI : 10.1137 / 1.9781611975215.2 .
  12. ^ Наумов, М .; Мун, Т. (2016). «Параллельное разбиение спектрального графа» . Технический отчет NVIDIA . nvr-2016-001.
  13. ^ Ньюман, MEJ (2006). «Модульность и структура сообщества в сетях» . PNAS . 103 (23): 8577–8696. arXiv : физика / 0602124 . Bibcode : 2006PNAS..103.8577N . DOI : 10.1073 / pnas.0601602103 . PMC 1482622 . PMID 16723398 .  
  14. ^ Ю. Чен, Г. Пауль, С. Хавлин, Ф. Liljeros, Стенли (2009). «Поиск лучшей стратегии иммунизации». Phys. Rev. Lett . 101 (5): 058701. DOI : 10,1103 / PhysRevLett.101.058701 . PMID 18764435 . CS1 maint: multiple names: authors list (link)
  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. ^ Альзате, Карлос; Суйкенс, Йохан АК (2010). «Многосторонняя спектральная кластеризация с расширениями вне выборки с помощью взвешенного ядра PCA». IEEE Transactions по анализу шаблонов и машинному анализу . 32 (2): 335–347. DOI : 10.1109 / TPAMI.2008.292 . ISSN 0162-8828 . PMID 20075462 . S2CID 200488 .   
  17. ^ Курве, А .; Griffin, C .; Кесидис Г. (2011) «Игра с разбиением графа для распределенного моделирования сетей», Труды Международного семинара 2011 года по моделированию, анализу и управлению сложными сетями : 9–16
  18. ^ Хендриксон, Брюс. "Chaco: Программное обеспечение для разбиения графов". Cite journal requires |journal= (help)
  19. ^ Catalyürek, Ü .; Айканат, К. (2011). PaToH: Инструмент разбиения гиперграфов .
  20. ^ Schlag, S .; Henne, V .; Heuer, T .; Meyerhenke, H .; Sanders, P .; Шульц, К. (30 декабря 2015 г.). «K-образное разбиение гиперграфа с помощью n-уровневого рекурсивного деления пополам». 2016 Труды восемнадцатого семинара по разработке алгоритмов и экспериментов (ALENEX) . Ход работы. Общество промышленной и прикладной математики. С. 53–67. DOI : 10.1137 / 1.9781611974317.5 . ISBN 978-1-61197-431-7. S2CID  1674598 .
  21. ^ Ахремцев, Ю .; Heuer, T .; Sanders, P .; Шлаг, С. (01.01.2017). «Разработка прямого k-образного алгоритма разбиения гиперграфа». 2017 Труды девятнадцатого семинара по разработке алгоритмов и экспериментов (ALENEX) . Ход работы. Общество промышленной и прикладной математики. С. 28–42. DOI : 10.1137 / 1.9781611974768.3 . ISBN 978-1-61197-476-8.
  22. ^ Heuer, Тобиас; Шлаг, Себастьян (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. DOI : 10.4230 / LIPIcs.SEA.2017.21 . ISBN 9783959770361.
  23. ^ Chevalier, C .; Пеллегрини, Ф. (2008). «PT-Scotch: инструмент для эффективного упорядочивания параллельных графов». Параллельные вычисления . 34 (6): 318–331. arXiv : 0907.1375 . DOI : 10.1016 / j.parco.2007.12.001 . S2CID 10433524 . 
  24. ^ Уолшоу, C .; Кросс, М. (2000). «Разделение сетки: многоуровневый алгоритм балансировки и уточнения». Журнал по научным вычислениям . 22 (1): 63–80. CiteSeerX 10.1.1.19.1836 . DOI : 10.1137 / s1064827598337373 . 
  25. ^ Diekmann, R .; Preis, R .; Schlimbach, F .; Уолшоу, К. (2000). «Оптимизированное по форме разбиение сетки и балансировка нагрузки для параллельного адаптивного FEM». Параллельные вычисления . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . DOI : 10.1016 / s0167-8191 (00) 00043-0 . 
  26. ^ Meyerhenke, H .; Monien, B .; Зауэрвальд, Т. (2008). «Новый многоуровневый алгоритм на основе диффузии для вычисления разбиений графа». Журнал параллельных вычислений и распределенных вычислений . 69 (9): 750–761. DOI : 10.1016 / j.jpdc.2009.04.005 . S2CID 9755877 . 
  27. ^ Meyerhenke, H. (2013). Оптимизация формы для балансировки нагрузки для параллельного MPI-адаптивного численного моделирования . 10-е задание по внедрению DIMACS в области разбиения графов и кластеризации графов. С. 67–82.
  28. ^ Сандерс, П .; Шульц, К. (2011). Разработка алгоритмов многоуровневого разбиения графов . Труды 19-го Европейского симпозиума по алгоритмам (ESA). 6942 . С. 469–480.
  29. ^ Trifunovic, A .; Knottenbelt, WJ (2008). «Параллельные многоуровневые алгоритмы разбиения гиперграфа». Журнал параллельных и распределенных вычислений . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . DOI : 10.1016 / j.jpdc.2007.11.002 . 
  30. ^ Девайн, К .; Boman, E .; Heaphy, R .; Bisseling, R .; Catalyurek, Ü. (2006). Параллельное разбиение гиперграфа для научных вычислений . Материалы 20-й Международной конференции по параллельной и распределенной обработке. п. 124.

Внешние ссылки [ править ]

  • Чемберлен, Брэдфорд Л. (1998). «Алгоритмы разделения графа для распределения рабочих нагрузок параллельных вычислений» [ постоянная мертвая ссылка ]

Библиография [ править ]

  • Бишо, Шарль-Эдмонд; Сиарри, Патрик (2011). Разбиение графа: оптимизация и приложения . ISTE - Wiley. п. 384. ISBN 978-1848212336.
  • Фельдманн, Андреас Эмиль (2012). Сбалансированное разбиение сеток и связанных графов: теоретическое исследование распределения данных при параллельном моделировании конечно-элементных моделей . Геттинген, Германия: Cuvillier Verlag. п. 218. ISBN 978-3954041251. Исчерпывающий анализ проблемы с теоретической точки зрения.
  • Керниган, BW; Лин, С. (1970). «Эффективная эвристическая процедура разбиения графов» (PDF) . Технический журнал Bell System . 49 (2): 291–307. DOI : 10.1002 / j.1538-7305.1970.tb01770.x . Одна из первых фундаментальных работ в этой области. Однако производительность O (n 2 ), поэтому она больше не используется.
  • Фидучча, CM; Mattheyses, RM (1982). Эвристика линейного времени для улучшения сетевых разделов . Конференция по автоматизации проектирования. DOI : 10.1109 / DAC.1982.1585498 . Более поздний вариант - линейное время, очень часто используемый как сам по себе, так и как часть многоуровневого разбиения, см. Ниже.
  • Karypis, G .; Кумар, В. (1999). «Быстрая и качественная многоуровневая схема для разбиения нерегулярных графов» . Журнал СИАМ по научным вычислениям . Многоуровневое разбиение - это современный уровень техники. В этой статье также есть хорошие объяснения многих других методов и сравнения различных методов по широкому кругу проблем.
  • Karypis, G .; Aggarwal, R .; Кумар, В .; Шехар, С. (март 1999 г.). «Многоуровневое разбиение гиперграфа: приложения в области СБИС». Транзакции IEEE в системах с очень крупномасштабной интеграцией (СБИС) . 7 (1): 69–79. CiteSeerX  10.1.1.553.2367 . DOI : 10.1109 / 92.748202 . Разделение графа (и, в частности, разделение гиперграфа) имеет множество применений в разработке интегральных схем.
  • Киркпатрик, S .; Gelatt, CD, Jr .; Векки, депутат (13 мая 1983 г.). «Оптимизация путем имитации отжига». Наука . 220 (4598): 671–680. Bibcode : 1983Sci ... 220..671K . CiteSeerX  10.1.1.123.7607 . DOI : 10.1126 / science.220.4598.671 . PMID  17813860 . S2CID  205939 . Также можно использовать имитацию отжига.
  • Hagen, L .; Канг, AB (сентябрь 1992 г.). «Новые спектральные методы для разделения и кластеризации по коэффициенту отсечения». IEEE Transactions по автоматизированному проектированию интегральных схем и систем . 11 (9): 1074–1085. DOI : 10.1109 / 43.159993 .. Существует целый класс методов спектрального разделения , в которых используются собственные векторы лапласиана графа связности. Вы можете увидеть демонстрацию этого , используя Matlab.