Виды алгоритмов визуализации неориентированных графов

Поскольку социальный граф друзей пользователя ВКонтакте является неориентированным, то в этом разделе будет дано кратное описание алгоритмов, работающих именно с неориентированными графами. Существуют три базовых подхода к визуализации неориентированных графов: метод «планаризации», метод «ориентации» и метод «направленных сил» [8, c.63].

Суть метода «планаризации» в том, что если граф не является планарным (то есть имеет пересечения ребер в своей двухмерной проекции), он искусственно делается им. Для этого в точках пересечения ребер расставляются искусственные «псевдо» -вершины, а затем к графу может быть применен один из методов построения планарного графа.

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

В этой работе мы не будет подробно останавливаться ни на тех, ни на других вследствие того, что для визуализации социальных графов, представляющих фрагменты реальных социальных сетей, повсеместно применяется третий вид алгоритмов — метод «направленных сил», или «Force-directed method/approach» в англоязычной литературе. В его основе лежит следующий принцип. Во-первых, задается случайное начальное состояние физической системы, состоящей из пружин (ребер) и металлических колец (вершин). Деформированные пружины приводят систему в движение. Происходят колебания, приводящие к изменению деформации пружин и положения колец-вершин. Когда система достигнет минимального энергетического состояния, работа алгоритма будет завершена (Кобуров, 2012).

Рисунок 7. Сжатия и растягивания пружин.

Рисунок 8. Демонстрация работы метода «направленных сил» .

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