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

Виды алгоритмов визуализации неориентированных графов Поскольку социальный граф друзей пользователя ВКонтакте является неориентированным, то в этом разделе будет дано кратное описание алгоритмов, работающих именно с неориентированными графами. Существуют три базовых подхода к визуализации неориентированных графов: метод «планаризации», метод «ориентации» и метод «направленных сил» [8, c. 63]. Суть метода «планаризации» в том, что если граф не является планарным (то есть имеет пересечения ребер в своей двухмерной проекции), он искусственно делается им. Для этого в точках пересечения ребер расставляются искусственные «псевдо»-вершины, а затем к графу может быть применен один из методов построения планарного графа. Метод «ориентации» основан по тому же принципу: производится искусственное преобразование неориентированного графа в ориентированный, после чего к графу может быть применен один из методов визуализации ориентированных графов. В этой работе мы не будет подробно останавливаться ни на тех, ни на других вследствие того, что для визуализации социальных графов, представляющих фрагменты реальных социальных сетей, повсеместно применяется третий вид алгоритмов – метод «направленных сил», или «Force-directed method/approach» в англоязычной литературе. В его основе лежит следующий принцип. Во-первых, задается случайное начальное состояние физической системы, состоящей из пружин (ребер) и металлических колец (вершин). Деформированные пружины приводят систему в движение. Происходят колебания, приводящие к изменению деформации пружин и положения колец-вершин. Когда система достигнет минимального энергетического состояния, работа алгоритма будет завершена (Кобуров, 2012). Рисунок 7. Сжатия и растягивания пружин Рисунок 8. Демонстрация работы метода «направленных сил» В следующем пункте будет приведен перечень различных алгоритмов визуализации графа, использующих метод «направленных сил». Force-directed алгоритмы Алгоритм «Frushterman-Reingold» был разработан в 1991 году Томасом Фруштерманом и Эдвардом Рейнгольдом (Фруштерман и Рейгольд, 1991). Сложность алгоритма O (N^2). Он позволяет эффективно строить двумерные представления графов, в которых содержится не более 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 (N^2), что позволяет обработать графы с числом вершин от 1 до 10 000 (именно такие ограничения имеет число друзей пользователя ВКонтакте). Если ребра графа имеют вес, он будет учтен при построении. При проектировании «Force Atlas» был сделан акцент на качестве визуализации, что делают раскладку графа, получающуюся на выходе максимально наглядной. Рисунок 11. Результат работы алгоритма «Force Atlas» Эмпирически было установлено, что многие естественно возникающие сети (такие как социальные, коммуникационные и биологические графы) хорошо моделируются безмасштабными сетями, то есть сетями, в которых степени вершин распределены по степенному закону (Бонатоа, Хадиб, Хорнк, Прахалад, Ванж, 2009). Вышеперечисленные характеристики стали причиной, по которой для визуализации социального графа пользователя ВКонтакте была выбрана библиотека, реализующая алгоритм направленных сил «Force Atlas».

Похожие:

	Программа дисциплины «Сценарный трейдинг» Правительство Российской... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное...
	Правительство Российской Федерации Федеральное государственное автономное...		Правительство Российской Федерации Федеральное государственное автономное...
	Правительство Российской Федерации Государственное образовательное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования
	Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования		Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования