Главная / Учебные материалы / ЛЕКЦИОННЫЕ МАТЕРИАЛЫ / Лекция 9. Перспективы развития методов, направлений и инструментария исследований и моделирования в науках об обществе / Перспективные направления компьютерных исследований в социальных сетях

Перспективные направления компьютерных исследований в социальных сетях

Сервисы рекомендаций – прогнозирование наиболее вероятных новых связей подписки/дружбы, использования сервисов соцсетей

Конкурс Facebook
Одним из примеров такого рода исследований является конкурс Facebook [9,10], выложившей в качестве задачи анонимизированный социальный граф с числом тестируемых вершин 262 588, числом ребер в графе 9 437 519, и числом вершин в графе 1 862 220. Данный граф получен из реального графа (правда, оговорено, что это не граф Facebook) путем удаления части ребер. Задача состоит в том, чтобы для каждой из тестируемых вершин (т.е. тех самых 262 588), представить ранжированный список 10 других вершин, с которыми у них с наибольшей вероятностью должна была быть или будет связь, то есть фактически, восстановить удаленные ребра и спрогнозировать возникновение новых. Наиболее успешных в этом конкурсе авторов компания собирается пригласить на работу.

Имхонет
Аналогичные по проблематике направления исследований активно развиваются и в других сервисах с элементами социальных сетей. Так, например, подобные рекомендации по возможным «друзьям» предлагаются на российском рекомендательном ресурсе Имхонет [11], где в качестве базы данных для вычисления наиболее вероятных друзей («единомышленников») служит сходство оценок фильмов, книг, и т.п., а не анализ графов дружбы. На основе этих оценок Имхонет формирует статистическое представление о вкусе пользователя и подбирает людей со статистически схожими предпочтениями. В дальнейшем на основе оценко "единомышленников" строятся индивидуализировнные рекомендации по фильмам, книгам, путешествиям и, как побочная линия, – знакомствам.

Автоматическое определение сообществ в социальных сетях
Актуальным, активно разрабатываемым и совершенствуемым направлением исследования и моделирования сетей является выявление сообществ (Community Detection) в социальных сетях [9,12,13]. В такого рода исследованиях сообществом считается совокупность пользователей, имеющих большую плотность связей внутри совокупности, по сравнению с плотностью внешних связей.

Иными словами, при изучении сложных сетей, считается, что сеть имеет структуру сообщества, если узлы сети могут быть легко разделены на (возможно перекрывающиеся) наборы узлов так, что каждый набор узлов имеет сравнительно большую внутреннюю плотность. В частном случае определения неперекрывающихся сообществ, это означает, что сеть делится на группы узлов с плотными внутренними связями и редкими связями между группами [12].

Основными алгоритмами определения сообществ в сетях являются [14]:

- Minimum-Cut Method (пер. с англ. – метод отсечения минимальных связей) – состоит в том, что сеть делится на заранее заданное число частей, обычно, примерно равного объема, определяемых таким образом, чтобы число связей между ними было минимальным. Метод имеет довольно существенные недостатки в применении к социальным сетям, так как находит сообщества, независимо от того, есть они в социальной сети или нет, причем именно то количество сообществ, которое задано вручную исследователем.

- Hierarchical clustering (пер. с англ. – иерархическая кластеризация) – в этом методе определяется количественная мера сходства некоторых (как правило, топологические) характеристик сходства между парами узлов. Часто используемые меры включают в себя косинус-подобие (cosine similarity), индекс Жаккара (Jaccard index), и расстояние Хемминга (Hamming distance) между строками матрицы смежности.

- Girvan-Newman algorithm clustering (пер. с англ. – алгоритм Гирвана-Ньюмана), основанный на параметре промежуточности вершин, – находит вершины, лежащие между сообществами и удаляет их, получая несвязанные сообщества. Дает достатоно хорошие результаты, но очень ресурсоемок с точки зрения вычислений.

- Modularity maximization (пер. с англ. – максимизация модульности) – наиболее используемый метод. Определяет сообщества путем попытки разбиения на части с максимальной модульностью. Несмотря на широкое применение, имеет ряд недостатков. Считается, что сегодня лучше работает следующий метод.

- Surprise maximization (пер. с англ. – максимизация неожиданных отклонений) – определение сообществ основано на кумулятивном гипергеометрическом распределении.

- The Louvain method (пер. с англ. – Лувинский метод) – подтвердил свою эффективность на ряде примеров и сейчас является одним из наиболее широко используемых методов. Метод реализован во многих программных пакетов сетевого анализа, в том числе в KXEN InfiniteInsight, NetworkX и Gephi. Проводится в два этапа: сначала выделяются локальные сообщества с максимальной модульностью. Затем, используя эти локальные сообщества в качестве узлов, строится сеть следующего порядка и в ней повторяется шаг 1. Эти шаги повторяются до достижения максимальной модульности.

- Clique based methods (пер. с англ. – метод, основанный на кликах) – кликами считаются подграфы, вершины которых соединены каждый с каждым в данной клике.

Исследования и разработки во этом направлении продолжают активно совершенствовать методы выделения сообществ.

Анализ тональности текста (сентимент-анализ)
Анализ тональности текста (сентимент-анализ, англ. Sentiment Analysis), активно развивающееся направление компьютерной лингвистики – класс методов контент-анализа, предназначенный для автоматизированного выявления в текстах эмоционально окрашенной лексики и эмоциональной оценки авторов по отношению к объектам, речь о которых идёт в тексте (анализ высказываний, англ. opinion mining) [15].

В современных системах автоматического определения эмоциональной оценки текста чаще всего используется одномерное эмотивное пространство: позитив или негатив (хорошо или плохо). Однако известны успешные случаи использования и многомерных пространств.

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