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

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

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

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

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

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

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

Алгоритмы

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

На первом этапе вершины размещаются на плоскости случайным образом.

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

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

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

• Алгоритм Eades
• Алгоритм Фрюхтермана-Рейнгольда (Fruchterman-Reingold)
• Алгоритм Камада-Кавай (Kamada and Kawai)
• Метод Барицентров Тутте (Tutte’s 1963 barycentric method)

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

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

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

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

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

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

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

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

Литература

1. Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p.