Программный модуль построения социальных графов сообществ сети "ВКонтакте"

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Программный модуль построения социальных графов сообществ сети «ВКонтакте»

Вронский К.А., Шеленок Е.А.

Вронский К. А. - студент группы ИС(аб)-71 кафедры «Автоматика и системотехника», Шеленок Е. А. - канд. техн. наук, доц. кафедры «Автоматика и системотехника.

В статье рассматривается разработка алгоритмического и программного обеспечение для построения социальных графов сообществ сети «ВКонтакте», позволяющее визуализировать получаемые результаты. В качестве инструментов решения задачи используются: положения теории графов, язык программирования Python, редактор исходного кода Visual Studio Code, визуализатор графов Gephi.

Ключевые слова: социальный граф, социальная сеть «ВКонтакте», теория графов, матрица смежности, модулярность, Python, Gephi.

Abstract: The article discusses the development of algorithmic- and software for building social graphs of the “vk.com” network communities, which allows to visualize the obtained results. The graph theory, the Python programming language, the source code editor Visual Studio Code and the graph visualizer Gephi are used as tools to solve the problem

Keywords: social graph, social network “vk.com”, graph theory, adjacency matrix, modularity, Python, Gephi.

Введение

Социальная сеть - это социальная структура, состоящая из узлов (обычно это лица или организации), которые связаны одним или более типами взаимозависимости, такими как: ценности, взгляды, мнения, идеи, дружба, финансовые взаимоотношения, конфликты, торговля и так далее. Аналитики социальных сетей оперируют терминами «узлы» и «связи».

Узел - это отдельный актор в пределах этой сети; связи - это отношения между узлами. Модель социальной сети может быть очень сложной: они включают в себя самые разные уровни связей от семейных до национальных и общечеловеческих. Социальные сети играют важную роль в том, как люди решают проблемы (например, выбор товара), функционируют организации, происходит личностный рост и развитие, обучение.

В самой простой форме социальная сеть это карта всех релевантных связей между узлами, и ее основу составляет социальный граф - явление, лежащее на стыке дискретной математики и социологии. Социальный граф представляет собой множество вершин, представляющих участников сети и различные виды социальных связей между ними. Возможны два вида связей: «явные», такие как друзья или коллеги, и «неявные», например, такие как одногруппники. Все пользователи с их историей переписки, фотографиями, видеофайлами и персональными данными хранятся в базах данных распределенных серверных кластеров.

В настоящее время одной из самых актуальных задач современной науки о данных является задача построения и визуализации социальных графов для различных сообществ или отдельных пользователей социальных сетей с целью анализа результатов по разным аспектам: социальным, культурным, профессиональным и другим. В настоящей работе с использованием языка Python, среды Visual Studio Code и редактора Gephi рассматриваются результаты проектирования программно-алгоритмического обеспечения системы построения социальных графов сообществ сети «ВКонтакте».

Социальные графы, сообщества и модулярность

К настоящему моменту времени четкого формального определения, какой граф можно называть социальным, не существует. Ясно, что в основе этого понятия лежит граф знакомств между людьми в некотором обществе. Можно сказать, что социальный граф -- это специальный вид графов, который характеризуется следующим набором свойств [1]:

Одна большая общая компонента связности, которая захватывает большинство вершин.

Распределение на степенях вершин. Социальные сети относятся к так называемым безмасштабным сетям (Scale-free network). Это означает, что количество вершин убывает [2].

Среднее расстояние. Социальные сети в среднем имеют очень маленькое расстояние между двумя случайными вершинами. Это свойство может быть продемонстрирована на модели современного общества. Существует так называемый феномен тесного мира (или теория шести рукопожатий), согласно которому любые два человека на планете разделены в среднем пятью уровнями общих знакомых и, соответственно, шестью уровнями связей.

Коэффициент кластеризации. Существует множество коэффициентов для графа, которые показывают некоторую его качественную характеристику. Обычно эту характеристику сравнивают с ее средним значением на случайном графе [1].

Структура сообществ. Коэффициент кластеризации показывает, насколько сильно вершины склонны образовывать группы (или сообщества), которые характеризуются тем, что вершины, входящие в одну группу, соединены между собой гораздо плотнее, чем со всем остальным графом. Если объединить вершины в сообщества, то можно без потери информации о структуре графа исследовать его на более абстрактном уровне. На рис. 1 первый граф (слева) имеет явные 3 сообщества, в то время как второй граф (справа) - нет.

Рис. 1. Пример графа, имеющего структуру сообществ (слева) и графа, не имеющего сообществ (справа)

где Ay - элементы матрицы смежности графа; diи dj степени i и j вершины графа; Ciи Cj -- метки вершины (номер сообщества, к которому относится вершина); m -- общее количество ребер в графе; ф(C, C. ) -- дельта-функция: равна единице, если Ci= Cj, иначе нулю.

Задача поиска выделения сообществ в графе сводится к поиску значений С,, максимизирующих значение модулярности.

Формула имеет множество обобщений, например, для взвешенных гра - фов, под Aj понимается вес ребра, соединяющего вершины іи j, а

