Задачи и методы определения атрибутов пользователей социальных сетей1 c Антон Коршунов Институт системного программирования РАН, Москва korshunov@ispras.ru Аннотация С точки зрения анализа данных, социальная сеть в её современном понимании представляет Рост популярности онлайновых сервисов собой граф с произвольным числом типов вершин социальных сетей — основных источни- и рёбер, весами и атрибутами, допускающий нали- ков персональных данных о пользовате- чие множественных связей между узлами [3]. Воз- лях Интернета — открывает беспрецедент- можность создания текстовых и мультимедийных ные возможности для решения исследо- объектов внутри сети делают её уникальным ис- вательских и бизнес-задач, а также со- точником данных о личной жизни и интересах ре- здания вспомогательных сервисов и при- альных пользователей (переписка, дневники, фо- ложений для пользователей социальных тоальбомы, видеозаписи, музыкальные компози- сетей. Определение неизвестных атрибу- ции и т.д.). Всё это обуславливает повышенный тов пользователей является одной из фун- интерес к сбору и анализу социальных данных со даментальных проблем анализа социаль- стороны компаний (конкурентное преимущество) ных данных. В представленной работе рас- и исследовательских институтов (новые задачи и смотрены методы решения некоторых ак- точки приложения известных подходов) [4]. туальных задач, связанных с определени- Обработка социальных данных требует также ем скрытых пользовательских атрибутов: разработки соответствующих алгоритмических и поиск сообществ пользователей, определе- инфраструктурных решений, позволяющих учи- ние демографических атрибутов пользова- тывать их размерность. К примеру, граф соци- телей, а также идентификация пользова- альной сети Facebook на сегодняшний день содер- телей в различных социальных сетях. жит более 1 миллиарда пользовательских аккаун- тов и более 100 миллиардов связей между ними. Каждый день пользователи добавляют более 200 1 Введение миллионов фотографий и оставляют более 2 мил- лиардов комментариев к различным объектам се- Онлайновые социальные сети (Facebook, Twitter, ти. На сегодняшний день большинство существу- YouTube и другие) к настоящему моменту стали ющих алгоритмов, позволяющих эффективно ре- неотъемлемой частью Веба и продолжают наби- шать актуальные задачи, не способны обрабаты- рать популярность [1, 2]. За последнее десятиле- вать данные подобной размерности за приемлемое тие социальные сервисы существенно изменились время. В связи с этим, возникает потребность в в плане архитектуры, функционала и пользова- новых решениях, позволяющих осуществлять рас- тельского интерфейса. С одной стороны, это обу- пределённую обработку и хранение данных без су- словлено стремлением сделать их использование щественной потери качества результатов. более удобным, а с другой - активной коммер- Помимо большого объёма данных и высокой циализацией и необходимостью увеличить время, динамичности социальной сети, нужно прини- проводимое пользователями на страницах серви- мать во внимание такие факторы, как нестабиль- сов. ность качества пользовательского контента (спам и ложные аккаунты), проблемы с обеспечением 1 Работа выполнена при поддержке гранта РФФИ приватности личных данных пользователей при №13-07-12134 офи_м “Исследование и разработка методов распределенной обработки больших баз графовых дан- хранении и обработке, а также частые обнов- ных”. ления пользовательской модели и функционала. Материалы 15-й всероссийской кон- В дополнение к перечисленным проблемам, это ференции "Электронные библиотеки: требует постоянного совершенствования алгорит- перспективные методы и техноло- мов решения различных аналитических и бизнес- гии, электронные коллекции— RCDL- задач. 2013, Ярославль, Россия, 14-17 октября Одной из фундаментальных задач анализа 2013 г. социальных данных является определение неиз- 183 вестных значений атрибутов пользователей. С ного графа на уровне связей между пользовате- этой целью специализированные методы анализа лями. сетевых, текстовых и других данных применяют- Благодаря проведённым исследованиям эмпи- ся к социальному графу на разных уровнях его рических данных социальных сетей стало возмож- организации: ным составить следующий список фундаменталь- ных свойств сообществ пользователей на уровне • на уровне сети скрытыми атрибутами мо- связей между пользователями в социальном гра- гут быть группы пользователей (сообще- фе [11, 12, 21]: ства), в которых состоит пользователь; • вершины в сообществе более тесно связаны • на уровне пользователя скрытыми мо- друг с другом, чем с вершинами за предела- гут быть биографические и демографиче- ми сообщества; ские атрибуты пользователя, а также его ин- тересы и предпочтения; • количество рёбер в сообществе растёт супер- линейно в зависимости от его размера; • на межсетевом уровне скрытым атрибу- том пользователя в одной сети может быть • сообщества могут пересекаться, т.е. один идентификатор этого пользователя в другой пользователь может относиться к несколь- сети. ким сообществам, что хорошо согласуется с тем фактом, что человек одновременно мо- В представленной работе рассмотрены некото- жет играть несколько социальных ролей в рые актуальные задачи, связанные с определени- обществе; ем атрибутов пользователей, а также разработан- ные нами методы их решения. Раздел 2 посвящён • сообщества имеют иерархическую структу- задаче поиска сообществ пользователей, целью ру, что можно объяснить тенденцией чело- которой является определение набора сообществ, веческого общества к формированию иерар- в котором состоит каждый пользователь сети. В хии социальных групп; разделе 3 рассмотрена задача определения демо- • размер сообществ распределён по степенно- графических атрибутов пользователей по текстам му закону; их сообщений и атрибутам профиля. Раздел 4 со- держит описание задачи идентификации пользо- • количество сообществ, к которым принадле- вателей в различных социальных сетях. жит вершина, распределено по степенному закону; 2 Поиск сообществ пользователей • вершины с небольшой степенью чаще вхо- дят в небольшое число сообществ, тогда как Поиск сообществ пользователей является важным вершины с большой степенью входят во мно- инструментом изучения и анализа социальных се- жество сообществ. тей, позволяющим исследовать мезоскопическую (модульную) организацию сети и использовать Использование перечисленных свойств позво- полученную информацию для решения различ- ляет выполнять поиск сообществ пользователей ных задач. К примеру, знания о структуре сооб- как множеств вершин социального графа. Резуль- ществ незаменимы для предсказания связей и ат- татом работы метода поиска сообществ являет- рибутов пользователей, расчёта близости пользо- ся покрытие — множество сообществ, в котором вателей в социальном графе, оптимизации пото- каждая вершина принадлежит как минимум од- ков данных в социальной сети, некоторых анали- ному сообществу. тических приложений и т.д. 2.2 Метод 2.1 Задача В связи с перечисленными особенностями сооб- С функциональной точки зрения сообщество - ществ пользователей многие алгоритмы опреде- это группа пользователей, выполняющая общую ления модульной структуры сетей неспособны роль или функцию и обладающая общими свой- корректно идентифицировать сообщества в соци- ствами, ценностями и целями. Немаловажным альном графе. Потенциально применимые алго- свойством также является тенденция к взаимному ритмы можно разделить на классы, основанные влиянию участников сообщества друг на друга. на статистической значимости сообществ, случай- Поскольку формализация приведённого опре- ных блужданиях, локальной оптимизации подгра- деления и построение соответствующей модели фов, вероятностных моделях и агентских моде- представляет определённые практические трудно- лях [5, 6]. Из рассмотренных классов только ме- сти, важно выделить некоторые особенности сооб- тоды, основанные на агентских моделях, позво- ществ пользователей, характерные для социаль- ляют достичь оптимального сочетания качества 184 Вычислительная сложность алгоритма O(T · |E|) для произвольного графа и O(T · |V |) для разреженного социального графа (T - количество итераций). Кроме того, алгоритм естественным образом формулируется в терминах Pregel [10] - вычис- лительной парадигмы для параллельных вычис- лений над графовыми данными. Разработанный метод был реализован в рамках Spark.Bagel 2 - фреймворка для параллельной обработки данных на кластере из потребительских компьютеров. Вместе с тем, проведённое нами исследование результирующих покрытий выявило недостаточ- ное качество результатов алгоритма SLPA для Рис. 1: Алгоритм SLPA: на каждой итерации случая значительно пересекающихся сообществ. “говорящие” узлы (окрашены чёрным) посылают Более детальное исследование получающихся по- “слушающему” узлу (окрашен белым) метки со- крытий выявило неспособность алгоритма разде- обществ (a,b,c,d ), выбирая их из текущего набо- лять значительно пересекающиеся сообщества. ра меток для каждого узла. “Слушающий” узел Для решения этой проблемы была предложена добавляет в свою память самую популярную из следующая модификация оригинального алгорит- полученных меток. ма: • применить алгоритм поиска максимальных результатов и производительности, необходимого клик размером не более 5 вершин к исход- для получения качественных результатов на гра- ному социальному графу; фах из миллиардов вершин. Разработанный нами метод представляет со- • всем вершинам, принадлежащим одной кли- бой модификацию алгоритма SLPA [10], основан- ке, назначить одну и ту же метку сообще- ного на агентской модели. Данный алгоритм ло- ства; кально имитирует человеческое общение между парами индивидуумов, а глобально моделирует • вершинам, не принадлежащим найденным инфекционный процесс. Основой алгоритма яв- кликам, назначить уникальные метки сооб- ляется процесс обмена метками сообществ между ществ; вершинами в соответствии с динамическими пра- • для каждой вершины найти локальные сооб- вилами взаимодействия (рисунок 1): щества среди вершин, непосредственно свя- 1. Память каждого узла инициализируется занных с ней; уникальной меткой сообщества; • на каждой итерации “говорящий” узел посы- 2. Затем итеративно повторяется последова- лает не одну, а несколько случайно выбран- тельность шагов: ных меток каждому из “слушающих” узлов; (a) Выбирается “слушающий” узел; • на каждой итерации “слушающий” узел при- нимает только по одной метке от каждого (b) Каждая из вершин-соседей выбранно- из своих локальных сообществ (выбирается го узла (“говорящие” узлы) случай- самая популярная из меток, отправленных ным образом выбирает метку с вероят- вершинами одного сообщества); ностью, пропорциональной количеству меток данного типа в своей памяти, и • выполнить итерации и пост-обработку по посылает выбранную метку “слушаю- аналогии с оригинальным алгоритмом. щему” узлу; Таким образом, на этапе инициализации на- (c) “Слушающий” узел выбирает самую по- мечаются центры будущих сообществ с помощью пулярную из присланных ему меток и найденных клик. Затем с помощью модифици- добавляет её в свою память. рованных правил взаимодействия вершин между 3. В ходе пост-обработки для каждой верши- собой поощряется объединение локальных сооб- ны выбираются самые популярные метки с ществ в глобальные. помощью заданного порога t; 2 http://spark-project.org/ 4. Выбранные метки определяют принадлеж- ность вершин к сообществам. 185 Рис. 2: Результаты оценки качества с помощью неориентированных LFR-графов. Каждый граф состоит из 2000 вершин, часть вершин состоит в пересекающихся сообществах (в данном случае каждая вершина состоит в 6 различных сообществах), остальные вершины состоят в непересекающихся сообществах. 2.3 Результаты На рисунке 2 приведено сравнение оригиналь- ного алгоритма SLPA с предложенными модифи- Наиболее распространённым способом оценки ка- кациями. Из графика следует, что лучших резуль- чества результатов методов поиска сообществ татов позволяет добиться сочетание инициализа- пользователей является сравнение двух покрытий ции кликами с модификацией правил взаимодей- для некоторого графа: найденного алгоритмом и ствия вершин с помощью локальных сообществ. референсного, то есть заранее заданного или из- Вместе с тем, использование локальных сооб- вестного. ществ без клик позволяет исключить значитель- Для оценки качества результатов разработан- ный объём вычислений, необходимый для поиска ного метода использовался генератор LFR [11], максимальных клик. При этом качество резуль- способный генерировать случайные графы с за- татов ухудшается незначительно и по-прежнему данной структурой сообществ. существенно лучше оригинального алгоритма. В качестве количественной меры для сравне- Для оценки производительности разработан- ния двух покрытий применялась нормализован- ного метода было проведено тестирование метода ная взаимная информация (NMI) [22], значение в параллельном режиме с помощью сервиса об- которой показывает, в какой степени наличие ин- лачных вычислений Amazon EC2. По результатам формации о структуре одного из покрытий умень- тестирования метод показал линейную масштаби- шает неопределённость по поводу другого покры- руемость от числа вершин в исходном графе, а тия: также от количества параллельно функциониру- N (X : Y ) = 1 − 12 [H(X|Y )norm + H(Y |X)norm ], ющих вычислительных элементов. где H(X|Y )norm - нормализованная услов- 3 Определение демографических ная энтропия X при условии Y (наоборот атрибутов пользователей для H(Y |X)norm ), а X и Y - случайные величины, ассоциированные со сравниваемыми покрытиями. При заполнении своего профиля в социальной се- С помощью выбранного метода оценки ка- ти пользователи зачастую по ошибке или предна- чества было проведено сравнение разработанно- меренно не заполняют некоторые поля либо дают го метода поиска сообществ пользователей с со- ложную информацию о фактах своей биографии, временными методами поиска пересекающихся интересах и предпочтениях. Кроме того, в кон- сообществ (алгоритмы SLPA [10], MOSES [20], тентных сетях (Twitter, YouTube) пользователь- OSLOM [21] и другие). По результатам тестиро- ский профиль часто ограничен набором базовых вания значение NMI для предложенного метода атрибутов, недостаточным для решения многих в большинстве случаев превосходит аналогичные задач, предполагающих персонализацию резуль- показатели выбранных для сравнения методов. татов. В остальных случаях лучшее качество показыва- ют методы, обладающие большей вычислитель- ной сложностью и неприменимые к графам боль- шой размерности (миллиарды вершин). 186 3.1 Задача как набор символьных строк, из которых извлека- ются признаки, а для разметки применяются до- В системах интернет-маркетинга и рекомендаций полнительные источники данных о пользователе, особую важность представляет определение демо- причём в большинстве случаев разметка произво- графических атрибутов пользователя для тар- дится вручную [16–18]. гетированного продвижения товаров и услуг в Разработанный нами метод обладает следую- группах пользователей с одинаковыми значени- щими преимуществами: ями атрибутов. К таким атрибутам относятся пол, возраст, семейное положение, уровень обра- • автоматическое построение исходного набо- зования, профессия, трудоустроенность, религи- ра данных; озные и политические взгляды, место жительства и т.д. Помимо интернет-сервисов, такие социо- • извлечение большого количества признаков демографические характеристики находят приме- различных типов как из текстов сообщений, нение в различных дисциплинах: социология, пси- так и из полей профиля пользователя, с учё- хология, криминология, экономика, управление том особенностей микросинтаксиса Twitter ; персоналом и др. • использование быстрого и эффективного ме- Демографические атрибуты можно условно тода отбора информативных признаков; разделить на категориальные (пол, националь- ность, раса, семейное положение, уровень образо- • расширяемый набор поддерживаемых атри- вания, профессия, трудоустроенность, религиоз- бутов: все поля Facebook -профиля, а также ные и политические взгляды) и численные (воз- любая информация о предпочтениях и ин- раст, уровень доходов). Условность разделения тересах пользователя могут быть использо- связана с тем, что значения численного атрибу- ваны в качестве атрибутов 3 ; та можно отобразить в набор категорий и в даль- нейшем рассматривать этот атрибут как катего- • расширяемый набор поддерживаемых язы- риальный. В частности, значения возраста мож- ков благодаря использованию автоматиче- но разделить на несколько возрастных категорий, ской идентификации языка текста сообще- что часто применяется на практике. ний и применению метода построения исход- Важным вопросом в решении задачи опреде- ного набора данных, не зависимого от языка. ления скрытых демографических атрибутов яв- Метод состоит из следующих этапов: ляется выбор признаков. В представленной ра- боте целевым источником данных была выбрана • построение исходного набора данных; сеть Twitter - контентная сеть с преобладанием текстового содержимого (сообщений пользовате- • предварительная обработка текста; лей). Таким образом, задача состоит в определе- • построение признакового описания; нии скрытых демографических атрибутов поль- зователей социальной сети по текстам их сооб- • отбор информативных признаков; щений. По смыслу задача эквивалентна класси- ческой задаче социолингвистики: определению • обучение; характерных особенностей языка представителей • классификация. различных социальных групп, позволяющих про- изводить частичную идентификацию человека по Все этапы, за исключением первого, выполня- принадлежности к этим группам. Такая поста- ются отдельно для каждого атрибута. новка задачи позволяет использовать предложен- На этапе построения исходного набора ный метод для обработки данных многих попу- данных производится сбор данных пользовате- лярных сетей, поскольку текстовые данные явля- лей из сети Twitter. Для каждого пользователя ются наиболее распространённым средством ком- сначала запрашивается только его профиль в се- муникации. ти Twitter. При наличии в нём ссылки на профиль того же пользователя в сети Facebook (в которой 3.2 Метод набор пользовательских атрибутов существенно больше, чем в Twitter) запрашиваются и сохра- Абсолютное большинство современных методов няются все доступные сообщения пользователя из определения демографических атрибутов пользо- сети Twitter. После чего для текущего пользова- вателей основаны на применении методов машин- теля запрашивается и сохраняется его профиль в ного обучения с учителем с целью классифика- сети Facebook, из которого извлекаются указанные ции пользователей по лингвистическим и другим пользователем значения его атрибутов. признакам в предопределённые классы, соответ- ствующие различным значениям изучаемых атри- 3 https://developers.facebook.com/docs/reference/api/user/ бутов. Сообщения пользователя рассматриваются 187 Таким образом, элементом набора данных для На этапе классификации в качестве входных каждого атрибута и языка является набор сим- данных используются тексты сообщений и поля вольных строк, полученных из текстов сообщений профиля произвольного пользователя. Выполня- и профиля одного пользователя в Twitter, а так- ется алгоритм классификация для заданного язы- же значение атрибута у данного пользователя в ка и атрибута. Результатом является значение ат- Facebook. рибута выбранного пользователя. На этапе предварительной обработки тек- ста к текстам полученного на предыдущем эта- 3.3 Результаты пе набора данных применяется метод определе- ния языковой принадлежности текста (библиоте- Для тестирования использовались наборы дан- ка language-detection 4 ). После этого данные поль- ных англоязычных пользователей Twitter, разме- зователей распределяются в различные наборы ченные по полу (мужской/женский) и возрасту данных в зависимости от языка пользователя. (моложе 20 лет/от 20 до 40 лет/старше 40 лет). Предварительно осуществляется фильтрация Набор данных, размеченный по полу, включа- сообщений, авторство которых не принадлежит ет 3 755 пользователей и 180 240 сообщений. На- пользователю (ретвиты). Поскольку цитирова- бор данных, размеченный по возрасту, включает ние сообщений других пользователей является 17 050 пользователей и 818 400 сообщений. Все на- весьма популярным способом распространения боры данных сбалансированы по значениям атри- информации в сети Twitter, этот шаг предвари- бутов. тельной обработки особенно важен для повыше- Для оценки качества результатов использует- ния точности метода. ся точность классификации (accuracy). Исходный На этапе построения признакового описа- набор данных разделяется на обучающую и тесто- ния из сообщений и полей Twitter -профиля поль- вую подвыборки. В качестве входных данных ис- зователей извлекаются лингвистические призна- пользуются тексты пользователей сети Twitter из ки. тестовой подвыборки исходного набора данных. Сначала к исходным текстам применяется то- Точность классификации по полу составля- кенизация. Для элементов специфического син- ет 83,3%. Использование для разметки словарей таксиса сообщений (хэштегов, @-ссылок ), а так- мужских и женских имён английского языка поз- же слов из полей профиля создаются токены спе- воляет увеличить исходный набор данных более циальных типов, а для обычных слов из сообще- чем в 4 раза (70734 пользователя) и повысить точ- ний - токены стандартного текстового типа. ность классификации до 89,2%. Rao et al [16] со- Из полученных токенов сообщений и полей общают о точности 72,33%, Al Zamal et al [18] - о профиля строится набор признаков в виде N - точности 80,2% для идентичной задачи. грамм размером от 1 до 7 с учётом порядка токе- Точность классификации по возрасту состав- нов. Аналогичный набор признаков строится для ляет 71,4%. всех символов в текстах пользователя. Каждый тип признаков представлен двумя подтипами: с 4 Идентификация пользователей в учётом и без учёта регистра символов. различных социальных сетях Итоговый вектор признаков для пользователя является бинарным, то есть содержит только ин- Одной из фундаментальных проблем проблем при формацию о наличии или отсутствии признака в использовании социальной информации о поль- его текстовых данных. Количество экземпляров зователе является её фрагментированность сре- одного признака игнорируется. ди множества различных онлайновых социаль- На этапе отбора информативных призна- ных сетей. Каждый год появляется множество как ков применяется метод, основанный на расчё- общенаправленных, так и нишевых социальных те условной взаимной информации [19]. Произво- сервисов, и для активных пользователей Интер- дится итеративный отбор тех признаков, которые нет типично иметь несколько профилей в различ- содержат наибольшее количество информации о ных социальных сетях. Несмотря на то, что су- значении атрибута и при этом существенно от- ществуют попытки по обеспечению единого спо- личаются от признаков, выбранных на предыду- соба взаимодействия между различными социаль- щих итерациях. Таким образом, каждый признак ными платформами (например, OpenSocial 5 ), они результирующего набора высоко информативен и не получили широкого применения, а новые соци- слабо зависит от остальных признаков. альные сервисы продолжают появляться. Иденти- На этапе обучения производится построение фикация пользователя в различных социальных модели классификации с использованием онлай- сетях позволяет получить более полную картину нового пассивно-агрессивного алгоритма [13]. о социальном поведении данного пользователя в 4 https://code.google.com/p/language-detection/ 5 http://opensocial.org/ 188 сети Интернет. Обнаружение аккаунтов, принад- A-4 лежащих одному человеку, в нескольких социаль- A-3 A-5 ных сетях, позволяет получить более полный со- A-6 циальный граф, что может быть полезно во мно- A-2 A-s гих задачах, таких как информационный поиск, интернет-реклама, рекомендательные системы и A-1 т.д. B-5 Поскольку поиск аккаунтов пользователя в B-4 различных сетях в общем случае требует наличия B-6 актуальных данных обо всех пользователях дан- B-3 B-s ных сетей, целесообразно ограничить простран- B-7 B-2 ство поиска ближайшими соседями какого-либо пользователя, аккаунты которого в исследуемых B-1 сетях известны. Таким образом, задача идентифи- кации пользователей в различных социальных се- Рис. 3: Результат идентификации пользователей. тях в локальной перспективе подразумевает со- Пунктирные стрелки обозначают проекции меж- поставление аккаунтов пользователей в рамках ду аккаунтами. Для вершин, закрашенных синим, списков контактов некоторого центрального поль- проекции были известны заранее, проекции для зователя в различных социальных сетях. Такая незакрашенных вершин были установлены алго- задача часто возникает при работе с контактами ритмом, для вершин, закрашенных серым, проек- пользователей в социальных мета-сервисах, кото- ции не были найдены рые, в частности, могут служить для объединения новостных потоков в поддерживаемых социаль- ных сервисах или предоставления единой системы информации о социальных связях пользователя обмена сообщениями. Другая область, в которой требуется его непосредственное разрешение. возникает подобная задача, это функция автома- тического объединения контактов из различных 4.2 Метод источников (телефонная книга, социальные сети, Большинство современных методов идентифика- мессенджеры), распространённая в современных ции пользователей в различных социальных сетях мобильных устройствах. ограничивается лишь анализом атрибутов профи- лей пользователей, поскольку они зачастую со- 4.1 Задача держат информацию, помогающую идентифици- Задача идентификации пользователей заключает- ровать пользователя. Общая схема работы таких ся в поиске как можно большего числа правиль- методов выглядит следующим образом [14]: но определенных пар аккаунтов (v, u) таких, что 1. приведение данных из полей профилей из v ∈ A, u ∈ B, принадлежащих одному и тому же двух социальных сетей к некоторому обще- пользователю (< A, B > - социальные графы). му виду (например, вектору, элементами ко- Сопоставленный аккаунт для аккаунта v ∈ A обо- торого являются атрибуты профилей); значается как pr(v) ∈ B и называется проекци- ей аккаунта v ∈ A в B, а множество всех проек- 2. попарное применение различных способов ций {pr(v)}v∈A аккаунтов из A в B как PR(A). сравнения к атрибутам профилей из анали- Если же для аккаунта v ∈ A не найдено подхо- зируемых сетей; дящей проекции, то проекция для v называется нейтральной и обозначается как pr(v) = N. При- 3. подсчет результирующего показателя похо- мер двух таких социальных графов < A, B > и жести между профилями и отсечение всех сопоставленных пар аккаунтов изображен на ри- парных результатов, для которых этот по- сунке 3. казатель ниже некоторого порогового значе- Поскольку задача идентификации рассматри- ния. вается в локальной перспективе, то подразумева- ется, что графы A и B имеют структуру эго-сетей После этого все оставшиеся пары считаются некоторого центрального пользователя. Эго-сеть сопоставленными между собой и принадлежащи- вершины e представляет из себя граф, состоящий ми одному пользователю. из вершины e, ближайших соседей e, а также дан- Очевидно, что информация, содержащаяся в ных о связях соседей e между собой и с други- профилях, достаточно ненадежна, так как дан- ми вершинами. Такая формулировка отражает ре- ные, указанные пользователем в разных социаль- альные ограничения использования социальных ных сетях, могут существенно отличаться, быть сетей, в которых для предоставлении какой-либо скрытыми из-за настроек приватности или не под- держиваться в актуальном состоянии. 189 Одним из способов улучшения результатов Унарная энергия характеризует похожесть описанного подхода является привлечение допол- вершины в A и его проекции в B на основании нительных источников данных, в частности ин- полей профилей в этих двух социальных сетях: формации о социальных связях между пользова- Φ(yv |xv ) = α(v) · (1 − profile-similarity(v, pr(v))) телями. Разработанный нами метод [7,8] использует со- Бинарная энергия отвечает за близость между циальные связи обеих рассматриваемых социаль- проекциями вершин v и u в графе B: ных сетей путем сравнения оригинальных списков Ψ(yv , yu |xv , xu ) = 1 − network-similarity(pr(v), pr(u)) контактов, естественным образом комбинируя их с информацией атрибутов профилей, благодаря Здесь 0 ≤ profile-similarity ≤ 1, и чему лишен многих недостатков существующих α(v) = log(degree(v)) ≥ 0 - коэффициент ба- методов идентификации пользователей. ланса между унарной и бинарной энергией. Метод основывается на двух основных прин- В качестве функции близости profile-similarity ципах: между полями профилей используется вероят- ность, с которой бинарный классификатор (C4.5 1. задачи выбора проекций для связанных вер- с MultiBoosting) считает их принадлежащими од- шин в графе A взаимосвязаны, иначе гово- ному пользователю на основании сравнения меж- ря, выбор проекции для некоторой вершины ду строковыми значениями атрибутов профи- зависит от значений проекций связанных с лей. Используемые для сравнения поля профилей ней вершин; Facebook и Twitter приведены в таблице 1. 2. если две вершины в графе A связаны, их Таким образом, для графов < A, B > суще- проекции должны иметь наиболее высокое ствует оптимальная конфигурация проекций: значение графовой близости. Y∗ = argminE(Y|X), Y В качестве функции графовой близости 0 ≤ network-similarity(pr(v), pr(u)) ≤ 1 использует- которая минимизирует функционал энергии, мак- ся модифицированный коэффициент Дайса: симизируя сумму функций близости и правдопо- добие модели. Разумно допустить, что не для всех вершин 2 · w(Lv ∩ Lu ) необходимо выбирать проекции. В разработан- network-similarity(v, u) = , v, u ∈ B, w(Lv ) + w(Lu ) ном методы проекция вершины v считаются за- ранее известной, если profile-similarity(v, pr(v)) ≥ где Lv и Lu - множества вершин, связанных с v и u ∆. Кроме того, проекции некоторых вершин мо- соответственно, а w(L) = |L| - вес этих множеств. гут быть указаны явно. Использование известных Также предполагается, что один из графов проекций позволяет уменьшить объём вычисле- < A, B > является ненаправленным. В дальней- ний и повысить качество результатов за счёт до- шем без ограничений общности таким графом бавления априорной информации о модели. считается A. Поскольку выбрать разумные фиксирован- На основе графа A строится модель условных ные значения функций близости для нейтраль- случайных полей [15], в которой множество на- ных проекций не представляется возможным, для блюдаемых переменных представлено вершинами фильтрации неправильно выбранных проекций графа A: X = V (A) = {xv , v ∈ A}, с каждой из используется схема обучения бинарного класси- которых ассоциирована одна скрытая переменная фикатора (С4.5 с MultiBoosting). Используя ин- Y = {yv , v ∈ A}, определяющая проекцию дан- формацию о контексте каждой вершины в A, ной вершины yv = pr(v) ∈ B. Скрытые перемен- классификатор решает, правильно ли для неё вы- ные могут принимать в качестве значения одну из брана проекция. Для этого используются следую- вершин графа B. Связи же наследуются из графа щие признаки: A: E = E(A). Данная модель порождает следую- щее вероятностное распределение: 1. profile-similarity(v, pr(v)); 2. средняя графовая близость к проекциям p(Y|X) = exp(−E(Y|X)), смежных вершин; X X E(Y|X) = Φ(yv |xv ) + Ψ(yv , yu |xv , xu ), 3. доля заранее известных проекций среди v∈V (v,u)∈E смежных вершин; где E - функционал энергии, моделируемый функ- 4. взаимная согласованность смежных вершин цией унарной энергии Φ и функцией бинарной с заранее известными проекциями: энергии Ψ. Обе энергетические функции веще- 1 X 1 X ственны и неотрицательны. · network-similarity(pr(v), pr(u)|v, u) n v n−1 u6=v 190 Таблица 1: Поля профилей Facebook и Twitter, участвующие в сравнении Поле в Facebook Поле в Twitter Имя (name) Имя (name) Псевдоним (screen_name) Веб-сайт (website) URL Таблица 2: Результаты экспериментов метод полнота точность F1 взвешенная сумма 0.45 0.94 0.61 profile-similarity 0.51 1.0 0.69 предложенный метод 0.80 1.0 0.89 4.3 Результаты B с некоторым порогом близости профилей, ниже которого проекция не включалась в результаты и Разработанный метод был протестирован на дан- считалась нейтральной. ных из социальных сетей Facebook и Twitter. Результаты тестирования приведены в табли- 16 центральных пользователей, имеющих про- це 2. филь в обеих сетях, предоставили доступ к сво- им эго-сетям, а также указали пары аккаунтов, принадлежащих одному и тому же пользователю. 5 Заключение Для всех участников эксперимента были загруже- ны профили их друзей (вместе со связями меж- В работе были рассмотрены основные особенно- ду ними), а также друзей их друзей. В Twitter сти социальных сетей как источников данных, а профиль загружался только при наличии между также некоторые задачи и методы анализа разно- пользователями взаимных связей следования для родных пользовательских данных из социальных поддержания семантики связей дружбы, харак- сетей, связанные с определением неизвестных зна- терных для Facebook. Суммарное число профилей чений пользовательских атрибутов. в Twitter и Facebook 398 и 977, а число связей 108 и Одной из доминирующих тенденций развития 641 соответственно. Общее число сопоставленных социальных сетей как социокультурного феноме- пар пользователей - 102. на является более глубокое понимание особенно- Для оценки качества результатов использует- стей социального поведения человека и, как след- ся точность, полнота и F1 -мера. Исходный набор ствие, создание новых средств для самовыраже- данных разделяется на обучающую и тестовую ния, а также обмена информацией и опытом. Ра- выборки. Для расчёта показателей качества при- зумно ожидать дальнейшего расширения пользо- меняется кросс-валидация с разбиением исходных вательской модели и функционала социальных се- данных на 3 непересекающихся блока. В каче- тей, что приведёт к появлению новых типов дан- стве входных данных используется пара эго-сетей ных в виде объектов и связей социального графа в Facebook и Twitter какого-либо центрального и, как следствие, возможности решать новые за- пользователя. дачи, связанные с обработкой персональной ин- Для сравнения были выбраны два базовых ал- формации. горитма, основанных на расчёте похожести про- филей пользователей. Первый алгоритм исполь- Благодарности зует взвешенную сумму значений функций стро- ковых близостей между полями профилей, коэф- Автор благодарит научного руководителя фициенты для которых подбирались при помощи д.т.н. Кузнецова С.Д., а также коллег из отдела линейной регрессии из предположения, что меж- информационных систем ИСП РАН за помощь в ду правильно сопоставленными профилями сум- разработке и реализации представленных в ра- ма близостей должна быть равна 1. Второй ал- боте методов: Аванесова В.С., Андрианова И.А., горитм использует функцию profile-similarity. Ре- Бартунова С.О., Белобородова И.Б., Бузуна Н.О., зультатом работы базового алгоритма считается Гомзина А.Г., Ипатова С.А., Турдакова Д.Ю., максимальное паросочетание между графом A и Филоненко И.И. 191 Список литературы algorithms on directed and weighted graphs with overlapping communities // Physical [1] D. M. Boyd, N.B. Ellison. Social network sites: Review E80, 016118 (2009) Definition, history, and scholarship // Journal of Computer-Mediated Communication, 2007, [12] Jaewon Yang, Jure Leskovec. Defining and 13(1), article 11 Evaluating Network Communities based on Ground-truth // Proceedings of 2012 IEEE [2] George Pallis, Demetrios Zeinalipour-Yazti, International Conference on Data Mining Marios D. Dikaiakos. Online Social Networks: (ICDM), 2012 Status and Trends // New Directions in Web Data Management 1, Studies in Computational [13] Koby Crammer, Ofer Dekel, Joseph Keshet, Intelligence Volume 331, 2011, pp 213-234 Shai Shalev-Shwartz, Yoram Singer. Online Passive-Aggressive Algorithms // JMLR, [3] Facebook Open Graph. https://developers. 7(Mar):551–585, 2006 facebook.com/docs/opengraph/ [14] I. Veldman. Matching profiles from social [4] Social Network Data Analytics. Editors: Charu network sites: similarity calculations with social C. Aggarwal // Springer, 2011 network support // Master’s thesis, University of Twente, 2009 [5] Nazar Buzun, Anton Korshunov. Innovative Methods and Measures in Overlapping [15] J. Lafferty, A. McCallum, F. Pereira. Community Detection // Proceedings of Conditional random fields: Probabilistic the International Workshop on Experimental models for segmenting and labeling sequence Economics and Machine Learning (EEML data // Proc. 18th International Conf. on 2012). — Leuven, Belgium, 6 May 2012 Machine Learning, 2001. Morgan Kaufmann. pp. 282–289 [6] Назар Бузун, Антон Коршунов. Выявление пересекающихся сообществ в социальных се- [16] Delip Rao, David Yarowsky, Abhishek тях // Доклады Всероссийской научной кон- Shreevats, Manaswi Gupta. Classifying Latent ференции «Анализ изображений, сетей и тек- User Attributes in Twitter // Proceedings of стов» (АИСТ’2012). — Екатеринбург, 16-18 the 2nd International Workshop on Search and марта 2012 г. Mining User-generated Contents, 2010 [7] Sergey Bartunov, Anton Korshunov, Seung- [17] John D. Burger, John Henderson, George Taek Park, Wonho Ryu, Hyungdong Lee. Joint Kim, Guido Zarrella. Discriminating Gender Link-Attribute User Identity Resolution in on Twitter // Proceedings of the Conference Online Social Networks // Proceedings of The on Empirical Methods in Natural Language Sixth SIGKDD Workshop on Social Network Processing, 2011 Mining and Analysis (SNA-KDD’12). — Beijing, China, 12 August 2012 [18] Faiyaz Al Zamal, Wendy Liu, Derek Ruths. Homophily and Latent Attribute Inference: [8] Сергей Бартунов, Антон Коршунов. Иден- Inferring Latent Attributes of Twitter Users тификация пользователей социальных сетей from Neighbors // Proceedings of the Sixth в Интернет на основе социальных связей // International AAAI Conference on Weblogs and Доклады Всероссийской научной конферен- Social Media, 2012 ции «Анализ изображений, сетей и текстов» (АИСТ’2012). — Екатеринбург, 16-18 марта [19] François Fleuret. Fast Binary Feature Selection 2012 г. with Conditional Mutual Information // JMLR, 5:1531–1555, 2004 [9] J. Xie, B. Szymanski. Towards Linear Time Overlapping Community Detection in Social [20] Aaron McDaid, Neil Hurley. Detecting Highly Networks // PAKDD 2012 Overlapping Communities with Model-Based Overlapping Seed Expansion // Proceedings of [10] Grzegorz Malewicz, Matthew Austern, Aart the 2010 International Conference on Advances Bik, James Dehnert, Ilan Horn, Naty Leiser, in Social Networks Analysis and Mining Grzegorz Czajkowski. Pregel: a system for large- (ASONAM ’10) scale graph processing // Proceedings of the 2010 ACM SIGMOD International Conference [21] Andrea Lancichinetti, Filippo Radicchi, José J. on Management of data Ramasco, Santo Fortunato. Finding statistically significant communities in networks // PLoS [11] Andrea Lancichinetti, Santo Fortunato. ONE 6, e18961 (2011) Benchmarks for testing community detection 192 [22] Andrea Lancichinetti, Santo Fortunato1, János Kertész. Detecting the overlapping and hierarchical community structure in complex networks // New J. Phys. 11 033015, 2009 Problems and methods for attribute detection of social network users Anton Korshunov Institute for system programming of RAS The increasing popularity of online social network services — the main sources of personal data of Internet users — brings unprecedented opportunities for solving research and business problems, and also for building auxiliary services and applications for social network users. Detection of latent user attributes constitutes a fundamental problem of social data analysis. In the paper, methods for solving several actual problems related to latent user attribute detection are considered: user community detection, detection of demographic user attributes, and user identity resolution in different social networks. 193