Графы, Нейронные сети

Метод укладки Gephi. Метод Фрухтермана-Рейнгольда и Openord

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

Метод Фрухтермана-Рейнгольда является алгоритмом с силовым подходом. Он требует длительного времени выполнения. Для реализации этого метода Gephi предоставляет несколько простых функций. Вместо настроек отталкивания и притяжения Фрухтерман-Рейнгольд использует один. Функция Область действует как среднее между двумя методами и максимально равномерно распределяет узлы, что обеспечивает примыкание кластеров друг к другу. Предоставление одной функции вместо двух создаёт большую зависимость от алгоритма и меньшую от конечного пользователя, так что нужно учитывать это ограничение, если вы выберете этот метод.

Рис. 1. Результат применения метода Fruchterman Reingold. Область10000, гравитация 10

И снова мы сталкиваемся с функцией Гравитация, более высокие значения которой вытягивают сеть к центру графа. Если задать значение этот параметра 0, то узлы будут тяготеть к центрам отдельных кластеров.

Рис. 2. Результат применения метода Fruchterman Reingold. Область1000, гравитация 0

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

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

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

жидкость(Liquid), расширение(Expansion), охлаждение(Cooldown), сжатие(Crunch) и кипячение(Simmer).

На каждом этапе варьируется несколько параметров оптимизации: температура, притяжение и демпфирование (гашение колебаний). Эти параметры определяют, насколько далеко вершины могут перемещаться. На каждом шаге алгоритма мы вычисляем два возможных хода вершины. Первый возможный ход — это всегда случайный прыжок, расстояние до которого определяется температурой. Второй возможный ход рассчитывается аналитически. Этот ход рассчитывается как взвешенный центр соседних вершин. Множитель демпфирования определяет, как далеко до этого центра вершине разрешено двигаться, а коэффициент притяжения определяет желательность такого движения. Из этих двух возможных ходов мы выбираем ход, который дает наименьшую внутреннюю суммарную энергию.

Конечный вид графа определяется тем, сколько времени затрачивается на каждый этап. По умолчанию проводится около 25% времени в стадии жидкости, 25% на стадии расширения, 25% на стадии охлаждения, 10% на стадии сжатия и 15% на стадии кипения.

Рис. 3. Результат применения метода Openord. Liquid 25%, Expansion 25%, Cooldown 25%, Crunch 10%, Simmer 15%

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

Рис. 4. Результат применения метода Openord. Liquid 100%, Expansion25%, Cooldown 25%, Crunch 10%, Simmer 15%
Рис. 5. Результат применения метода Openord. Liquid 25%, Expansion 100%, Cooldown 25%, Crunch 10%, Simmer 15%
Рис. 6. Результат применения метода Openord. Liquid 25%, Expansion 75%, Cooldown 25%, Crunch 10%, Simmer 15%
Рис. 7. Результат применения метода Openord. Liquid 25%, Expansion 25%, Cooldown 100%, Crunch 10%, Simmer 15%

На этапах сжатия и кипения используется более низкая температура (примерно 1/4 температуры, используемой во время предыдущих этапов), а также более низкое притяжение и демпфирование.

Рис. 8. Результат применения метода Openord. Liquid 25%, Expansion 25%, Cooldown 25%, Crunch 100%, Simmer 15%
Рис. 9. Результат применения метода Openord. Liquid 25%, Expansion 25%, Cooldown 25%, Crunch 10%, Simmer 100%

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

Настройка Edge Cut дает пользователям возможность диктовать, как обрабатываются края. Значение 0 может привести к тому, что кластеры примыкают друг к другу или перекрывают друг друга.

Рис. 10. Результат применения метода Openord. Edge Cut 0

Установка более высоких значений позволяет увеличить пустое пространство между кластерами и сделать его более визуально привлекательным.

Рис. 11. Результат применения метода Openord. Edge Cut 1

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

Fixed time настраивает время фиксации — время, когда вершины не будут двигаться. 0 означает, что они не будут зафиксированы и 1, то что они будут оставаться зафиксированными.

Окончательный вид графа можно изменить случайно, задав значение Random seed.

Советуем почитать