Триадно-транзитивная информационно-управляющая рекомендательная система для социальной сети (Twitter)

Twitter was developed with using the methods of triadic-transitive analysis and subject headings of user’s messages.

Keywords: social networks, twitter, recommendation systems

Разработана структура рекомендательной системы для социальной сети Twitter с использованием методов триадно-транзитивного анализа и определения тематики сообщений.

Ключевые слова: социальные сети, twitter, рекомендательные системы.

В последние годы большую популярность приобрели социальные сети, дающие возможность зарегистрированным в них пользователям, взаимодействовать между собой. Одной из таких сетей, является система микроблогов «Twitter» [4], позволяющая своим пользователям отправлять короткие (до 140 символов) текстовые сообщения, которые могут увидеть другие пользователи. Сообщения можно получать и отправлять через браузер, SMS, сторонние клиенты для различных устройств.

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

Существует также следующие возможности взаимодействия:

1.Ответить на сообщение. При прочтении сообщения пользователи будут видеть, на какое сообщение был написан ответ.

2.Упомянуть другого пользователя в своем сообщении. Для этого перед именем пользователя ставится знак «@»

3.Ретвит - ретрансляция сообщения другого пользователя своим подписчикам с указанием первоисточника.

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

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

На рис. 1 представлена структурная схема рекомендательной системы для выявления источников информации, которые могут быть интересны целевому пользователю. Система предоставляет возможность пользователю, запрашивающему рекомендацию, уточнять информацию о связях (например, отвечая на вопросы «Пользователи X, Y, Z - ваши коллеги?», «Больше не рекомендовать пользователя Y?»), обозначая, таким образом, свои приоритеты.

Первоначальной задачей является выявление данных о пользователе – получение списков его подписчиков и источников информации, личных данных (пол, страна, город, понятные ему языки), его сообщений. Средством для получения этих данных является программный интерфейс приложения Twitter API [5].

Рисунок 1. Структура рекомендательной системы

Подключение к TwitterAPI происходит через протокол OAuth, который позволяет предоставить доступ к защищенным ресурсам (в данном случае списки источников и подписчиков, а так же списки сообщений, в случае защищенного(private) аккаунта) без ввода имени пользователя и пароля twitter-аккаунта в рекомендательной системе – это связывание происходит на стороне сервера twitter.com. После связывания, рекомендательная система получает информацию о пользователе. Все полученные данные заносятся в базу данных рекомендательной системы.

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

После получения списка подписчиков и источников, особое внимание стоит уделить пользователям, с которыми исходный пользователь имеет взаимные связи. Эти связи в сети Twitter часто образуются на основе существующих связей в реальной жизни или сети Интернет, и, иногда, образуются в соответствии с явлением взаимного обмена [1], не отражая при этом сущность взаимной связи в социальных сетях – взаимный обмен вниманием между пользователями. В таких случаях уточнить силу связей между пользователями помогает накопленный опыт взаимодействия между ними – ответы, упоминания, ретвиты и классификация исходным пользователем своих «друзей» в сети Twitter. Пользователю достаточно отметить группы своих коллег, однокурсников или одноклассников, а так же группу людей, которых он знает в реальной жизни, не входящих в первую категорию.

В связи с низким лимитом на количество разрешенных в час запросов в TwitterAPI (350 для аутентифицированных пользователей), для получения данных о подписчиках и источниках второго уровня удаленности от исходного пользователя используется интерфейс социального графа GoogleSocialGraphAPI[6], который позволяет делать 30 тысяч запросов в день.

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

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

Стемминг представляет собой нахождение основы слова (которая не обязательно совпадает с его корнем) для заданного слова. Лемматизация – приведение исходного слова к его нормальной грамматической форме.

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

На втором этапе проводится сопоставление полученных форм с базой терминов. Стоит учитывать специфику формата сообщений – они всегда короткие и, как правило, написаны в разговорном стиле. В отличие от текстов большой длины, где ошибка в определении рубрики для отдельного слова не столь весома, в коротких текстах такая ошибка может повлечь за собой неверное определение тематики сообщения. Чтобы этого не происходило, нужно устранить имеющиеся в базе данных неточности в определении соответствия терминов и рубрик, уделить особое внимание многозначным терминам и омонимам, учесть собственные имена – такие как названия фильмов, мест, персоналий и т.д. Для устранения неточностей в базе терминов хорошо подходит тестирование ее на таких же коротких сообщениях [3].

По результатам рубрикации сообщений пользователям сопоставляются ключевые для них тематики и проводится коллаборативная фильтрация по схожести пользователей. Отобранные пользователи получают дополнительные веса в социальном графе.

После того, как были получены все необходимые данные о связях между пользователями в сети Twitter, мы можем построить ориентированный антирефлексивный граф и произвести для него триадно-транзитивный анализ. Такой анализ заключается в нахождении триад в соответствии с выделенными в работе [2] шаблонами: общие интересы, общая аудитория, транзитивность и фильтрация, обоюдность и взаимность.

Шаблон общие интересы характеризуется тем, что связи образовываются вокруг какого-то общего интереса или источника информации. При увеличении числа источников, которые разделяют два пользователя, возрастает вероятность, что они будут друг для друга полезными источниками информации.

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

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

Шаблон обоюдность и взаимность между двумя пользователями применим тогда, когда оба пользователя являются и подписчиками и источниками информации друг для друга. Если между пользователями, входящими в триаду, уже установлены две обоюдные связи, велика вероятность, что образуется третья обоюдная связь. Такое явление носит название триадное замыкание [7]. Взаимность показывает, сколько внимания уделяют друг другу пользователи, исходя из опыта взаимодействия между ними.

После выделения структур в графе, на него накладываются дополнительные веса из коллаборативной фильтрации пользователей и опыта взаимодействия. В соответствии с математической моделью, а так же предпочтениями пользователя (пол, язык, страна, город источника), для него формируются рекомендации. Начальные данные для той части математической модели, которая отвечает за обработку структуру связей, основываются на статистических данных эксперимента из [2].

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

Список информационных источников

1. Cialdini, R. B. (2001). Influence: Science and practice (4th ed.). Boston: Allyn & Bacon.

2. Scott A. Golder and Sarita Yardi. “Structural Predictors of Tie Formation in Twitter: Transitivity and Mutuality.” Proceedings of the Second IEEE International Conference on Social Computing. August 20-22, 2010. Minneapolis, MN.

3. Белов А. А., Волович М. М. Автоматическое распознавание тематики сверхкоротких текстов - http://www.dialog-21.ru/dialog2007/materials/html/05.htm (дата обращения 25.02.2011)

4. About Twitter - http://twitter.com/about/ (дата обращения 25.02.2011)

5. Twitter API Documentation - http://dev.twitter.com/doc (датаобращения 25.02.2011)

6. About the Social Graph API - http://code.google.com/intl/ru/apis/socialgraph/docs/ (датаобращения 25.02.2011)

7. Triadic Closure - http://en.wikipedia.org/wiki/Triadic_closure (дата обращения 25.02.2011)