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

Оглавление

Введение

Актуальность

Цель и задачи исследования

Структура работы

Глава 1

1.1 Социальные сети

1.1.1 Понятие социальной сети

1.1.2 Модель социальной сети

1.2 Репутация в виртуальных сообществах

1.2.1 Репутация как объект изучения

1.2.2 Репутация с точки зрения асимметрии информации

1.2.3 Репутация в вопросе кооперации

1.2.4 Определение репутации

Вывод по главе 1

Глава 2

2.1 Математические методы для расчета репутации

2.2 Теоретико-игровые модели репутации

2.2.1 Предпосылки использования теории игр

2.2.2 Парные игры в нормальной форме на примере модели Schillo

2.2.3 Байесовы игры на примере модели Joo Young Lee

2.2.4 Многоагентные динамические игры

Вывод по главе 2

Глава 3

3.1 Система для расчета репутации

3.2 Архитектура и функциональные модули системы

3.2.1 Сбор данных для социальной сети

3.2.2 Способы хранения данных для социальной сети

3.2.3 Анализ репутации социальной сети

3.2.4 Интерпретация репутационных показателей

3.3 Практическая часть: создание прототипа системы для расчета репутации

3.3.1 Описание выполненной задачи

3.3.2 Реализация модели

3.3.3 Результаты

Заключение

Список литературы



Введение

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

Актуальность

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

· Репутация как средство уменьшения асимметрии информации

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

· Интерпретация больших данных.

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

· Несоответствие между большим количеством репутационных моделей и применений на практике

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

Цель и задачи исследования

Цель данного исследования сформулирована следующим образом:

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

Были поставлены следующие задачи:

1. Изучить теоретику социальных сетей и репутации.

2. Изучить существующие математические модели для измерения репутации, определить место теоретико-игрового подхода в измерении репутации.

3. Предложить структуру системы для расчета репутации, выделить функциональные модули системы.

4. Изучить и выбрать практические инструменты, необходимые для реализации модулей системы.

5. Разработать прототип системы для расчета репутации.

Структура работы

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

Глава 1

1.1 Социальные сети

1.1.1 Понятие социальной сети

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

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

· Цифровая природа информации.

Тот факт, что электронные социальные сети оперируют цифровой информацией, дает массу возможностей для получения данных, по которым сеть строится. Традиционное изучение социальных сетей испытывает проблемы с неточностью, субъективностью и малым размером выборки. [5] В то время как для моделирования реальных социальных взаимодействий необходимо использовать социологические инструменты сбора информации (опросы, эксперименты и проч.), онлайн-взаимодействия документируются сами собой, оставляя в ходе своего технического исполнения терабайты данных. Структура пользователей того или иного сервиса ("френды" в социальных сетях), сообщения между пользователями или публичные комментарии - на основе такого рода данных в том числе могут быть построены социальные сети.

· Стимулирование разрастания социальных сетей интернетом.

Знание о коммуникационных системах и отношениях появилось задолго до повсеместного внедрения интернета в современную жизнь. Тем не менее, сегодня наблюдается своего рода миграция этих коммуникационных систем из реальной площадки в виртуальную. К примеру, человек веками занимается торговлей, но уже последние полвека он может осуществлять торговлю в том числе в интернете. При этом, интернет дает возможности для расширения числа коммуникативных связей одного человека. Индивид способен совершать покупки, не ограничиваясь географическим местом проживания; фирма может насчитывать несколько филиалов, которые эффективно связаны корпоративными системами онлайн - иными словами, социальные сети, использующие интернет как ресурс, более обширны и имеют сложную структуру. Более сложные социальные сети требуют соответствующие технические инструменты для анализа и интерпретации.

· Сетевая природа онлайн-взаимодействия.

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

