Графы

Методы укладки Gephi. Yufan Hu и Yufan Hu Proportional

Время прочтения: 3 мин.

В предыдущих статьях были рассмотрены методы Force Atlas, Force Atlas2, Fruchterman Reingold и OpenOrd. Продолжим рассматривать различные методы укладки инструмента Gephi.

Алгоритм Yufan Hu дает более быстрые результаты по сравнению с другими методами, сосредоточив внимание на притяжении и отталкивании узлов, расположенных по соседству (а не делая расчёт для всей сети), что значительно снижает вычислительную нагрузку на локальную машину. Он также имеет то преимущество, что сам останавливается за счет метода адаптивного охлаждения, поэтому он может работать намного быстрее, чем такие методы, как Force Atlas.

Рис. 1. Результат применения метода Yufan Hu. Оптимальное расстояние 100, относительная сила 0.2

Данный алгоритм позволяет настроить Оптимальное расстояние, более высокие значения которого толкает узлы дальше друг от друга, без явной установки уровня отталкивания.

Рис. 2. Результат применения метода Yufan Hu. Оптимальное расстояние 1000, относительная сила 0.2

Так же для настройки отталкивания и притяжения узлов Yufan Hu использует комбинированную настройку под названием Относительная сила, которая изменяет соотношение между отталкиванием и притяжением. Увеличение этого параметра усиливает отталкивание и разнесение узлов. Уменьшение сближает узлы, так как притяжению придаётся больший вес, чем отталкиванию.

Рис. 3. Результат применения метода Yufan Hu. Оптимальное расстояние 100, относительная сила 5

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

В заключении хотелось бы подвести итог сравнением алгоритмов.

Имя алгоритмаСильные стороныСлабые стороныКогда использовать
Force AtlasВключает много вариантов настройки
и имеет высокий уровень точности
Может быть очень
медленным и не подходит для больших
сетей
Для анализа
сетевых графов
и для рассмотрения
поведения сети
Force Atlas 2Быстрее чем оригинал и может работать с очень большими сетямиНемного страдает
общая точность
Подходит для сетевого анализа
и исследований,
обнаружения
поведенческих
паттернов
Fruchterman-
Reingold
Точный и стремится
строить графы лёгкие для чтения
Очень
медленный и не подходит для больших
сетей
Хорошо подходит для
обобщенного
вида на малый
средний размер
сети
OpenOrdОчень
быстрый и может работать с очень большими сетями
Не очень
точен на
небольших сетях
Используется
для быстрого
понимания
большой сетевой
структуры
Yifan HuДостаточно быстр, по сравнению с другими методамиНе хватает опции для отдельной настройки
отталкивания и притягивания
Для быстрого просматривания
от малых и средних графов
Yifan Hu
Proportional
Обрабатывает
относительно
большие графы и
быстро работает
Даёт среднее качествоДля быстрого просматривания
от малых и средних графов
Советуем почитать