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

Выявление требований к системе

• 
  Сбор данных пользователя социальной сети ВКонтакте, используя VK API (до 1000 друзей)
  
• 
  Визуализация списка его друзей в качестве социального графа
  
• 
  Расчет социальных характеристик, описанных в параграфе 3.4, для построенной сети
  

• 
  Реализация в виде клиент-серверного приложения
  
• 
  Стабильная работа на компьютерах с операционными системами Windows 7/8, Mac OS X, Linux при использовании последних версий браузеров Google Chrome, Mozilla Firefox, Яндекс.Браузер, Opera (число друзей до 1000 человек)
  
• 
  Хранение данных в базе данных MySQL
  
• 
  Реализация клиента на HTML/CSS с использованием JavaScript с библиотеками с использованием SVG
  
• 
  Реализация сервера на PHP, выполняемом на Apache-сервере
  

2. Алгоритмы визуализации графов

1. Общие сведения

2. Способы и критерии визуализации

• 
  Произвольное:
  

• 
  Полигональное – в нем для отображения ребер используются ломаные:
  

• 
  Прямолинейное – ребра изображаются отрезками:
  

• 
  Ортогональное – ребра – ломаные, состоящие из вертикальных и горизонтальных отрезков:
  

• 
  Сеточное – вершины расположены в узлах сетки:
  

• 
  Восходящее и нисходящее – применяется для изображения ориентированных графов. Показывает «поток» - направлением движения по графу (например, сверху вниз). Также этот способ позволяет наглядно визуализировать иерархические отношения (например, генеалогическое древо) вершин:
  

• 
  Минимизация числа пересечений ребер
  
• 
  Минимизация пространства занимаемого изображением графа (размеров областей графа)
  
• 
  Максимизация минимального угла между ребрами в графе
  
• 
  Универсальность длин ребер (минимизация различий между ними)
  
• 
  Минимизация числа изгибов ортогональных и наклонов полигональных отображений
  
• 
  Максимизация симметрии