В рамках данного исследования рассматриваются социальные сети именно онлайн-коммуникаций. При этом, социальные сети могут быть выделены в различных контекстах. Обычно, контекст определяется характером отношений, которыми связаны ячейки сети. Характер отношений, в свою очередь, задается электронным ресурсом, где происходят онлайн-взаимодействия. К примеру, в социальной сети интернет-магазина ячейками могут являться покупатели и продавцы, а отношения между ними отражать непосредственно торговые отношение, или же некую эмоциональную характеристику: доверие, честное поведение[губ]. Еще один пример социальной сети - взаимоотношения между сотрудниками одной фирмы. Такие сети могут быть построены на основе текстового анализа корпоративной переписки той или иной фирмы, а анализ подобных социальных сетей может быть применен в оценке эффективности сотрудников фирмы, выявить скрытых лидеров или, наоборот, эксплуататоров коллектива. Наконец, сам по себе напрашивается анализ интернет-сетей для общения (Facebook, Instagram, ВКонтакте и проч.). Ячейками социальных сетей здесь являются пользователи, которые связаны отношениями дружбы, подписки, просмотров. Анализ социальной сети в данном случае позволяет оценить так называемый селф-брендинг пользователя социальной сети, или же измерить охват аудитории рекламодателя или СМИ, осуществляющих свою деятельность в данной социальной сети.

1.1.2 Модель социальной сети

Анализ социальной сети зачастую подразумевает построение её модели. Базисом для анализа и моделирования социальной сети является теория графов. Формально социальная сеть математически описывается графом , где вершины графа - множество агентов, ребра графа - множество отношений между агентами [6]. В зависимости от моделируемой задачи, граф может быть направленным и ненаправленным, или мультиграфом. Отношения дружбы, товарищества, доверия могут быть интерпретированы с помощью ненаправленных рёбер графа, в то время как такие отношения, как торговля (покупка/продажа), отправка сообщения, хорошо описываются с помощью направленных графов. Графы, в том числе, являются инструментом для интерпретации данных, так как они могут быть явным образом визуализированы, а графическая информация в целом более доступна человеку. Помимо этого, графовое представление дает массу инструментов для анализа данных, основанных на соответствующем разделе дискретной математики.

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

1.2 Репутация в виртуальных сообществах

1.2.1 Репутация как объект изучения

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



Рис. 1.1 Изучение репутации в различных областях знаний

1.2.2 Репутация с точки зрения асимметрии информации

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

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

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

· Члены сообществ зачастую анонимны, при этом границы входа и выхода в виртуальные сообщества могут отсутствовать.

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

Выделенные выше факторы свидетельствуют о том, что виртуальным сообществам присуща асимметрия информации, а интернет магазины и C2C системы могут быть проинтерпретированы, как "рынки лимонов". [9] В работе Акерлофа "Рынок лимонов" говорится о том, что рынки с несимметричной информацией деградируют и вырождаются при отсутствии механизмов, умаляющих влияние асимметрии информации. В работе [3] утверждается, что информационная асимметрия может быть смягчена с помощью репутации и доверия. Идея состоит в том, что для агентов, располагающих большей информацией и гипотетически способных вести себя оппортунистически, рассчитывается некий показатель репутации. Менее информированная сторона составляет некое представление о контрагенте на основе его репутации, в конечном счете принимая решение, доверять ему или нет. Репутация в таком случае играет в роли фактора, ограничивающего действия более информированного агента, поскольку теперь дабы эффективно действовать на рынке, агент вынужден заботиться о своей репутации.

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

1.2.3 Репутация в вопросе кооперации

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

Идея состоит в том, что члены социальной сети имеют некое представление о других агентах социальной сети, которое описывается понятием репутации. Моделирование репутации как меры готовности кооперировать может быть использовано для создания систем, прогнозирующих поведение партнеров и конкурентов. Помимо этого, таким подходом к репутации можно оценить эффективность влияния одного актора социальной сети на других. Такая задача имеет особенно важное значение в социальных сетях для общения (типа ВКонтакте, Facebook) для сообществ, осуществляющих некую коммерческую деятельность или выступающих в качестве рекламодателя и СМИ.

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

