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

Физическое моделирование для визуализации графиков

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

Визуализация ссылок между страницами вики с использованием принудительного макета.

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

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

Силы

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

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

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

Методы

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

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

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

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

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

Качественные результаты

По крайней мере, для графов среднего размера (до 50–500 вершин) полученные результаты обычно имеют очень хорошее качество, основанное на следующих критериях: равномерная длина ребер, равномерное распределение вершин и проявление симметрии. Этот последний критерий является одним из наиболее важных, и его трудно достичь с помощью любого другого типа алгоритма.

Гибкость

Алгоритмы, направленные на силу, можно легко адаптировать и расширить для удовлетворения дополнительных эстетических критериев. Это делает их наиболее универсальным классом алгоритмов рисования графов. Примеры существующих расширений включают расширения для ориентированных графов, рисования трехмерных графиков, ^[6] рисования кластерных графов, рисования ограниченных графов и рисования динамических графов.

Интуитивный

Поскольку они основаны на физических аналогиях обычных объектов, таких как пружины, поведение алгоритмов относительно легко предсказать и понять. Это не относится к другим типам алгоритмов рисования графиков .

Простота

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

Интерактивность

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

Прочная теоретическая база

В то время как в литературе и на практике часто появляются простые специальные алгоритмы, направленные на принуждение (поскольку их относительно легко понять), более аргументированные подходы начинают набирать обороты. Статистики решают подобные проблемы в многомерном масштабировании (MDS) с 1930-х годов, а физики также имеют долгую историю работы с соответствующими проблемами n тел - поэтому существуют чрезвычайно зрелые подходы. Например, подход мажорирования напряжений к метрическому MDS может быть применен к построению графика, как описано выше. Было доказано, что это сходится монотонно . ^[5] Монотонная сходимость, свойство, при котором алгоритм на каждой итерации снижает нагрузку или стоимость макета, важна, поскольку гарантирует, что макет в конечном итоге достигнет локального минимума и остановится. Графики демпфирования приводят к остановке алгоритма, но не могут гарантировать достижение истинного локального минимума.

Недостатки

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

Высокое время работы

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

Плохие локальные минимумы

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

История

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

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

Смотрите также

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

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

1. Гранжан, Мартен (2015), «Введение в визуализацию объектов, l'analyse de reseau en histoire», 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..
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
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, Чтобы добиться эстетически приятного расположения графика, необходимо также использовать модифицированные силы Фрухтермана-Рейнгольда, поскольку метод Камады-Каваи сам по себе не обеспечивает удовлетворительных методов, а скорее создает хорошую приближенную структуру, так что Расчеты Рейнгольда позволяют быстро «привести в порядок» планировку.
11. Камада, Томихиса; Каваи, Сатору (1989), «Алгоритм рисования общих неориентированных графов», Information Processing Letters , 31 (1), Elsevier: 7–15, doi : 10.1016/0020-0190(89)90102-6.
12. Фрухтерман, Томас MJ; Рейнгольд, Эдвард М. (1991), «Построение графика путем принудительного размещения», Software: Practice and Experience , 21 (11), Wiley: 1129–1164, doi : 10.1002/spe.4380211102, S2CID  31468174.
13. http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf Многоуровневый алгоритм для принудительного рисования графиков
14. Тутте, WT (1963), «Как нарисовать график», Труды Лондонского математического общества , 13 (52): 743–768, doi : 10.1112/plms/s3-13.1.743.
15. Идс, Питер (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

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

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