Русская Википедия:Силовые алгоритмы визуализации графов
Силовые алгоритмы визуализации графов — класс алгоритмов визуализации графов в эстетически приятном виде. Их цель — расположить узлы графа в двумерном или трёхмерном пространстве так, что все рёбра имели бы более-менее одинаковую длину, и свести к минимуму число пересечений рёбер путём назначения сил для множества рёбер и узлов основываясь на их относительных положениях, а затем путём использования этих сил либо для моделирования движения рёбер и узлов, либо для минимизации их энергииШаблон:Sfn.
В то время, как визуализация графов может оказаться трудной задачей, силовые алгоритмы, будучи физическими моделями, обычно не требуют специальных знаний в теории графов, таких как планарность графа.
Силы
Силовые алгоритмы визуализации графов назначают силы на множестве рёбер и узлов графа. Обычно используются подобные пружинным силы притяжения на основе закона Гука для назначения сил парам концов ребра графа. В то же время используются силы отталкивания, подобные отталкиванию электрически заряженных частиц на основе закона Кулона, чтобы разделить все пары узлов. Для получения равновесного состояния этой системы сил рёбра стремятся получить однородные длины (ввиду действия пружин), а узлы, не связанные ребром, стремятся расположиться поодаль друг от друга (ввиду действия сил отталкивания). Силы притяжения (рёбра) и силы отталкивания (узлы) могут быть определены с помощью функций, которые не основаны на физическом поведении пружин и частиц. Например, некоторые силовые системы используют пружины, силы которых меняются логарифмически, а не линейно.
Альтернативная модель рассматривает подобные пружинным силы для каждой пары узлов <math>(i,j)</math>, где идеальная длина <math>\delta_{ij}</math> каждой пружины пропорциональна расстоянию в графе между узлами i и j, а силы отталкивания не используются. Минимизация разницы (обычно, квадрата разницы) между евклидовым и идеальным расстоянием между узлами эквивалентна метрической задаче многомерного шкалирования.
Силовой граф может использовать силы, отличные от механических пружин и сил отталкивания зарядов. Сила, аналогичная гравитации, может быть использована для притяжения вершин в сторону фиксированной точки пространства рисования графа. Это может быть использовано для сведения различных компонент связности несвязного графа в одно целое, в противном случае эти части разлетелись бы друг от друга под действием сил отталкивания. Также это позволяет получить узлы с улучшенной центральной позицией в рисункеШаблон:Sfn. Это также может повлиять на расстояние между вершинами в одной компоненте связности. Аналоги магнитных полей могут быть использованы для ориентированных графов. Силы отталкивания можно расположить как на рёбрах, так и на узлах с целью избежать наложения или почти наложения в конечном рисунке. В рисунках с кривыми рёбрами, такими как дуги окружностей или сплайны, силы могут быть также расположены в контрольных точках этих кривых, например, чтобы улучшить угловое разрешениеШаблон:Sfn.
Методы
Как только силы на узлах и рёбрах определены, поведение всего графа под действием этих сил может быть итеративно промоделировано, как если бы это была физическая система. В такой ситуации силы, действующие на узлы, пытаются стянуть их ближе или оттолкнуть их друг от друга подальше. Это продолжается, пока система не придёт в состояние механического равновесия, то есть положение узлов не меняется от итерации к итерации. Положение узлов в этом состоянии равновесия используется для генерации рисунка графа.
Для сил, определённых из пружин, идеальная длина которых пропорциональна расстоянию в графе, мажорирование стресса даёт очень хорошее поведение (то есть монотонную сходимость)Шаблон:Sfn и математически элегантный путь минимизации этой разницы и, следовательно, к хорошему размещению вершин графа.
Можно также использовать механизмы, которые ищут минимум энергии более прямо, а не по физической модели. Такие механизмы, являющиеся примерами общих методов глобальной оптимизации, включают имитацию отжига и генетические алгоритмы.
Преимущества
Следующие свойства являются наиболее важными преимуществами силовых алгоритмов:
- Результаты хорошего качества
- По меньшей мере для графов среднего размера (до 50—500 вершин), полученные результаты обычно имеют очень хорошие рисунки графов по следующим критериям: однородность длин рёбер, равномерное распределение вершин и симметрия. Последний критерий наиболее важен и трудно достижим в других типах алгоритмов.
- Гибкость
- Силовые алгоритмы могут быть легко приспособлены и расширены для дополнительных эстетических критериев. Это делает алгоритмы более универсальными классами алгоритмов визуализации графов. Примерами существующих расширений являются алгоритмы для ориентированных графов, визуализация трёхмерных графовШаблон:R, кластерная визуализация графов, визуализация графов с ограничениями и динамическая визуализация графов.
- Интуитивность
- Поскольку алгоритмы основаны на физических аналогах привычных объектов, наподобие пружин, поведение алгоритмов относительно просто предсказать и понять. Этого нет в других типах алгоритмов визуализации графов.
- Простота
- Типичные силовые алгоритмы просты и могут быть реализованы в несколько строк кода. Другие классы алгоритмов визуализации, такие как алгоритмы на основе ортогональных размещений, обычно требуют куда больше работы.
- Интерактивность
- Ещё одним преимуществом этого класса алгоритмов является аспект интерактивности. При рисовании промежуточных этапов графа пользователь может проследить, как меняется граф, прослеживая эволюцию от беспорядочного месива в хорошо выглядящую конфигурацию. В некоторых средствах интерактивного рисования графа пользователь может отбросить один или несколько узлов из состояния равновесия и наблюдать миграцию узлов в новое состояние равновесия. Это даёт алгоритмам преимущество для динамических и Шаблон:Не переведено 5 систем визуализации графов.
- Строгая теоретическая поддержка
- В то время как простые силовые алгоритмы часто появляются в литературе и на практике (поскольку они относительно просты и понятны), начинает возрастать число более обоснованных подходов. Статистики решали подобные задачи в многомерном шкалировании (Шаблон:Lang-en, MDS) с 1930-х годов, а физики также имеют длинную историю работы со связанными задачами Шаблон:Не переведено 5, так что существуют вполне вызревшие подходы. Как пример, подход мажорирования стресса к метрическим MDS может быть применен для визуализации графа и в этом случае можно доказать монотонную сходимостьШаблон:Sfn. Монотонная сходимость, свойство, что алгоритм будет на каждой итерации уменьшать напряжение или цену размещения вершин, важно, поскольку это гарантирует, что размещение, в конечном счёте, достигнет локального минимума и алгоритм остановится. Глушение колебаний приводит к остановке алгоритма, но не гарантирует, что будет достигнут истинный локальный минимум.
Недостатки
Главные недостатки силовых алгоритмов:
- Большое время работы
- Типичные силовые алгоритмы в общем случае, как считается, имеют время работы, эквивалентные O(n3), где n — число узлов входного графа. Это потому, что число итераций оценивается в O(n), а на каждой итерации необходимо просмотреть все пары узлов и вычислить взаимные силы отталкивания. Это похоже на задачу N-тел в физике. Однако, поскольку силы отталкивания локальны по природе, граф может быть разбит так, что будут рассматриваться только соседние вершины. Основные техники, использованные алгоритмами для определения размещения узлов больших графов, включают вложения высокой размерностиШаблон:Sfn, многоуровневые представления и другие методы, связанные с Шаблон:Не переведено 5. Например, основанный на Шаблон:Не переведено 5 метод FADEШаблон:Sfn может улучшить время работы до n*log(n) на итерацию. В качестве грубой оценки, за несколько секунд можно ожидать рисования максимум 1000 узлов в стандартной технике n2 на итерацию и 100 000 с техникой n*log(n) на итерациюШаблон:Sfn. Силовые алгоритмы, когда они комбинируются с многоуровневым подходом, могут рисовать графы с миллионами узлов Шаблон:R.
- Плохие локальные минимумы
- Легко видеть, что силовой алгоритм даёт граф с минимальной энергией, в частности, это может быть лишь локальный минимум. Найденный локальный минимум может быть, во многих случаях существенно хуже глобального минимума, что приводит к представлению плохого качества. Для многих алгоритмов, особенно для тех, которые позволяют только движение градиентного спуска, на конечный результат может сильно влиять начальное положение, которое в большинстве случаев генерируется случайно. Проблема плохого локального минимума становится особенно важной при росте числа вершин графа. Комбинирование различных алгоритмов помогает решить эту проблемуШаблон:Sfn. Например, можно использовать алгоритм Камады — КаваиШаблон:Sfn для быстрой генерации приемлемого начального размещения, а затем алгоритм Фрухтермана — РейнгольдаШаблон:Sfn для улучшения положения соседних узлов. Другая техника получения глобального минимума — использование многоуровневого подхода Шаблон:R.
История
Силовые методы визуализации графов восходят к работе ТаттаШаблон:Sfn, в которой он показал, что полиэдральные графы могут быть нарисованы на плоскости с выпуклыми гранями путём фиксации вершин внешней грани планарного вложения графа в Шаблон:Не переведено 5, расположения подобных пружинам притягивающих сил на каждом ребре и позволения системе прийти в равновесное состояниеШаблон:Sfn. Ввиду простой природы сил в этом случае система не может застрять в локальном минимуме, а сходится к единственной глобальной оптимальной конфигурации. Ввиду этой статьи вложения планарных графов с выпуклыми гранями иногда называют вложениями Татта.
Комбинацию сил притяжения смежных вершин графа и сил отталкивания для всех вершин первым использовал ИдсШаблон:SfnШаблон:Sfn. Ещё одну пионерскую работу по этому типу силового размещения опубликовали Фрухтерман и РейнгольдШаблон:Sfn. Идея использования лишь сил пружин между всеми парами вершин с идеальными длинами пружин, равными расстоянию по графу, принадлежит Камаде и КаваиШаблон:SfnШаблон:Sfn.
См. также
- Cytoscape, программа для визуализации биологических сетей. Базовый пакет включает силовые размещения как один из встроенных методов.
- Шаблон:Не переведено 5, интерактивная визуализация и исследовательская платформа exploration для всех видов сетей и сложных систем, динамических и иерархических графов.
- Graphviz, программное средство, реализующее многоуровневый силовой алгоритм размещения (среди прочих других), способный обрабатывать очень большие графы.
- Шаблон:Не переведено 5, программное средство, реализующее большинство силовых алгоритмов размещения (GEM, LGL, GRIP, FM³).
- Шаблон:Не переведено 5
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга Шаблон:Wayback
- Шаблон:Книга Цитата: Для получения эстетически приятного размещения графа необходимо использовать модифицированные силы Фрухтермана — Рейнгольда, так как метод Камады — Каваи не даёт удовлетворительных результатоы, но создаёт хорошее приблизительное размещение, из которого вычисления Фрухтермана — Рейнгольда могут быстро «доделать» размещение.
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Литература для дальнейшего чтения
Ссылка
- Визуализация на flash + исходники и описание
- Диссертация Даниэля Тункеланга о силовом размещении графа (доступны исходники на Github)
- Hyperassociative Map Algorithm
- Интерактивные алгоритмы рисования графа в реальном времени использованы в средстве онлайнового моделирования базы данных