1.2.4 Определение репутации

В [8] дается следующее определение репутации: сформировавшееся общественное мнение о качествах, достоинствах и недостатках того или иного индивида. Исследователи компьютерной науки определяют репутацию схожим образом. По их мнению, это восприятие о намерениях и нормах агента, сформировавшееся на основе его прошлых действий. Репутация с точки зрения компьютерной науки подразумевает некий количественный показатель, который рассчитывается на основе действий агента, а также наблюдений прочих акторов социальной сети [3].

Однако, в существующих научных работах об измерении репутации в виртуальных сообществах определения репутации вводятся различными способами. Базисом такого различия является та область знаний, с точки зрения которой эти определения трактуются. К примеру, в естественном своем значении понятие репутации находится на стыке таких наук, как социология и психология. Оттенок ментальных отношений, присущий понятию репутации, осложняет его математическое или компьютерное моделирование отражающим действительность образом. Тем не менее, во многих работах понятие репутации находит свое применение как экономистами, так и исследователями компьютерной науки. Стоит отметить, что введенные ими определения не отражают полной сути столь многоуровневого понятия, как репутация; во многих случаях репутация является не более, чем абстракцией, которая, впрочем, в той или иной мере отражает одну из сущностей комплекса понятия "реальной" репутации. В работе [2] в качестве определения репутации предлагается типология (рис. 1.2), созданная на основе обзора работ, в которых рассчитываются те или иные репутационные показатели.

· Контекстность и персонализация

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

· Глобальная и локальная репутация

Репутация с точки зрения персонализации может быть глобальной и персонализированной. Имеется в виду, что репутация может быть как индивидуальной характеристикой и описывать взаимодействия между двумя взаимодействующими агентами, так и агрегированным показателем репутации относительно всей социальной сети. Глобальная репутация видна для всех участников социальной сети. Различие данных подходов состоит в том, что в первом случае отдельный агент может иметь одновременно высокие показатели репутации для одних агентов и низкие для других. Стоит отметить, что в ряде работ [3] для определения репутации в локальном смысле, а именно, репутации одного агента с точки зрения другого используется понятие доверия. Однако здесь и далее мнение одного индивида относительно другого будет определяться с помощью понятия репутации.

Рис. 1.2 Типология репутации, представленная в работе [2]

· Индивидуальная и групповая репутация

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

· Непосредственная и косвенная репутация

Непосредственная репутация рассчитывается напрямую на основе прямых взаимодействий между акторами социальной сети (к примеру, факт покупки товара в интернет-магазине), в то время как интерпретация репутации как косвенной или опосредованной меры подразумевает показатель, отражающий мнения одного агента о другом, составленной не прямыми взаимодействиями с ним, но на основе информации третьих лиц или с помощью "сарафанного радио". Стоит отметить, что моделирование репутации в непосредственном виде легче осуществить, поскольку можно полагаться на непосредственные факты взаимодействия. В то же время, в естественном своём смысле репутация о человеке или бренде часто складывается без опыта прямого взаимодействия с ним. Таким образом, при моделировании репутации в непосредственном виде необходимо учитывать такие факторы, как ограниченную рациональность людей и когнитивные факторы [3], что представляется непростой задачей.

· Репутация по наблюдениям и прямым контактам

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

· Априорные и транслированные показатели репутации

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

Вывод по главе 1

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



Глава 2

Глава содержит обзор математических моделей, в которых осуществляется расчет репутационных показателей. В главе будут рассмотрены преимущественно теоретико-игровые модели.

2.1 Математические методы для расчета репутации

репутация социальный виртуальный сообщество

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

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

