Силовые алгоритмы расположения вершин на плоскости - Визуализация графа цитирования

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

История силовых начинается с алгоритма Tutte в 1963 для планарных графов [8]. Однако современные подходы больше похожи на алгоритм, предложенный Peter Eades [9] в 1984. Основная идея была в том, чтобы представить вершины как стальные кольца, а ребра как пружины между ними. В начале работы алгоритма всем вершинам присваивалось случайное положение на плоскости. После этого запускалась симуляция физической системы, в которой силы упругости приводят систему в состояние с минимальной энергией. На рис. 1 схематично проиллюстрирована работа алгоритма такого типа.

работа силового алгоритма [7]

Рисунок 1. Работа силового алгоритма [7]

Также были сделаны два улучшения этой идеи. Первая состояла в том, чтобы использовать логарифмическую силу упругости, вместо обычной линейной (закон Гука), так как линейная зависимость оказалась слишком сильной; формула выглядит следующим образом:

,

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

,

Где - это константа, а - это расстояние между вершинами.

На каждом шаге алгоритма высчитывалась суммарная сила, действующая на каждую вершину, и потом вершина перемещалась на расстояние, где - маленькая константа (размер шага). Количество шагов также было константным.

В 1991 году Thomas Fruchterman и Edward Reingold улучшили этот алгоритм и в честь них он получил название Fruchterman-Reingold [10]. Этот алгоритм получил большую популярность и используется сейчас в таких больших системах и библиотеках как Gephi, graph-tool, d3, Boost Graph и другие.

Этот алгоритм имеет дополнительные наработки по сравнению с алгоритмом Eades. Во-первых, силы притягивания (силы упругости) и силы отталкивания считались немного по другому:

,

,

Где - это расстояние между вершинами, а - это оптимальное расстояние между ними, определяемая следующим образом:

,

Где - это константа, - это площадь рабочей области в которой должны находится все вершины, а - это количество вершин.

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

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

Похожие статьи




Силовые алгоритмы расположения вершин на плоскости - Визуализация графа цитирования

Предыдущая | Следующая