Введение 3
Постановка задачи 5
Обзор литературы 6
Основные определения 7
Глава 1. Данные и работа с ними 8
1.1. Коллекция данных 8
1.2. Взаимосвязь между дружбой пользователей и их атрибутами 9
Глава 2. Работа с социальным графом 12
2.1. Эвристические алгоритмы 12
2.2. Результаты 14
2.3. Вывод 16
Глава 3. Метод обучения с частичным привлечением учителя .... 18
3.1. Описание метода 18
3.2. Решение задачи оптимизации 19
3.3. Машинное обучение 21
3.4. Результаты 27
3.5. Вывод 30
Глава 4. Задача линейного программирования 31
4.1. Постановка задачи 31
4.2. Решение задачи 32
4.3. Вывод 33
Анализ методов 34
Заключение 36
Список литературы 37
Приложение 39
В настоящее время распространенность и значимость социальных сетей весьма высока. Существует достаточно большое число различных площадок, которые охватывают разные сферы интересов человека. Некоторые из таких сетей небольшие, но узко специализированные, например, сообщество Executive.ru [1] объединяет менеджеров, которые заинтересованы в профессиональном росте и в получении новых знаний для повышении квалификации. Сообщество, по его данным, насчитывает около 300 тысяч пользователей. Среди широкого спектра различных социальных сетей находятся и известные крупные сети глобального характера. Среди русских сетей это, например, «Одноклассники» и «ВКонтакте», а среди мировых — «Facebook» и «Google+». В сети «ВКонтакте» по данным компании зарегистрировано более 350 миллионов пользователей [2], а «Facebook» ежемесячно посещают 1,59 млрд. активных пользователей по данным от 31 декабря 2015 года [3].
Крупнейших сетей по всему миру насчитывают в количестве около 22 штук [4]. В них люди взаимодействуют с другими пользователями, создают свой круг общения по интересам и обмениваются информацией. В социальной сети у каждого пользователя есть профиль — некоторая информация, доступная другим пользователям. Атрибутами профиля, например, могут быть: имя, фамилия, возраст, город, университет и др. К сожалению, многие пользователи не стремятся указывать полную информацию о себе, например, возраст в профиле может быть неверным или вовсе опущен. Данное обстоятельство затрудняет поиск новых друзей, а также ограничивает возможности в разных областях человеческой деятельности.
Многие владельцы бизнеса продвигают свои услуги и продукты в социальных сетях, создавая для этого отдельные страницы или предлагая их в переписке другим пользователям. Любая компания имеет свою целевую аудиторию, и для нее очень важно продвигать свой продукт заинтересованным людям.
Кроме того, социальные сети — это удобная площадка для проведения социологических исследований. Важнейшими параметрами в социологическом опросе являются пол и возраст человека. Определение возраста пользователей социальной сети позволит сформировать репрезентативную выборку, то есть каждый пользователь, вне зависимости от того, указал он свой возраст или нет, имеет шанс попасть в данную выборку. Таким образом в итоговой выборке будут присутствовать представители разных подгрупп, что обеспечивает правильность дальнейших расчетов и исследований.
Таким образом, наличие полной информации из профиля пользователя является важным критерием для успешной работы в самых разных сферах человеческой деятельности.
В рамках данной работы реализован и исследован общий метод определения скрытых атрибутов пользователей социальных сетей. Более того, проведены эксперименты на двух задачах: определение атрибутов пользователя по его эго-сети; определение атрибутов всех пользователей в рассматриваемом социальном графе.
В начале исследования проведен анализ социальных сетей, в результате которого выбрана наиболее подходящая сеть, а также отражен процесс загрузки данных и их хранение.
В ходе работы установлена зависимость между равенством атрибутов и дружбой пользователей, которая позволила разработать эвристические методы для определения атрибута пользователя на основе информации из его эгосети. Рассмотрен ряд недостатков этих методов и способ их устранения — метод обучения с частичным привлечением учителя. Для этого сформулирована оптимизационная задача, предложен способ ее решения и проведено исследование с различными метриками на двух поставленных задачах. Кроме того, в качестве возможного решения поставленных задач адаптирована задача линейного программирования и предложен способ ее решения.
В результатах работы отражен анализ предложенных методов для обеих поставленных задач. Метод обучения с частичным привлечением учителя показал наиболее точные результаты, достигая тем самым цели работы.
