Силовые алгоритмы

Силовые алгоритмы (force-directed algorithms) размещения графов на плоскости или в пространстве относятся к алгоритмам изображения графа, основанным на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.

Постановка задачи

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

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

Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства:

1. Между вершинами графа должно быть достаточно расстояния.
2. Связанные вершины должны находится рядом с друг другом, не связанные в отдалении.

Алгоритмы

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

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

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

• Алгоритм Идеса (P.Eades)
• Алгоритм Фрюхтермана-Рейнгольда (T.Fruchterman, S.Reingold)
• Алгоритм Камада-Кавай (T.Kamada, S.Kawai)
• Метод барицентров Тутте (W.Tutte)

Применение и реализации

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

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

D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата.

VivaGraphJS предназначен для расширения и поддержки различных механизмов рендеринга и алгоритмов размещения графов. Позволяет размещать граф с помощью силового алгоритма, позволяя задавать параметры.

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

Открытые проблемы

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

Литература

• Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p.
• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.