Force-directed алгоритмы.
Клиент-серверное веб-приложение
Алгоритм «Frushterman-Reingold» был разработан в 1991 году Томасом Фруштерманом и Эдвардом Рейнгольдом (Фруштерман и Рейгольд, 1991). Сложность алгоритма O (N2). Он позволяет эффективно строить двумерные представления графов, в которых содержится не более 1000 вершин. Для построения не используется вес ребер. Рисунок 10. Результат работы алгоритма «Yifan Hu Multilevel». Рисунок 9. Результат… Читать ещё >
Force-directed алгоритмы. Клиент-серверное веб-приложение (реферат, курсовая, диплом, контрольная)
Алгоритм «Frushterman-Reingold» был разработан в 1991 году Томасом Фруштерманом и Эдвардом Рейнгольдом (Фруштерман и Рейгольд, 1991). Сложность алгоритма O (N2). Он позволяет эффективно строить двумерные представления графов, в которых содержится не более 1000 вершин. Для построения не используется вес ребер.
Рисунок 9. Результат работы алгоритма «Frushterman-Reingold» .
Алгоритм «Yifan Hu Multilevel» был создан Йфаном Ху в 2005 году (Йфан, 2005). Его сложность O (N * log (N)). Ограничение на размер графа: 100 — 100 000 вершин. Также, как и в предыдущем алгоритме, вес ребер не задействован. Алгоритм работает значительно быстрее предшественника, так как для расчета отталкивающих сил вершин используются силы отталкивания кластеров от вершин. В силу роста производительности алгоритм теряет в точности визуализации. Еще одной его особенностью является автоматическая остановка по достижении колебаний минимального порогового значения.
Рисунок 10. Результат работы алгоритма «Yifan Hu Multilevel» .
Алгоритм «Force Atlas» разработан создателями Gephi в 2007 для визуализации безмасштабных сетей (графы, в которых степени вершин распределены по степенному закону) (Джакоми, Хэйман, Вентурини, Бастиан, 2007). Сложность составляет O (N2), что позволяет обработать графы с числом вершин от 1 до 10 000 (именно такие ограничения имеет число друзей пользователя ВКонтакте). Если ребра графа имеют вес, он будет учтен при построении. При проектировании «Force Atlas» был сделан акцент на качестве визуализации, что делают раскладку графа, получающуюся на выходе максимально наглядной.
Рисунок 11. Результат работы алгоритма «Force Atlas» .
Эмпирически было установлено, что многие естественно возникающие сети (такие как социальные, коммуникационные и биологические графы) хорошо моделируются безмасштабными сетями, то есть сетями, в которых степени вершин распределены по степенному закону (Бонатоа, Хадиб, Хорнк, Прахалад, Ванж, 2009). Вышеперечисленные характеристики стали причиной, по которой для визуализации социального графа пользователя ВКонтакте была выбрана библиотека, реализующая алгоритм направленных сил «Force Atlas» .