Модели [11, 12, 14] являются усовершенствованными вариантами механизмов, описанных ранее, так как также полагаются на дискретные оценки, но обрабатывают их с помощью более продвинутых математических методов. К примеру, модель Sporas [11] оценивает надежность рассчитанной репутации, используя стандартное отклонение ее значений. Модель, предложенная исследователями Abdul-Rahman и Hailes [12] также использует дискретные оценки, при этом репутация конкретного агента является вектором всех оценок - количества оценок "очень надежный", "надежный", "ненадежный", "очень ненадежный", которые получил конкретный агент. Оценка доверия при к агенту рассчитывается при этом как средневзвешенное оценок. В модели ReMSA [14] происходит учет частоты взаимодействия между агентами, а также учитывает структуру графа и, соответственно, механизмы информационного распространения показателя репутации.

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

2.2 Теоретико-игровые модели репутации

2.2.1 Предпосылки использования теории игр

В статье [11] указаны критерии, характерные для моделирования репутации. Критерии состоят в следующем:

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

· Информация о взаимодействиях должна распространяться между участниками сети.

· Оценки предыдущих взаимодействий должны участвовать в принятии решения текущих взаимодействий.

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

2.2.2 Парные игры в нормальной форме на примере модели Schillo

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

В модели Schillo [10] игра между агентами представляет из себя повторяющуюся дилемму заключенного. Игры между агентами проводятся попарно, то есть мощность множества игроков . Стратегий, как и в классической дилемме заключенного, также две: сотрудничество или предательство.

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

,

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

Модель позволяет оценивать локальную репутацию (одного агента по отношению к другому) на основе продолжительных взаимодействий. Исследователи отмечают, что модель может быть практически применена в электронной коммерции схемы B2B, где предприятия могут кооперироваться в долгосрочном периоде или попытаться "снять сливки". Входными параметрами модели является набор игроков и заданная для каждого игрока вероятность сокрытия информации.



2.2.3 Байесовы игры на примере модели Joo Young Lee

Байесовы игры являются играми с неполной информацией, в которых выигрыш игрока помимо действий остальных игроков зависит от типов игроков, которые задают их стратегии поведения, при этом, тип агента известен только самому агенту и неизвестен остальным участникам игры. Байесовы игры применимы в ситуациях, где агентов можно разделить на две или более групп в зависимости от их поведения. К примеру, в [14] на основе байесовых игр предлагается рассчитывать показатель репутации в eBay, где в предположении модели есть честные и нечестные продавцы.

В модели Joo Young Lee [15] вводится байесова репутационная игра , где - социальная сеть агентов;

,

набор стратегий агентов первого хода и агентов ответного хода ;

набор типов игроков, а тип j-того игрока; оцененная i-тым игроком вероятность того, что j-тый игрок имеет тип ; функция полезности .

Показатель репутации в модели измеряется непосредственно выигрышами игры, которые являются приростами локальной (парной) репутации , складывающейся из нескольких повторяющихся игр. Стратегии инициирующего игрока - вступать в кооперацию с оппонентом для увеличения величины своей репутации (стратегия ) или не вступать (стратегия ). Игрок , совершающий ответный ход, принимает предложение (стратегия ) или отказывает (стратегия ). В случае, если игрок принимает предложение, его стратегия определяется из в зависимости от его типа или соответственно. На рисунке 2.1 механизм продемонстрирован деревом игры.

Рис 2.1 Дерево баейсовой репутационной игры

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

(1);

(2);

(3).



Выбор стратегии игроками осуществляется также на основе оценивания вероятности , а также с учетом вероятностей принятия той или иной стратегии , и .

Рис 2.2 Смешанные стратегии игроков с оцениваемыми вероятностями выбора

Представленная модель довольно-таки абстрактна, так как выигрыши осуществляются не в материальной форме, а также, требует интерпретации параметра , который подается на вход модели вместе с графом социальной сети и является оценкой степени j-го агента. Тем не менее, в 3-й главе будет представлена реализация именно этой модели.

2.2.4 Многоагентные динамические игры

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

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

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



,

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

