Силовое рисование графика

Визуализация социальных сетей с использованием алгоритма принудительного рисования графов ^[1]

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

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

Силы

Алгоритмы рисования графов, ориентированные на силу, распределяют силы между набором ребер и набором узлов рисунка графа . Обычно пружинные силы притяжения, основанные на законе Гука, используются для притяжения пар концов ребер графа друг к другу, в то время как одновременно силы отталкивания, подобные силам электрически заряженных частиц, основанных на законе Кулона, используются для разделения всех пар узлов. В состояниях равновесия для этой системы сил края имеют тенденцию иметь одинаковую длину (из-за сил пружины), а узлы, не соединенные краем, имеют тенденцию отдаляться друг от друга (из-за электрического отталкивания). Силы притяжения кромок и отталкивания вершин можно определить с помощью функций, которые не основаны на физическом поведении пружин и частиц; например, в некоторых системах с направленным усилием используются пружины, сила притяжения которых логарифмическая, а не линейная.

Альтернативная модель рассматривает пружинную силу для каждой пары узлов. $(i,j)$ где идеальная длина $\delta _{ij}$ каждой пружины пропорционально теоретическому расстоянию между узлами i и j без использования отдельной отталкивающей силы. Минимизация разницы (обычно квадратной разницы) между евклидовым и идеальным расстояниями между узлами эквивалентна задаче метрического многомерного масштабирования .

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

Методы

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

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

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

Преимущества

Среди наиболее важных преимуществ алгоритмов принудительного управления можно назвать следующие:

Качественные результаты: По крайней мере, для графов среднего размера (до 50–500 вершин) полученные результаты обычно имеют очень хорошее качество, основанное на следующих критериях: равномерная длина ребер, равномерное распределение вершин и проявление симметрии. Этот последний критерий является одним из наиболее важных, и его трудно достичь с помощью любого другого типа алгоритма.
Гибкость: Алгоритмы, направленные на силу, можно легко адаптировать и расширить для удовлетворения дополнительных эстетических критериев. Это делает их наиболее универсальным классом алгоритмов рисования графов. Примеры существующих расширений включают расширения для ориентированных графов, рисования трехмерных графиков, ^[6] рисование кластерного графа, рисование ограниченного графа и рисование динамического графа.
Интуитивный: Поскольку они основаны на физических аналогиях обычных объектов, таких как пружины, поведение алгоритмов относительно легко предсказать и понять. Это не относится к другим типам алгоритмов рисования графиков .
Простота: Типичные алгоритмы принудительного управления просты и могут быть реализованы в нескольких строках кода. Другие классы алгоритмов рисования графов, например, алгоритмы для ортогональных макетов, обычно гораздо более сложны.
Интерактивность: Еще одним преимуществом этого класса алгоритмов является интерактивный аспект. Рисуя промежуточные этапы графа, пользователь может проследить, как он развивается, видя, как он превращается из запутанного беспорядка в красивую конфигурацию. В некоторых инструментах рисования интерактивных графиков пользователь может вывести один или несколько узлов из состояния равновесия и наблюдать, как они возвращаются в исходное положение. Это делает их предпочтительным выбором для динамических и онлайн -систем рисования графиков.
Прочная теоретическая база: В то время как в литературе и на практике часто появляются простые специальные алгоритмы, направленные на принуждение (поскольку их относительно легко понять), более аргументированные подходы начинают набирать обороты. Статистики решают подобные проблемы в многомерном масштабировании (MDS) с 1930-х годов, а физики также имеют долгую историю работы с соответствующими проблемами n тел - поэтому существуют чрезвычайно зрелые подходы. Например, подход мажорирования напряжений к метрическому MDS можно применить к построению графика, как описано выше. Было доказано, что это сходится монотонно . ^[5] Монотонная сходимость — свойство алгоритма на каждой итерации уменьшать нагрузку или стоимость макета — важна, поскольку гарантирует, что макет в конечном итоге достигнет локального минимума и остановится. Графики демпфирования приводят к остановке алгоритма, но не могут гарантировать достижение истинного локального минимума.

