Силовые алгоритмы визуализации графов

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

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

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

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

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

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

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

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

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

Результаты хорошего качества

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

Гибкость

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

Интуитивность

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

Простота

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

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

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

Строгая теоретическая поддержка

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

Главные недостатки силовых алгоритмов:

Большое время работы

Типичные силовые алгоритмы в общем случае, как считается, имеют время работы, эквивалентные O(n³), где n — число узлов входного графа. Это потому, что число итераций оценивается в O(n), а на каждой итерации необходимо просмотреть все пары узлов и вычислить взаимные силы отталкивания. Это похоже на задачу N-тел в физике. Однако, поскольку силы отталкивания локальны по природе, граф может быть разбит так, что будут рассматриваться только соседние вершины. Основные техники, использованные алгоритмами для определения размещения узлов больших графов, включают вложения высокой размерности^[7], многоуровневые представления и другие методы, связанные с моделированием задачи n тел^[англ.]. Например, основанный на моделировании Барнса-Хата^[англ.] метод FADE^[8] может улучшить время работы до n*log(n) на итерацию. В качестве грубой оценки, за несколько секунд можно ожидать рисования максимум 1000 узлов в стандартной технике n² на итерацию и 100 000 с техникой n*log(n) на итерацию^[8]. Силовые алгоритмы, когда они комбинируются с многоуровневым подходом, могут рисовать графы с миллионами узлов ^[9].

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

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

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

Комбинацию сил притяжения смежных вершин графа и сил отталкивания для всех вершин первым использовал Идс^[16][17]. Ещё одну пионерскую работу по этому типу силового размещения опубликовали Фрухтерман и Рейнгольд^[18]. Идея использования лишь сил пружин между всеми парами вершин с идеальными длинами пружин, равными расстоянию по графу, принадлежит Камаде и Каваи^[19][11].

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

• Martin Grandjean. Introduction à la visualisation de données, l'analyse de réseau en histoire // Geschichte und Informatik 18/19. — 2015.
• Stephen G. Kobourov. Spring Embedders and Force-Directed Graph Drawing Algorithms. — 2012. — Bibcode: 2012arXiv1201.3011K. — arXiv:1201.3011.
• Bannister M. J, Eppstein M. J., Goodrich M. T., Trott L. Force-directed graph drawing using social gravity and scaling // Proc. 20th Int. Symp. Graph Drawing. — 2012.
• Chernobelskiy R., Cunningham K., Goodrich M. T., Kobourov S. G., Trott L. Force-directed Lombardi-style graph drawing // Proc. 19th Symposium on Graph Drawing. — 2011.
• Jan de Leeuw. Convergence of the majorization method for multidimensional scaling // Journal of Classification. — Springer, 1988. — Т. 5, вып. 2. — С. 163—180. — doi:10.1007/BF01897162.
• David Harel, Yehuda Koren. Graph drawing by high-dimensional embedding // Proceedings of the 9th International Symposium on Graph Drawing. — 2002. — С. 207—219. — ISBN 3-540-00158-1.
• Aaron Quigley, Peter Eades. FADE: Graph Drawing, Clustering, and Visual Abstraction // Proceedings of the 8th International Symposium on Graph Drawing. — 2001. — С. 197—210. — ISBN 3-540-41554-8. Архивная копия от 21 мая 2006 на Wayback Machine
• Christian Collberg, Stephen Kobourov, Jasvir Nagra, Jacob Pitts, Kevin Wampler. A System for Graph-based Visualization of the Evolution of Software // Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03). — New York, NY, USA: ACM, 2003. — С. 77—86; figures on p. 212. — ISBN 1-58113-642-0. — doi:10.1145/774833.774844. Цитата: Для получения эстетически приятного размещения графа необходимо использовать модифицированные силы Фрухтермана — Рейнгольда, так как метод Камады — Каваи не даёт удовлетворительных результатов, но создаёт хорошее приблизительное размещение, из которого вычисления Фрухтермана — Рейнгольда могут быстро «доделать» размещение.
• Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13, вып. 52. — doi:10.1112/plms/s3-13.1.743.
• Peter Eades. A Heuristic for Graph Drawing // Congressus Numerantium. — 1984. — Т. 42, вып. 11.
• Thomas M. J. Fruchterman, Edward M. Reingold. Graph Drawing by Force-Directed Placement // Software – Practice & Experience. — Wiley, 1991. — Т. 21, вып. 11. — doi:10.1002/spe.4380211102.
• Tomihisa Kamada, Satoru Kawai. An algorithm for drawing general undirected graphs // Information Processing Letters. — Elsevier, 1989. — Т. 31, вып. 1. — doi:10.1016/0020-0190(89)90102-6.

• Giuseppe di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1999. — ISBN 978-0-13-301615-4.
• Drawing graphs: methods and models / Michael Kaufmann, Dorothea Wagner. — Springer, 2001. — (Lecture Notes in Computer Science 2025). — ISBN 978-3-540-42062-0. — doi:10.1007/3-540-44969-8.

• Визуализация на flash + исходники и описание
• Диссертация Даниэля Тункеланга о силовом размещении графа (доступны исходники на Github)
• Hyperassociative Map Algorithm
• Интерактивные алгоритмы рисования графа в реальном времени использованы в средстве онлайнового моделирования базы данных