(1) .

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

(2) ,

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

Таким образом, прибыль агента рассчитывается по следующей формуле:



(3)

где - это вектор инвестиций агентов в репутацию, - цена продукта, переменные издержки производства, - постоянные переменные. Целевая функция является суммарной прибылью за периодов времени:

(4)

Подставив (1) - (3) в (4) получена игра в нормальной форме, где каждый агент выбирает величину репутационных издержек. В игре может быть найдено равновесие Нэша, и рассчитаны выигрыши сторон в результате их стратегий.

Вывод по главе 2

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



Глава 3

3.1 Система для расчета репутации

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

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

3.2 Архитектура и функциональные модули системы

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

Рис. 3.1 Иллюстрация централизованной (а) и распределенной (б) архитектур систем репутации. Оранжевыми фигурными стрелками показано предоставление информации об агентах сети, синими - получение репутационных показателей

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

Проектируемую систему можно разделить на три модуля: модуль для сбора данных, модуль расчета репутации и модуль интерпретации полученных данных.

Рис. 3.2 Модули проектируемой системы для расчета репутации



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

3.2.1 Сбор данных для социальной сети

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

· API виртуальных платформ.

В случае если репутация рассчитывается на основе непосредственных взаимодействий между агентами сети, будь то совершение транзакций или отношения в социальной сети типа "лайк", "френд", для извлечения этой информации могут быть использованы API платформы. Очевидно, что в таком случае, социальная сеть базируется на платформе, API которой используется для извлечения данных, и взаимодействия всех агентов социальной сети происходят в рамках одной платформы. С помощью API можно собрать данные для социальных сетей из интернет-магазинов и аукционов (eBay, Amazon), C2C систем (Uber, BlaBlaCar), коммуникативных социальных сетей (ВКонтакте, Instagram). Ограничениями данного подхода являются привязанность к конкретной платформе, таким образом, модуль сбора данных для социальной сети не является универсальным для нескольких платформ. Помимо этого, с помощью API можно собрать информацию о непосредственных фактах взаимодействия (например, отправка сообщения), однако без учета семантики (собирается информация о самом факте отправки сообщения, но не о его смысле, эмоциональном оттенке и проч.). Помимо этого, ограничение на сбор данных связано с персональными данными и политикой конфиденциальности.

· Работа с текстовыми данными.

В ходе взаимодействия пользователей во всемирной сети остается огромное количество документов, своего рода свидетельств этого взаимодействия. Такими документами могут являться электронные сообщения, комментарии в разного рода платформах, гипертекст. Алгоритмы, используемые для работы с текстовыми данными, могут быть самыми разными в зависимости от формата текстовых документов, поступающих на вход системы, а также от контекста социальной сети. В работах [5,17] сбор информации для социальной сети происходит на основе анализа текстовых документов. В [17], к примеру, на вход модуля для сбора информации поступает текстовый файл, содержащий электронную корреспонденцию. Программный модуль разделяет документ на отдельные письма, удаляет заголовок и подпись для исключения шума, маркирует IP, URL и домен в письмах. На основе каждого письма формируется объект из четырех сущностей , где - содержание письма, - время отправки письма, - электронный адрес автора, - булева переменная, показывающая, является ли письмо ответом или пересылкой. Между объектами далее выстраивается сеть со связями "отправил сообщение". В работе [5] упоминаются программные модули, используемые для анализа гипертекста, так называемые скреперы и спайдеры. Скреперы - программы, которые обрабатывают веб-страницу таким образом, что ее содержание становится пригодным для использования в качестве входных данных. Спайдеры - класс программ, который следует по ребрам связей гипертекста и извлекают данные. На вход спайдеры получают "первоначальный посев", набор страниц, а на выходе спайдеры возвращают набор из пар страниц, при этом каждая пара состоит из страницы из посева и новой страницы. Исследователи отмечают, что при использовании описанных методов необходимо отделять важные связи от шума (рекламных объявлений, к примеру), а также считаться с информационной политикой ресурсов.

