Особенности реализации программы
Клиентская часть веб-приложения выполняет большую часть его функционала, а именно:
Предоставляет пользователю интерфейс по управлению программой (ввод исходных данных, проверка их корректности, ведение консольного журнала выполнения программы);
Рисунок 12. Интерфейс управления построением графа
Рисунок 13. Настройки визуализации графа
Таблица 2. Описание настроек визуализации
Настройка
|
Эффект на визуализацию
|
Диапазон допустимых значений
|
Длина пружин
|
Чем больше длина, тем на большем расстояния вершины графа будут расположены друг от друга
|
Действительное число в диапазоне [45; 500]
|
Коэффициент отталкивания
|
Чем выше, тем дальше друг от друга будут расположены вершины графа
|
Действительное число в диапазоне [-10; -0.1]
|
Максимальные колебания покоя
|
Чем выше значение, тем быстрее алгоритм прекратит работу(продолжительность колебаний графа)
|
Действительное число в диапазоне [0.005; 0.5]
|
Коэффициент упругости
|
Чем выше, тем меньше расстояние между вершинами и выше частота колебаний
|
Действительное число в диапазоне [0.000001; 0.00001]
|
Коэффициент сцепления
|
Чем выше, тем ниже амплитуда и частота колебаний (граф рисуется более плавно)
|
Действительное число в диапазоне [0.005; 0.09]
|
Режим сбора данных
|
Скорость получения информации о списках друзей пользователей и добавления новых ребер в граф: 25 списков друзей (список ребер инцидентных 25 вершинам) в секунду -быстрый режим, 1 список друзей – медленный
|
Быстрый / медленный
|
Формирует и посылает на сервер запрос в зависимости от стадии выполнения (сбор персональных данных главного пользователя, сбор данных его друзей, получение списков друзей);
Рисунок 14. Пример сформированного HTTP-POST запроса для получения персональных данных
Обрабатывает полученные с сервера ответы, динамически обновляя информацию о графе;
Рисунок 15. Полученные данные пользователя
Рисунок 16. Полученные списки друзей пользователей
Строит двухмерное представление социального графа;
Рисунок 17. Построенное представление социального графа
Рассчитывает социальные характеристики из параграфа [3.4]
Рисунок 18. Рассчитанные характеристики социального графа
Изначально был выбран подход, реализующий все функции по работе с графом (за исключением его конечной визуализации) на сервере. Однако он не оправдал себя в ходе экспериментов: приложение ожидало ответа значительное время (в среднем не менее 40 секунд). Вынесение задач по формированию графа на клиентскую часть позволило значительно сократить время ожидания до отклика программы. В дополнение к этому процесс работы алгоритма «направленных сил» над графом стал более наглядным.
Серверная часть веб-приложения формирует запросы к методам API ВКонтакте, записывает собранные данные в базу данных и возвращает исходные данные о ребрах и вершинах социального графа на клиентскую часть. Для этого реализован PHP-скрипт «dispatcher.php», выполняющий роль диспетчера запросов. Получив и обработав входной запрос, он определяет, какому скрипту будет передано управление.
Визуализация графа происходит на его клиентской части в несколько этапов. Сначала рисуется пользователь, его друзья и связывающие их связи.
Рисунок 19. Строящийся социальный граф в первый момент времени
Голубым цветом обозначаются участники сети мужского пола, розовым – женского, красным – пользователь, для которого строиться граф. Их связи обозначены серыми отрезками. Затем клиент посылает запрос серверу на получение списков друзей участников сети, сервер в свою очередь обращается к API ВКонтакте. Ответ он возвращается на клиентскую часть, которая, обработав его, ищет тех пользователей в полученных списках, которые представлены в построенном социальном графе. Они добавляются в граф.
Рисунок 20. Масштабированный фрагмент социального графа
Когда все связи добавлены, граф постепенно стабилизируется, достигая минимального энергетического состояния. Когда колебания достигнут порогового значения, они прекратятся, и алгоритм закончит выполнение. После этого можно подробно изучить сформированные кластеры графа, используя режим полноэкранного просмотра и масштабирование отдельных частей графа.
Рисунок 21. Интерфейс для управления изображением графа
Рисунок 22. Построенный социальный граф пользователя
вцфв
Рисунок 23. Социальный граф пользователя с выделенными кластерами
Веб-приложении обеспечивает вычисление значений следующих социальных характеристик: гомогенность, центральность, плотность графа, расстояние.
Гомогенность по признаку = число участников сети обладающим этим признаком/общее число участников сети. Соседство = процент людей, проживающим в том же городе или стране, что и пользователь, для которого был построен социальный граф. Общая гомогенность = среднее арифметическое всех рассчитанных показателей гомогенности по признаку и соседству.
Центральность пользователя = число минимальных кратчайших путей между любыми двумя его друзьями, проходящими через него.
Плотность графа = отношение реального числа связей в графе к максимально возможному в неориентированном графе с тем же числом вершин (оно вычисляется по формуле N * (N – 1) / 2, где N – число вершин графа).
Число структурных пробелов = отсутствие связей между частями социального графа. Во всех построенных графах эти пробелы отсутствуют, так как пользователь является связующим звеном («мостом») между всеми его друзьями. Таким образом, не проводя расчетов, можно приравнять этот показатель к нулю.
Расстояние = минимальное расстояние в графе между любыми двумя участниками. Так как во всех построенных графах каждый знает каждого через пользователя, то расстояние всегда будет не больше двух (друг №1 – пользователь – друг №2). Однако нужно проверить граф на полноту, так как в полном графе (все вершины имеют прямые связи друг с другом) расстояние равно единице.
Для корректной работы веб-приложения может быть использован компьютер, имеющий мышь и характеристики не ниже следующих: однопроцессорный двухъядерный компьютер с 2 ГБ оперативной памяти и 4 ГБ дисковой памяти с выходом в интернет на скорости не менее 2 Mbit/сек.
На клиентских рабочих местах должно быть установлено следующее ПО:
Операционная система Microsoft Windows Vista/7/8;
Все подсистемы рассчитаны на использование посредством современных ПК-версий веб-браузеров Google Chrome, Яндекс.Браузер, Mozilla Firefox и Opera, актуальных на 1 апреля 2014 года;
Для корректной работы необходима поддержка в браузерах SVG-графики, AJAX-запросов и скриптов языка Javascript.
Само веб-приложение должно быть размещено на хостинге, имеющем стандартный набор параметров для обеспечения работы веб-сайтов с PHP-скриптами и СУБД MySQL.
Заключение
В ходе выполнения данной выпускной квалификационной работы было разработано клиент-серверное веб-приложение, решающие все поставленные задачи:
Сбор социально-демографических данных пользователей сети ВКонтакте;
Построение на их основе социального графа;
Визуализация социального графа на плоскости в виде, пригодном для дальнейшего анализа;
Расчет характеристик социального графа.
Программный продукт был снабжен документацией в составе:
Техническое задание (ГОСТ 19.201-79)
Программа и методика испытаний (ГОСТ 19.301-79)
Руководство программиста (ГОСТ 19.505-79)
Текст программы (ГОСТ 19.401-78)
Дальнейшие направления разработки включают в себя:
Реализации возможности построения социальных графов пользователей других онлайн-социальных сетей;
Оптимизация работы программы при пятизначном числе вершин;
Разработка функционала для выявления и анализа кластеров социального графа;
Внедрение опции добавления в социальный граф новых пользователей.
Список использованных источников
[1] Goble, G., The History of Social Networking, DigitalTrends, 2012, URL: http://www.digitaltrends.com/features/ (retrieved date January 12, 2014)
[2] Sherman M., Implicit vs. explicit social graphs, Matt Sherman's blog of web, 2011, URL: http://clipperhouse.com/2011/06/19/implicit-vs-explicit-social-graphs/ (retrieved date February 3, 2014)
[3] Miller, R., Facebook Servers, Data Center Knowledge, 2012
[4] Носов В. И., Элементы теории графов, Новосибирск: СГУТИ, 2008
[5] Briggs, G., Building The Implicit Social Graph, The Moz Blog, 2011
[6] Abraham A., Hassanien A. E., Snášel V., Computational Social Network Analysis: Trends, Tools and Research Advances, London: Springer, 2009
[7] Russell, M. A., Mining the Social Web, O’Reilly Media, 2011
[8] I. F. Cruz, R. Tamassia, «How to Visualize a Graph: Specification and Algorithms», Tuffs University & Brown University, 1994
[9] Kobourov S. G., Spring Embedders and Force Directed Graph Drawing Algorithms, Cornell University Library of ARXIV, 2012
[10] Fruchterman, T. M. J., & Reingold, E. M., Graph Drawing by Force-Directed Placement. Software: Practice and Experience, 21(11), 1991
[11] Yifan Hu, «Efficient and High Quality Force-Directed Graph Drawing», Wolfram Research Inc, 2005
[12] Jacomy, M., Heymann, M., Venturini, T., Bastian, M., ForceAtlas2, A Graph Layout Algorithm for Handy Network Visualization, Sciencese Po medialab, Universite et Marie Curie, Gephi Consortium, 2007
[13] Bonatoa, A. & Hadib, N. & Hornc, P. & Prałatd, P. & Wange, C., Models of Online Social Networks. Internet Mathematics, 6(3), 285-313, 2009
[14] Krebs, V., Social Network Analysis, A Brief Introduction, Orgnetm, 2012, URL: http://www.orgnet.com/sna.html (retrieved date January 31, 2014)
[15] Ugander, J. & Karrer, B. & Backstrom, L. & Marlow, C. The Anatomy of the Facebook Social Graph. Cornell University Library of ARXIV, 2011
[16] Mishra, N. & Schreiber, R. & Stanton I. & Tarjan, R. E., Finding Strongly-Knit Clusters in Social Networks. Internet Mathematics, 5(1-2), 155-174, 2008
|
