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

Для эффективной работы с графами нужно знать различные типы укладки графов, а также их настройки. В этой статье мы рассмотрим одни из самых популярных методов – Force Atlas и Force Atlas 2.

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

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

Рассмотрите свои варианты с точки зрения целостности. Конечная цель создать граф, который не только понятен, но и позволяет рассказать убедительную историю. Если при достижении этих целей макет выглядит впечатляюще, даже лучше! Однако любое прочтение литературы и поиск в интернете быстро покажет, что многие графы выглядят впечатляюще, но не передают смысла данных, и они настолько плотны, что их невозможно прочитать. Не становитесь жертвой создания, чего-то впечатляющего, ради красивой картинки — всегда помните, что вы используете средство просмотра графов, и делаете все возможное, чтобы показать данные чётко. Теперь, когда мы определили приоритеты, мы можем перейти к рассмотрению различных компоновок Gephi.

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


Рис. 1. Граф переводов пользователей трёх различных банков

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

Сила отталкивания — это мера, позволяющая определить, насколько сильно каждый узел будет отталкивать другие узлы. Выставленный на высокие значения, этот параметр создаёт график с большим интервалом между узлами. Его можно использовать вместе с противоположным эффектом притяжения. Большие значения параметра сила притяжения сблизит соединенные узлы, что создаст сеть, которая потенциально более кластеризована. Конечно, в зависимости от лежащего в основе набора данных. Если ваша цель — создать граф, зависящий от изолированной группы внутри сети, то высокая сила притяжения в сочетании с высокой силой отталкивания может помочь нам добиться этого результата. Для наглядности так же можно задать размеры узлов в зависимости от исходящих рёбер.


Рис.2 Результат применения Force Atlas. Сила отталкивания 20000

Еще одна полезная функция, особенно когда важны размеры узлов — это флажок «Учитывать размер». Этот переключатель помогает алгоритму избегать перекрытия узлов или, наоборот, не брать в расчёт размер узла. Это очень полезно, когда у нас есть сеть с большими узлами, которые могут легко закрыть более мелкие узлы.


Рис. 3 Результат применения настройки «Учитывать размер»

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


Рис. 4 Результат применения настройки «Гравитация». Значение гравитации 30000.

Еще одна возможность — расположить крупные узлы подальше от центра графа с помощью флажка «Ослабление хабов». Когда установлен флажок «Да», алгоритм будет иметь тенденцию отодвигать крупные узлы от центра сети, обеспечивая несколько иную перспективу, чем традиционные макеты.


Рис. 5 Результат применения настройки «Ослабление хабов»

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

Force Atlas 2 — это более быстрая, обновленная версия Force Atlas. Здесь также можно настроить число потоков, что позволит вам воспользоваться преимуществами многоядерной обработки и даст вам большую мощность для построения макета. Значение по умолчанию — 2, но, очевидно, оно может быть увеличено в зависимости от возможностей вашей локальной машины.

Задать расстояние между узлами здесь можно с помощью настройки «Разреженность».


Рис.6 Результат применения Force Atlas 2. Разреженность 200.

Аналогом параметра «Учитывать размер» здесь будет параметр «Запрет перекрытия» можно использовать, чтобы более крупные узлы не перекрывали другие компоненты в сети.

Еще один интересный вариант — использовать настройку «Влияние весов рёбер» для управления внешним видом вашей сети. Значение 1.0 соответствует нормальному влиянию, а значение 0 сообщает алгоритму, чтобы он вообще не ссылался на веса ребер при вычислении компоновки.

Уровни выше единицы будут все больше зависеть от веса ребер, в результате чего сильно связанные узлы будут ближе друг к другу.


Рис.7 Результат применения настроек «Запрет перекрытия» и «Влияние весов рёбер»

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

Как и в большинстве макетов, ориентированных на силу, Force Atlas 2 содержит опцию «Гравитация», которая дает пользователям возможность тянуть узлы к центру графа (через более высокие настройки) или отодвигать их от центра, когда требуется лучшая видимость в центре сети. В сочетании с настройкой «Влияние весов рёбер» она позволяет отдельно выделить узлы с сильной связью.



Рис.8 Результат применения настроек «Гравитация» и «Влияние весов рёбер»

В качестве ещё одного примера, рассмотрим граф просмотра сотрудниками клиентов в разрезе отделов. Так как набор данных был большого объёма и требовалась большая скорость обработки, была использована укладка Force Atlas2. Для ускорения обработки, процесс был запущен на 4-х ядрах. Был установлен запрет перекрытий и выставлена высокая разреженность. Так же, для наглядности, было выставлено ослабление хабов.


Рис.9 Граф просмотра сотрудниками клиентов

Главное отличие рассмотренных методов укладки – скорость работы. Однако, другие настройки могут так же повлиять на ваш выбор. Но любое ваше решение должно быть принято в зависимости от вашей задачи.