Модулярность возможно эффективно пересчитывать при небольших изменениях в кластерах. Например, если добавить изолированную вершину в кластер С, то изменение функционала для взвешенного графа можно посчитать как

где ?tot- сумма весов ребер внутри сообщества С; ?tot- сумма весов всех ребер инцидентных вершинам из С; d, -- сумма весов ребер инцидентных вершине i; di?in-- сумма весов ребер соединяющих вершину d, и вершину из С; m-- сумма весов всех ребер [4].

Недостатками модулярности являются:

Функционал не является непрерывным, и задача его оптимизации - дискретная. Для поиска глобального оптимума используют приближенные схемы. Некоторые из них оптимизируют значение функционала, другие по значению модулярности выбирают наилучшее решение из найденных, то есть без гарантий локальной оптимальности решения.

Проблема разрешающей способности (невозможность анализа сообщества небольшого размера). Эта проблема решается путем использования модифицированного функционала, который сохраняет все достоинства и добавляет параметр масштабирования [5].

Инструментарий VKAPI

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

Если рассматривать «ВКонтакте» как источник необходимой информации для парсинга, можно столкнутся со следующими проблемными группами пользователей, которые не будут попадать в нашу выборку, по причине неактуальности или конфиденциальности данных: удаленные пользователи, не активные пользователи, пользователи с закрытым профилем.

На рис. 2 представлено предположительное изменение активности пользователей с течением времени [6].

Рис. 2. Возможное изменение активности пользователей с течением времени

API ВКонтакте (VKAPI) - это интерфейс, который позволяет получать информацию из базы данных сайта «vk.com» с помощью http-запросов к специальному серверу. Синтаксис запросов и тип возвращаемых ими данных строго определены на стороне самого сервиса, который установил ограничение на количество отправляемых запросов в секунду - 3 и в сутки - 3000

Например, для получения данных о пользователе с идентификатором 351601988 необходимо составить запрос такого вида:

https://api.vk.com/method/users .get?user_id=351601988&v=5.52

Рассмотрим отдельно все его составляющие.

С целью построения социальных графов сообществ и пользователей сети «ВКонтакте» было рарзаьотано программное обеспечение, основанное на возможностях инструментария VKAPI. В качестве целевых данных будут выступать социальный граф, визуализированный по одному из алгоритмов [7] и графики зависимостей центральностей от показателя ранжирования Пейджа [1] и файл формата «json», в котором будут храниться структурированные данные. Входными данными программы служат уникальная ссылка пользователя, либо ссылка сообщества (группы). Программа получает в теле запроса следующие данные: фамилия, идентификатор пользователя, имя, пол, город и данные об образовательном(-ых) учреждении(-иях). Анализ сообществ. Рассмотрим работоспособность алгоритма на примере анализа сообщества «Двигатель ФАИТ ТОГУ» (короткая ссылка «fait_ik»), состоящего из 273 человек. Процесс получения данных показан на рис. 3.

Рис. 3. Процесс получения данных подписчиков сообщества

Рис. 4. Графики зависимости центральностей от показателя ранжирования Пэйджа (сверху - центральность по степени и близости, снизу - центральность по посредничеству и влиятельности)

Рис. 5. Выходные данных о пользователях в файле «fait_ik.json»

Рис. 6.Выходные данных о пользователях в файле «fait ik.json»

Рис. 7. Результирующий граф

Рис. 8. Граф с выделением сообществ

Рис. 9. Граф с учетом мелких сообществ

Рис. 10. Граф с сортировкой по полу пользователей (зеленый - мужской, розовый - женский)

Рис. 11. Граф с сортировкой по университету пользователей

Рис. 12. Граф с сортировкой по городу проживания пользователей

Заключение

Разработано программно-алгоритмическое обеспечение на основе языка программирования Python с использованием инструментария VKAPIна основе данных профилей пользователей - подписчики сообщества (группы). Выполнен статистический анализ на основе отношений различных видов центральностей с показателями ранжирования Пейджа, что напрямую отражает корреляционные коэффициенты, которые показывают взаимосвязь между узлами графа. С использованием средств Gephi проведен визуальный анализ, позволяющий выделять в полученном графе сообщества с заданным разрешением (точностью), позволяя исследовать тот или иной круг лиц на отношение к определенной компании (сообществу), то есть предсказывать их.

Разработанное программное обеспечение способно в кратчайшие сроки получать необходимую для статистического и визуального анализа информацию разной степени заполненности.

Литература

1. 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).

2. Briggs G. Building the Implicit Social Graph, The Moz Blog, 2011.

3. Russell M. A. Mining the Social Web. - O'Reilly Media, 2011.

4. Cruz I.F., Tamassia R. How to visualize a graph: Specification and algorithms // Technical report Tufts University. - 1994.

5. Kobourov S. G. Spring embedders and force directed graph drawing algorithms. - 2012, Retrieved from http://arxiv.org/abs/1201.3011

6. Abraham A., Hassanien A. E., Snвsel V. Computational Social Network Analysis: Trends, Tools and Research Advances. - London: Springer, 2009.

7. Goble G., The History of Social Networking // Digital Trends. - 2012, URL: http://www.digitaltrends.com/features/ (retrieved date January 12, 2014).

Размещено на Allbest.ru