Раздел графа

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

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

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

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

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

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

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

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

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

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

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

Учитывая график $G=(V,E)$ с матрицей смежности $A$ , где запись $A_{ij}$ подразумевает ребро между узлом $i$ и $j$ и матрица степеней $D$ , которая представляет собой диагональную матрицу, где каждый диагональный элемент строки $i$ , $d_{ii}$ , представляет степень узла узла $i$ . Матрица Лапласа $L$ определяется как $L=D-A$ . Теперь раздел с сокращением соотношения для графика $G=(V,E)$ определяется как раздел $V$ в непересекающиеся $U$ , и $W$ , минимизируя соотношение

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

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

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

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

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

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

Приложения

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

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

Иммунизация

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

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

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

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

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

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

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

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

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

ПОМЕЩАТЬ ^[7] — это семейство разбиения графов, разработанное Кариписом и Кумаром. Среди этого семейства kMetis нацелен на более высокую скорость разделения, hMetis, ^[8] применяется к гиперграфам и нацелен на качество разделения, а ParMetis ^[7] представляет собой параллельную реализацию алгоритма разделения графа Metis.

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

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Андреев Константин; Раке, Харальд (2004). «Сбалансированное разбиение графа». Материалы шестнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах . Барселона, Испания. стр. 120–124. CiteSeerX 10.1.1.417.8592 . дои : 10.1145/1007912.1007931 . ISBN 978-1-58113-840-5 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Булюк, Айдын; Мейерхенке, Хеннинг; Сафро, Илья; Сандерс, Питер ; Шульц, Кристиан (2013). «Последние достижения в секционировании графов». arXiv : 1311.3144 [ cs.DS ].
^ Фельдманн, Андреас Эмиль; Фоскини, Лука (2012). «Сбалансированные разделы деревьев и приложений». Материалы 29-го Международного симпозиума по теоретическим аспектам информатики : 100–111.
^ Jump up to: ^а ^б Фельдманн, Андреас Эмиль (2012). «Быстрое сбалансированное секционирование сложно даже на сетках и деревьях». Материалы 37-го Международного симпозиума по математическим основам информатики . arXiv : 1111.6745 . Бибкод : 2011arXiv1111.6745F .
^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Freeman & Co. ISBN 978-0-7167-1044-8 .
^ Хендриксон, Б.; Лиланд, Р. (1995). Многоуровневый алгоритм разбиения графов . Материалы конференции ACM/IEEE 1995 года по суперкомпьютерам. АКМ. п. 28.
^ Jump up to: ^а ^б ^с ^д Карипис, Г.; Кумар, В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». SIAM Журнал по научным вычислениям . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . дои : 10.1137/S1064827595287997 . S2CID 3628209 .
^ Jump up to: ^а ^б Карипис, Г.; Аггарвал, Р.; Кумар, В.; Шекхар, С. (1997). Многоуровневое разбиение гиперграфа: применение в области СБИС . Материалы 34-й ежегодной конференции по автоматизации проектирования. стр. 526–529.
^ Jump up to: ^а ^б Князев, Андрей В. (2006). Многомасштабное разбиение спектрального графа и сегментация изображений . Семинар по алгоритмам обработки современных массивов данных Стэнфордского университета и Yahoo! Исследовать.
^ Дж. Деммель, [1] , CS267: Примечания к лекции 23, 9 апреля 1999 г., Разделение графа, Часть 2
^ Князев, Андрей (2018). О спектральном разбиении знаковых графов . Восьмой семинар SIAM по комбинаторным научным вычислениям, CSC 2018, Берген, Норвегия, 6–8 июня. arXiv : 1701.01394 . дои : 10.1137/1.9781611975215.2 .
^ Наумов М.; Мун, Т. (2016). «Параллельное разбиение спектрального графа» . Технический отчет NVIDIA . нвр-2016-001.
^ Ньюман, МЕДЖ (2006). «Модульность и структура сообщества в сетях» . ПНАС . 103 (23): 8577–8696. arXiv : физика/0602124 . Бибкод : 2006PNAS..103.8577N . дои : 10.1073/pnas.0601602103 . ПМЦ 1482622 . ПМИД 16723398 .
^ Ю. Чен, Г. Пол, С. Хэвлин, Ф. Лильерос, Х. Э. Стэнли (2009). «В поисках лучшей стратегии иммунизации». Физ. Преподобный Летт . 101 (5): 058701. doi : 10.1103/PhysRevLett.101.058701 . ПМИД 18764435 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Райхардт, Йорг; Борнхольдт, Стефан (июль 2006 г.). «Статистическая механика обнаружения сообществ». Физ. Преподобный Е. 74 (1): 016110. arXiv : cond-mat/0603718 . Бибкод : 2006PhRvE..74a6110R . дои : 10.1103/PhysRevE.74.016110 . ПМИД 16907154 . S2CID 792965 .
^ Альзате, Карлос; Суйкенс, Йохан АК (2010). «Многосторонняя спектральная кластеризация с расширениями за пределами выборки посредством взвешенного ядра PCA». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (2): 335–347. дои : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . ПМИД 20075462 . S2CID 200488 .
^ Курве, А.; Гриффин, К.; Кесидис Г. (2011) «Игра с разделением графов для распределенного моделирования сетей», Материалы Международного семинара 2011 г. по моделированию, анализу и управлению сложными сетями : 9–16
^ Шлаг, С.; Хенне, В.; Хойер, Т.; Мейерхенке, Х.; Сандерс, П.; Шульц, К. (30 декабря 2015 г.). «K-образное разделение гиперграфа посредством n-уровневого рекурсивного деления пополам». 2016 Материалы восемнадцатого семинара по алгоритмической разработке и экспериментам (ALENEX) . Общество промышленной и прикладной математики. стр. 53–67. arXiv : 1511.03137 . дои : 10.1137/1.9781611974317.5 . ISBN 978-1-61197-431-7 . S2CID 1674598 .
^ Ахремцев Ю.; Хойер, Т.; Сандерс, П.; Шлаг, С. (1 января 2017 г.). «Разработка прямого алгоритма разделения гиперграфа k-way». 2017 Материалы девятнадцатого семинара по алгоритмической разработке и экспериментам (ALENEX) . Общество промышленной и прикладной математики. стр. 28–42. дои : 10.1137/1.9781611974768.3 . ISBN 978-1-61197-476-8 .
^ Хойер, Тобиас; Шлаг, Себастьян (2017). «Улучшение схем огрубления для разделения гиперграфов путем использования структуры сообщества». В Илиопулосе, Костас С.; Писсис, Солон П.; Пуглиси, Саймон Дж.; Раман, Раджив (ред.). 16-й Международный симпозиум по экспериментальным алгоритмам (SEA 2017) . Международные труды Лейбница по информатике (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 .
^ Шевалье, К.; Пеллегрини, Ф. (2008). «PT-Scotch: инструмент для эффективного параллельного упорядочения графов». Параллельные вычисления . 34 (6): 318–331. arXiv : 0907.1375 . дои : 10.1016/j.parco.2007.12.001 . S2CID 10433524 .
^ Уолшоу, К.; Кросс, М. (2000). «Разбиение сетки: многоуровневый алгоритм балансировки и уточнения». Журнал научных вычислений . 22 (1): 63–80. Бибкод : 2000SJSC...22...63W . CiteSeerX 10.1.1.19.1836 . дои : 10.1137/s1064827598337373 .
^ Дикманн, Р.; Прейс, Р.; Шлимбах, Ф.; Уолшоу, К. (2000). «Разбиение сетки с оптимизированной формой и балансировка нагрузки для параллельного адаптивного FEM». Параллельные вычисления . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . дои : 10.1016/s0167-8191(00)00043-0 .
^ Мейерхенке, Х.; Моньен, Б.; Зауэрвальд, Т. (2008). «Новый многоуровневый алгоритм на основе диффузии для вычисления разбиений графа». Журнал параллельных вычислений и распределенных вычислений . 69 (9): 750–761. CiteSeerX 10.1.1.702.7275 . дои : 10.1016/j.jpdc.2009.04.005 . S2CID 9755877 .
^ Мейерхенке, Х. (2013). Оптимизация формы балансировки нагрузки для MPI-параллельного адаптивного численного моделирования . Десятый конкурс по внедрению DIMACS по разделению графов и кластеризации графов. стр. 67–82.
^ Сандерс, П .; Шульц, К. (2011). Разработка алгоритмов разбиения многоуровневых графов . Материалы 19-го Европейского симпозиума по алгоритмам (ESA). Том. 6942. стр. 469–480.
^ Трифунович А.; Ноттенбелт, WJ (2008). «Параллельные многоуровневые алгоритмы разделения гиперграфов». Журнал параллельных и распределенных вычислений . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . дои : 10.1016/j.jpdc.2007.11.002 .
^ Девайн, К.; Боман, Э.; Хифи, Р.; Бисселинг, Р.; Каталюрек, Ю. (2006). Параллельное разбиение гиперграфов для научных вычислений . Материалы 20-й Международной конференции по параллельной и распределенной обработке. п. 124.

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

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

[balgraph-1] Jump up to: ^а ^б ^с ^д ^и Андреев Константин; Раке, Харальд (2004). «Сбалансированное разбиение графа». Материалы шестнадцатого ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах . Барселона, Испания. стр. 120–124. CiteSeerX 10.1.1.417.8592 . дои : 10.1145/1007912.1007931 . ISBN 978-1-58113-840-5 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[recentadvances-2] Булюк, Айдын; Мейерхенке, Хеннинг; Сафро, Илья; Сандерс, Питер ; Шульц, Кристиан (2013). «Последние достижения в секционировании графов». arXiv : 1311.3144 [ cs.DS ].

[baltrees-3] Фельдманн, Андреас Эмиль; Фоскини, Лука (2012). «Сбалансированные разделы деревьев и приложений». Материалы 29-го Международного симпозиума по теоретическим аспектам информатики : 100–111.

[fastpartition-4] Jump up to: ^а ^б Фельдманн, Андреас Эмиль (2012). «Быстрое сбалансированное секционирование сложно даже на сетках и деревьях». Материалы 37-го Международного симпозиума по математическим основам информатики . arXiv : 1111.6745 . Бибкод : 2011arXiv1111.6745F .

[minbisect-5] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Freeman & Co. ISBN 978-0-7167-1044-8 .

[6] Хендриксон, Б.; Лиланд, Р. (1995). Многоуровневый алгоритм разбиения графов . Материалы конференции ACM/IEEE 1995 года по суперкомпьютерам. АКМ. п. 28.

[:0-7] Jump up to: ^а ^б ^с ^д Карипис, Г.; Кумар, В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». SIAM Журнал по научным вычислениям . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . дои : 10.1137/S1064827595287997 . S2CID 3628209 .

[hmetis-8] Jump up to: ^а ^б Карипис, Г.; Аггарвал, Р.; Кумар, В.; Шекхар, С. (1997). Многоуровневое разбиение гиперграфа: применение в области СБИС . Материалы 34-й ежегодной конференции по автоматизации проектирования. стр. 526–529.

[spectralmultigrid2006-9] Jump up to: ^а ^б Князев, Андрей В. (2006). Многомасштабное разбиение спектрального графа и сегментация изображений . Семинар по алгоритмам обработки современных массивов данных Стэнфордского университета и Yahoo! Исследовать.

[10] Дж. Деммель, [1] , CS267: Примечания к лекции 23, 9 апреля 1999 г., Разделение графа, Часть 2

[11] Князев, Андрей (2018). О спектральном разбиении знаковых графов . Восьмой семинар SIAM по комбинаторным научным вычислениям, CSC 2018, Берген, Норвегия, 6–8 июня. arXiv : 1701.01394 . дои : 10.1137/1.9781611975215.2 .

[spectral_nvidia_tr-12] Наумов М.; Мун, Т. (2016). «Параллельное разбиение спектрального графа» . Технический отчет NVIDIA . нвр-2016-001.

[npnas-13] Ньюман, МЕДЖ (2006). «Модульность и структура сообщества в сетях» . ПНАС . 103 (23): 8577–8696. arXiv : физика/0602124 . Бибкод : 2006PNAS..103.8577N . дои : 10.1073/pnas.0601602103 . ПМЦ 1482622 . ПМИД 16723398 .

[14] Ю. Чен, Г. Пол, С. Хэвлин, Ф. Лильерос, Х. Э. Стэнли (2009). «В поисках лучшей стратегии иммунизации». Физ. Преподобный Летт . 101 (5): 058701. doi : 10.1103/PhysRevLett.101.058701 . ПМИД 18764435 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[potts-15] Райхардт, Йорг; Борнхольдт, Стефан (июль 2006 г.). «Статистическая механика обнаружения сообществ». Физ. Преподобный Е. 74 (1): 016110. arXiv : cond-mat/0603718 . Бибкод : 2006PhRvE..74a6110R . дои : 10.1103/PhysRevE.74.016110 . ПМИД 16907154 . S2CID 792965 .

[pami-16] Альзате, Карлос; Суйкенс, Йохан АК (2010). «Многосторонняя спектральная кластеризация с расширениями за пределами выборки посредством взвешенного ядра PCA». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (2): 335–347. дои : 10.1109/TPAMI.2008.292 . ISSN 0162-8828 . ПМИД 20075462 . S2CID 200488 .

[17] Курве, А.; Гриффин, К.; Кесидис Г. (2011) «Игра с разделением графов для распределенного моделирования сетей», Материалы Международного семинара 2011 г. по моделированию, анализу и управлению сложными сетями : 9–16

[18] Шлаг, С.; Хенне, В.; Хойер, Т.; Мейерхенке, Х.; Сандерс, П.; Шульц, К. (30 декабря 2015 г.). «K-образное разделение гиперграфа посредством n-уровневого рекурсивного деления пополам». 2016 Материалы восемнадцатого семинара по алгоритмической разработке и экспериментам (ALENEX) . Общество промышленной и прикладной математики. стр. 53–67. arXiv : 1511.03137 . дои : 10.1137/1.9781611974317.5 . ISBN 978-1-61197-431-7 . S2CID 1674598 .

[19] Ахремцев Ю.; Хойер, Т.; Сандерс, П.; Шлаг, С. (1 января 2017 г.). «Разработка прямого алгоритма разделения гиперграфа k-way». 2017 Материалы девятнадцатого семинара по алгоритмической разработке и экспериментам (ALENEX) . Общество промышленной и прикладной математики. стр. 28–42. дои : 10.1137/1.9781611974768.3 . ISBN 978-1-61197-476-8 .

[20] Хойер, Тобиас; Шлаг, Себастьян (2017). «Улучшение схем огрубления для разделения гиперграфов путем использования структуры сообщества». В Илиопулосе, Костас С.; Писсис, Солон П.; Пуглиси, Саймон Дж.; Раман, Раджив (ред.). 16-й Международный симпозиум по экспериментальным алгоритмам (SEA 2017) . Международные труды Лейбница по информатике (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 .

[scotch-21] Шевалье, К.; Пеллегрини, Ф. (2008). «PT-Scotch: инструмент для эффективного параллельного упорядочения графов». Параллельные вычисления . 34 (6): 318–331. arXiv : 0907.1375 . дои : 10.1016/j.parco.2007.12.001 . S2CID 10433524 .

[jostle-22] Уолшоу, К.; Кросс, М. (2000). «Разбиение сетки: многоуровневый алгоритм балансировки и уточнения». Журнал научных вычислений . 22 (1): 63–80. Бибкод : 2000SJSC...22...63W . CiteSeerX 10.1.1.19.1836 . дои : 10.1137/s1064827598337373 .

[party-23] Дикманн, Р.; Прейс, Р.; Шлимбах, Ф.; Уолшоу, К. (2000). «Разбиение сетки с оптимизированной формой и балансировка нагрузки для параллельного адаптивного FEM». Параллельные вычисления . 26 (12): 1555–1581. CiteSeerX 10.1.1.46.5687 . дои : 10.1016/s0167-8191(00)00043-0 .

[dibap-24] Мейерхенке, Х.; Моньен, Б.; Зауэрвальд, Т. (2008). «Новый многоуровневый алгоритм на основе диффузии для вычисления разбиений графа». Журнал параллельных вычислений и распределенных вычислений . 69 (9): 750–761. CiteSeerX 10.1.1.702.7275 . дои : 10.1016/j.jpdc.2009.04.005 . S2CID 9755877 .

[pdibap-25] Мейерхенке, Х. (2013). Оптимизация формы балансировки нагрузки для MPI-параллельного адаптивного численного моделирования . Десятый конкурс по внедрению DIMACS по разделению графов и кластеризации графов. стр. 67–82.

[kahip-26] Сандерс, П .; Шульц, К. (2011). Разработка алгоритмов разбиения многоуровневых графов . Материалы 19-го Европейского симпозиума по алгоритмам (ESA). Том. 6942. стр. 469–480.

[parkway-27] Трифунович А.; Ноттенбелт, WJ (2008). «Параллельные многоуровневые алгоритмы разделения гиперграфов». Журнал параллельных и распределенных вычислений . 68 (5): 563–581. CiteSeerX 10.1.1.641.7796 . дои : 10.1016/j.jpdc.2007.11.002 .

[zoltan-28] Девайн, К.; Боман, Э.; Хифи, Р.; Бисселинг, Р.; Каталюрек, Ю. (2006). Параллельное разбиение гиперграфов для научных вычислений . Материалы 20-й Международной конференции по параллельной и распределенной обработке. п. 124.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]