Недостатки

К основным недостаткам силовых алгоритмов можно отнести следующее:

Высокое время работы: Обычно считается, что типичные алгоритмы, направленные на силу, выполняются за кубическое время ( $O(n^{3})$ ), где $n$ — количество узлов входного графа. Это связано с тем, что количество итераций оценивается как линейное ( $O(n)$ ), и на каждой итерации необходимо посетить все пары узлов и вычислить их взаимные силы отталкивания. Это связано с проблемой N тел в физике. Однако, поскольку силы отталкивания носят локальный характер, граф можно разделить так, чтобы учитываться только соседние вершины. Общие методы, используемые алгоритмами для определения макета больших графов, включают многомерное встраивание, ^[7] многослойное рисование и другие методы, связанные с моделированием N-тел . Например, моделировании Барнса – Хата. метод FADE, основанный на ^[8] может улучшить время работы, чтобы оно было линейным, или $n\log(n)$ за итерацию. Грубо говоря, можно рассчитывать на то, что за несколько секунд можно будет нарисовать не более 1000 узлов стандартным способом. $n^{2}$ за технику итерации и 100 000 с $n\log(n)$ за каждую итерацию. ^[8] Алгоритмы принудительного управления в сочетании с подходом кластеризации графов могут создавать графы из миллионов узлов. ^[9]

Плохие локальные минимумы: Легко видеть, что алгоритмы, направленные на силу, создают граф с минимальной энергией, в частности тот, полная энергия которого является лишь локальным минимумом . Найденный локальный минимум во многих случаях может быть значительно хуже глобального минимума, что приводит к низкому качеству рисунка. Для многих алгоритмов, особенно тех, которые допускают только вниз перемещение вершин , на конечный результат может сильно влиять первоначальная компоновка, которая в большинстве случаев генерируется случайным образом. Проблема плохих локальных минимумов становится более важной по мере увеличения числа вершин графа. Совместное применение различных алгоритмов помогает решить эту проблему. ^[10] Например, с помощью алгоритма Камады–Каваи ^[11] чтобы быстро создать разумный первоначальный макет, а затем алгоритм Фрухтермана-Рейнгольда. ^[12] для улучшения размещения соседних узлов. Другой метод достижения глобального минимума — использование многоуровневого подхода. ^[13]

История

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

Комбинация сил притяжения на соседних вершинах и сил отталкивания на всех вершинах была впервые использована Идсом (1984) ; ^[15] Дополнительная новаторская работа над этим типом силовой компоновки была проведена Фрухтерманом и Рейнгольдом (1991) . ^[12] Идея использования только пружинных сил между всеми парами вершин с идеальной длиной пружины, равной теоретическому расстоянию между вершинами, взята из работы Камада и Каваи (1989) . ^[11]

См. также

Cytoscape — программное обеспечение для визуализации биологических сетей. Базовый пакет включает в себя принудительно управляемые макеты в качестве одного из встроенных методов.
Gephi — интерактивная платформа визуализации и исследования всех видов сетей и сложных систем, динамических и иерархических графиков.
Graphviz — программное обеспечение, реализующее многоуровневый алгоритм принудительной компоновки (среди многих других), способное обрабатывать очень большие графики.
Tulip — программное обеспечение, реализующее большинство алгоритмов принудительной компоновки (GEM, LGL, GRIP, FM³).
Предфуз

Ссылки