· Семантический анализ текста.

Семантический анализ текста подразумевает анализ смысловой нагрузки текста, в то время как в предыдущем абзаце речь шла больше об анализе данных. На данный момент существует масса анализаторов текста, однако, преимущественно, на английском языке. Тем не менее, в рамках заданного контекста может быть разработана система для сбора семантической онтологии той или иной специализации [18]. Семантические анализаторы текста способны распознавать эмоциональную окраску сообщения, что в теории позволяет на основе анализа переписки построить социальную сеть с ментальными отношениями (уважение, симпатия). Стоит отметить, что силами семантического аппарата может быть смоделирована и сама репутация [19].

· Прогнозирование недостающих данных.

В работе [17] представлен микро-уровневый подход к анализу социальных сетей. Под микро-уровневым подходом понимается ситуация, когда расчет репутации происходит распределённо (см. 3.2), и социальная сеть обозревается не вся целиком (макро-уровень), а с точки зрения конкретной ячейки (т.н. эго-сети [5]). В ситуации, когда известны только связи заданной ячейки, но неизвестны степени ячеек, связанных с данной, представленный метод позволяет оценить степени связанных ячеек с помощью бета-распределения. Такой подход не является сбором данных по сути, но позволяет дополнить информацию об имеющейся социальной сети, для которой далее рассчитываются репутационные показатели. Реализация подобных методов логически должна содержаться в модуле сбора информации.

3.2.2 Способы хранения данных для социальной сети

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

· Текстовые форматы.

Пожалуй, самым простым и доступным способом представления графа для дальнейшей визуализации является текстовый формат. Визуализаторами поддерживаются CSV, JSON, XML представления графов.

CSV - текстовый формат, предназначенный для представления таблиц в текстовом виде. Каждая строка данного текстового формата является строкой таблицы, значения ячеек которых разделяются заданным символом (первоначально запятой, однако под CSV объединяются табличные данные с любыми разделителями).

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

Рис. 3.3 CSV-таблицы ячеек и связей.



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

JSON - текстовый формат обмена данными. Несмотря на то, что формат основан на JavaScript, считается независимым от языка и может использоваться практически с любым языком программирования.

JSON и XML могут кодировать такие структуры данных, как пара ключ: значение и последовательность значений. Подобная структуризация позволяет описывать граф одним текстовым файлом, в отличие от CSV.

GraphML, Trivial Graph Format (TGF), DOT - языки и форматы, которые, в отличие от JSON и CSV были созданы непосредственно для описания графов. GraphML является расширением языка разметки XML. Граф, описанный на языке DOT, также представляет из себя текстовый файл с раширением GV. Файлы данного формата используются рядом графических утилит, о которых подробнее будет сказано позже.

Рис. 3.5. Примеры ориентированного и неориентированного графов, описанных на DOT.



Рис. 3.6. Граф на двух вершинах, описанный в GraphML

· Графовая база данных

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

Самой распространенной графовой БД на данный момент является Neo4J [27]. Neo4J обладает массой достоинств: оптимизированный дисковый менеджер хранилища, мощный движок обхода графа. Один экземпляр данной СУБД способен обрабатывать графы с миллиардным количеством узлов и связей; способен обрабатывать графы, которые не помещаются в оперативной памяти. Для извлечения информации из БД Neo4j существует свой язык запросов Cypher.



3.2.3 Анализ репутации социальной сети

Реализация выбранной модели для оценки репутационных показателей может быть осуществлена с использованием любого языка программирования, однако, учитывая тот факт, что моделирование репутации зачастую подразумевает оперирование с громоздким математическим аппаратом, наиболее подходящими инструментами для реализации являются математико-специализированные языки (MatLab, R) и функциональные языки (Haskell, Ruby). По большому счету, выбор инструмента разработки зависит от сложности модели.

...