Скачать 216.05 Kb.
|
Особенности реализации программыКлиентская часть веб-приложения выполняет большую часть его функционала, а именно:
Рисунок 12. Интерфейс управления построением графа Рисунок 13. Настройки визуализации графа Таблица 2. Описание настроек визуализации
Рисунок 14. Пример сформированного HTTP-POST запроса для получения персональных данных
Рисунок 15. Полученные данные пользователя Рисунок 16. Полученные списки друзей пользователей
Рисунок 17. Построенное представление социального графа
Рисунок 18. Рассчитанные характеристики социального графа Изначально был выбран подход, реализующий все функции по работе с графом (за исключением его конечной визуализации) на сервере. Однако он не оправдал себя в ходе экспериментов: приложение ожидало ответа значительное время (в среднем не менее 40 секунд). Вынесение задач по формированию графа на клиентскую часть позволило значительно сократить время ожидания до отклика программы. В дополнение к этому процесс работы алгоритма «направленных сил» над графом стал более наглядным. Серверная часть веб-приложения формирует запросы к методам API ВКонтакте, записывает собранные данные в базу данных и возвращает исходные данные о ребрах и вершинах социального графа на клиентскую часть. Для этого реализован PHP-скрипт «dispatcher.php», выполняющий роль диспетчера запросов. Получив и обработав входной запрос, он определяет, какому скрипту будет передано управление. Визуализация графа происходит на его клиентской части в несколько этапов. Сначала рисуется пользователь, его друзья и связывающие их связи. Рисунок 19. Строящийся социальный граф в первый момент времени Голубым цветом обозначаются участники сети мужского пола, розовым – женского, красным – пользователь, для которого строиться граф. Их связи обозначены серыми отрезками. Затем клиент посылает запрос серверу на получение списков друзей участников сети, сервер в свою очередь обращается к API ВКонтакте. Ответ он возвращается на клиентскую часть, которая, обработав его, ищет тех пользователей в полученных списках, которые представлены в построенном социальном графе. Они добавляются в граф. Рисунок 20. Масштабированный фрагмент социального графа Когда все связи добавлены, граф постепенно стабилизируется, достигая минимального энергетического состояния. Когда колебания достигнут порогового значения, они прекратятся, и алгоритм закончит выполнение. После этого можно подробно изучить сформированные кластеры графа, используя режим полноэкранного просмотра и масштабирование отдельных частей графа. Рисунок 21. Интерфейс для управления изображением графа Рисунок 22. Построенный социальный граф пользователя вцфв Рисунок 23. Социальный граф пользователя с выделенными кластерами Веб-приложении обеспечивает вычисление значений следующих социальных характеристик: гомогенность, центральность, плотность графа, расстояние. Гомогенность по признаку = число участников сети обладающим этим признаком/общее число участников сети. Соседство = процент людей, проживающим в том же городе или стране, что и пользователь, для которого был построен социальный граф. Общая гомогенность = среднее арифметическое всех рассчитанных показателей гомогенности по признаку и соседству. Центральность пользователя = число минимальных кратчайших путей между любыми двумя его друзьями, проходящими через него. Плотность графа = отношение реального числа связей в графе к максимально возможному в неориентированном графе с тем же числом вершин (оно вычисляется по формуле N * (N – 1) / 2, где N – число вершин графа). Число структурных пробелов = отсутствие связей между частями социального графа. Во всех построенных графах эти пробелы отсутствуют, так как пользователь является связующим звеном («мостом») между всеми его друзьями. Таким образом, не проводя расчетов, можно приравнять этот показатель к нулю. Расстояние = минимальное расстояние в графе между любыми двумя участниками. Так как во всех построенных графах каждый знает каждого через пользователя, то расстояние всегда будет не больше двух (друг №1 – пользователь – друг №2). Однако нужно проверить граф на полноту, так как в полном графе (все вершины имеют прямые связи друг с другом) расстояние равно единице. Для корректной работы веб-приложения может быть использован компьютер, имеющий мышь и характеристики не ниже следующих: однопроцессорный двухъядерный компьютер с 2 ГБ оперативной памяти и 4 ГБ дисковой памяти с выходом в интернет на скорости не менее 2 Mbit/сек. На клиентских рабочих местах должно быть установлено следующее ПО:
Само веб-приложение должно быть размещено на хостинге, имеющем стандартный набор параметров для обеспечения работы веб-сайтов с PHP-скриптами и СУБД MySQL. ЗаключениеВ ходе выполнения данной выпускной квалификационной работы было разработано клиент-серверное веб-приложение, решающие все поставленные задачи:
Программный продукт был снабжен документацией в составе:
Дальнейшие направления разработки включают в себя:
Список использованных источников[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 |
Программа дисциплины «Сценарный трейдинг» Правительство Российской... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... | ||
Правительство Российской Федерации Федеральное государственное автономное... | Правительство Российской Федерации Федеральное государственное автономное... | ||
Правительство Российской Федерации Государственное образовательное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | ||
Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | ||
Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | ||
Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | ||
Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | ||
Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | Правительство Российской Федерации Федеральное государственное автономное... Федеральное государственное автономное образовательное учреждение высшего профессионального образования |