^ Гранжан, Мартин (2015), «Введение в визуализацию данных, сетевой анализ в истории», Geschichte und Informatik 18/19 (PDF) , стр. 109–128
^ Кобуров, Стивен Г. (2012), Spring Embedders и алгоритмы принудительного рисования графов , arXiv : 1201.3011 , Bibcode : 2012arXiv1201.3011K .
^ Баннистер, MJ; Эппштейн, Д .; Гудрич, Монтана ; Тротт, Л. (2012), «Силовое рисование графов с использованием социальной гравитации и масштабирования», Proc. 20-й Международный Симп. Рисунок графика , arXiv : 1209.0748 , Bibcode : 2012arXiv1209.0748B .
^ Чернобельский Р.; Каннингем, К.; Гудрич, Монтана ; Кобуров, С.Г.; Тротт, Л. (2011), «Рисование графика в стиле Ломбарди, управляемое силой», Proc. 19-й симпозиум по рисованию графов (PDF) , стр. 78–90 .
^ Перейти обратно: ^а ^б де Леу, Январь (1988), «Сходимость метода мажорирования для многомерного масштабирования», Journal of Classification , 5 (2), Springer: 163–180, doi : 10.1007/BF01897162 , S2CID 122413124 .
^ Восе, Аарон. «3D-просмотрщик филогенетического дерева» . Проверено 3 июня 2012 г.
^ Харель, Дэвид ; Корен, Иегуда (2002), «Рисование графов методом многомерного встраивания», Труды 9-го Международного симпозиума по рисованию графов , стр. 207–219, CiteSeerX 10.1.1.20.5390 , ISBN 3-540-00158-1
^ Перейти обратно: ^а ^б Куигли, Аарон; Идс, Питер (2001), «FADE: рисование графов, кластеризация и визуальная абстракция», Труды 8-го Международного симпозиума по рисованию графов (PDF) , стр. 197–210, ISBN 3-540-41554-8 .
^ «Галерея больших графов» . Проверено 22 октября 2017 г.
^ Коллберг, Кристиан; Кобуров, Стивен; Награ, Ясвир; Питтс, Джейкоб; Уэмплер, Кевин (2003), «Система для графической визуализации эволюции программного обеспечения», Труды симпозиума ACM 2003 года по визуализации программного обеспечения (SoftVis '03) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 77– 86, рисунки на стр. 212, номер домена : 10.1145/774833.774844 , ISBN 1-58113-642-0 , S2CID 824991 , Чтобы добиться эстетически приятного расположения графика, также необходимо использовать модифицированные силы Фрухтермана-Рейнгольда, поскольку метод Камады-Каваи сам по себе не обеспечивает удовлетворительных методов, а скорее создает хорошую приближенную структуру, так что Расчеты Рейнгольда позволяют быстро «привести в порядок» планировку.
^ Перейти обратно: ^а ^б Камада, Томихиса; Каваи, Сатору (1989), «Алгоритм рисования общих неориентированных графов», Information Processing Letters , 31 (1), Elsevier: 7–15, doi : 10.1016/0020-0190(89)90102-6 .
^ Перейти обратно: ^а ^б Фрухтерман, Томас М.Дж.; Рейнгольд, Эдвард М. (1991), «Построение графика путем принудительного размещения», Software: Practice and Experience , 21 (11), Wiley: 1129–1164, doi : 10.1002/spe.4380211102 , S2CID 31468174 .
^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Многоуровневый алгоритм для принудительного управленияРисование графиков
^ Тутте, WT (1963), «Как нарисовать график», Proceedings of the London Mathematical Society , 13 (52): 743–768, doi : 10.1112/plms/s3-13.1.743 .
^ Идс, Питер (1984), «Эвристика для построения графиков», Congressus Numerantium , 42 (11): 149–160 .

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

ди Баттиста, Джузеппе; Питер Идс ; Роберто Тамассиа ; Иоаннис Г. Толлис (1999), Рисование графиков: алгоритмы визуализации графиков , Прентис Холл, ISBN 978-0-13-301615-4
Кауфманн, Майкл; Вагнер, Доротея , ред. (2001), Рисование графиков: методы и модели , Конспект лекций по информатике 2025, том. 2025, Спрингер, номер документа : 10.1007/3-540-44969-8 , ISBN. 978-3-540-42062-0 , S2CID 1808286

Внешние ссылки

об алгоритмах принудительного рисования. Глава книги Стивена Г. Кобурова
Диссертация Дэниела Танкеланга о силовой компоновке графов

[1] Гранжан, Мартин (2015), «Введение в визуализацию данных, сетевой анализ в истории», Geschichte und Informatik 18/19 (PDF) , стр. 109–128

[2] Кобуров, Стивен Г. (2012), Spring Embedders и алгоритмы принудительного рисования графов , arXiv : 1201.3011 , Bibcode : 2012arXiv1201.3011K .

[3] Баннистер, MJ; Эппштейн, Д .; Гудрич, Монтана ; Тротт, Л. (2012), «Силовое рисование графов с использованием социальной гравитации и масштабирования», Proc. 20-й Международный Симп. Рисунок графика , arXiv : 1209.0748 , Bibcode : 2012arXiv1209.0748B .

[4] Чернобельский Р.; Каннингем, К.; Гудрич, Монтана ; Кобуров, С.Г.; Тротт, Л. (2011), «Рисование графика в стиле Ломбарди, управляемое силой», Proc. 19-й симпозиум по рисованию графов (PDF) , стр. 78–90 .

[dl88-5] Перейти обратно: ^а ^б де Леу, Январь (1988), «Сходимость метода мажорирования для многомерного масштабирования», Journal of Classification , 5 (2), Springer: 163–180, doi : 10.1007/BF01897162 , S2CID 122413124 .

[6] Восе, Аарон. «3D-просмотрщик филогенетического дерева» . Проверено 3 июня 2012 г.

[7] Харель, Дэвид ; Корен, Иегуда (2002), «Рисование графов методом многомерного встраивания», Труды 9-го Международного симпозиума по рисованию графов , стр. 207–219, CiteSeerX 10.1.1.20.5390 , ISBN 3-540-00158-1

[quigley+eades-8] Перейти обратно: ^а ^б Куигли, Аарон; Идс, Питер (2001), «FADE: рисование графов, кластеризация и визуальная абстракция», Труды 8-го Международного симпозиума по рисованию графов (PDF) , стр. 197–210, ISBN 3-540-41554-8 .

[9] «Галерея больших графов» . Проверено 22 октября 2017 г.

[10] Коллберг, Кристиан; Кобуров, Стивен; Награ, Ясвир; Питтс, Джейкоб; Уэмплер, Кевин (2003), «Система для графической визуализации эволюции программного обеспечения», Труды симпозиума ACM 2003 года по визуализации программного обеспечения (SoftVis '03) , Нью-Йорк, Нью-Йорк, США: ACM, стр. 77– 86, рисунки на стр. 212, номер домена : 10.1145/774833.774844 , ISBN 1-58113-642-0 , S2CID 824991 , Чтобы добиться эстетически приятного расположения графика, также необходимо использовать модифицированные силы Фрухтермана-Рейнгольда, поскольку метод Камады-Каваи сам по себе не обеспечивает удовлетворительных методов, а скорее создает хорошую приближенную структуру, так что Расчеты Рейнгольда позволяют быстро «привести в порядок» планировку.

[kk89-11] Перейти обратно: ^а ^б Камада, Томихиса; Каваи, Сатору (1989), «Алгоритм рисования общих неориентированных графов», Information Processing Letters , 31 (1), Elsevier: 7–15, doi : 10.1016/0020-0190(89)90102-6 .

[fr91-12] Перейти обратно: ^а ^б Фрухтерман, Томас М.Дж.; Рейнгольд, Эдвард М. (1991), «Построение графика путем принудительного размещения», Software: Practice and Experience , 21 (11), Wiley: 1129–1164, doi : 10.1002/spe.4380211102 , S2CID 31468174 .

[13] ttp://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Многоуровневый алгоритм для принудительного управленияРисование графиков

[14] Тутте, WT (1963), «Как нарисовать график», Proceedings of the London Mathematical Society , 13 (52): 743–768, doi : 10.1112/plms/s3-13.1.743 .

[15] Идс, Питер (1984), «Эвристика для построения графиков», Congressus Numerantium , 42 (11): 149–160 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]