Визуализация сильно связных неориентированных графов в трехмерном пространстве с помощью адаптации силового алгоритма

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

Основной проблемой при визуализации графов является расположение вершин  и дуг относительно друг друга таким образом, чтобы они не перекрывали друг друга, а также, по возможности, не пересекались. Это можно решить с помощью нескольких подходов: силового, спектрального, метода связывания и других. В данной работе использовался силовой алгоритм Фруктермана-Рейнгольда. Но, поскольку сам алгоритм изначально был разработан для расположения графа на плоскости, была осуществлена его адаптация для трехмерного пространства. Смысл алгоритма: для нахождения оптимальных координат в пространстве мы представляем вершины как атомарные частицы, которые притягиваются и отталкиваются друг от друга. У вершин есть определенное начальное расположение и заданная свобода движения. В результате  работы алгоритма, система, обладающая определённым уровнем энергии постепенно «остывает» и приходит в состояние равновесия. Поскольку сила является отрицательным градиентом энергии, то положение равновесия соответствует локальному минимуму энергии.

(a)	(b)

Рис. 1 - Результаты визуализации (а) граф 10 вершин, (б) граф 15 вершин.

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

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

Научный руководитель: с.н.с. Центра распределенных вычислений ИППИ РАН, к.т.н. Курочкин И.И.