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

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

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

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

· Библиотеки JS

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

o Arbor.js

Arbor [20] является специализированной под визуализацию графов с помощью библиотекой, использующей jQuery. Как заявляют разработчики библиотеки, использование библиотеки позволяет сосредоточиться на дизайне элементов графа и его общем визуальном стиле, в то время как математика отображения и физика анимации реализованы средствами arbor.

o d3.js

Очень мощная библиотека для визуализации в целом, D3 Data-Driven Documents [22] позволяет рисовать в том числе и графы. На сайте фреймворка сказано, что он разработан для решения проблемы эффективного управления документами на основе информации. Синтаксис D3 основывается на сложившихся веб-стандартах: HTML, SVG, CSS. Стоит отметить, что данный фреймворк особенно хорош в создании анимационных объектов, взаимодействующих с пользователем. В плане визуализации графов на сайте библиотеки в открытом доступе лежит пример кода, реализующего интерактивную визуализацию графа. Алгоритм рассчитывает, как оптимально отобразить граф, однако изображение графа не статично в данном примере. Пользователь курсором мыши может хватать граф за ячейки, перетаскивать их, и в зависимости от действий пользователя граф может занять иную оптимальную позицию.

Рис. 3.7 Визуализация графа с помощью D3

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

· Пакет утилит Graphviz

Пакет утилит Graphviz [21,24] для автоматической визуализации графов работает с графами, описанными на языке DOT, о котором говорилось ранее. В пакете есть несколько инструментов, использующих различные алгоритмы визуализации. Для создания многоуровневого направленного графа используется инструмент dot, использующий алгоритм ранговой модели. Для реализации ненаправленных графов используется несколько различных инструментов, в частности graph, использующий аналогичный ранговый подход; метод twopi, который отрисовывает графы с радиальной раскладкой, и другие.

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

Рис. 3.8 (а, б) Примеры графов, построенных с помощью neato (а) и twopi (б) инструментов пакета Graphviz

Рис. 3.9, 3.10 Демонстрация возможностей инструмента dot пакета Graphviz: код графа на языке DOT и его автоматическая визуализация

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

· Средство визуализации данных Gephi

Gephi[23] является программным обеспечением для визуализации графов с открытым исходным кодом. На сайте продукта сказано, что подходит для визуализации графов и сетей любых видов.

Gephi[23] может принимать большое количество форматов данных (CSV, JSON), а также возможен импорт из реляционной БД. Импортируются две таблицы: edges и nodes. При этом таблица ячеек должна содержать обязательное поле id, а таблица связей - поля source и target. При импорте графа можно указать его ориентацию.

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

Рис. 3.11 Пример графа, полученного с помощью Gephi

· · Визуализаторы графовой базы данных Neo4j

Разработчики Neo4j [27] предлагают разные способы для визуализации своего продукта, а именно, графовой базы данных. Сам продукт поддерживает отрисовку с помощью javascript и библиотек Alchemy.js или упомянутую ранее D3.js. Предполагается, что база данных портируется в формате GraphJSON и по нему строится с помощью указанных библиотек. Также, существует PHP-драйвер для описания данных Neo4j (создания новых ячеек и связей).

Помимо этого, существуют отдельные продукты, работающих с базами данных Neo4j. Одним из самых продвинутых является проприетарное ПО Linkruious [25]. Linkurious предлагает широкий спектр услуг, выходящий за рамки обычной визуализации. Данный продукт позволяет осуществлять поиск по базе данных Neo4j, осуществлять аналитику с помощью обработчика языка запросов Cypher, а также редактировать саму графовую БД: добавлять и удалять новые ячейки, связи. Что касается визуализации, она разработана на высоком уровне: позволяет добавлять лейблы к ячейкам, настраивать связи, иными словами, делать красивые и информативные графы. Полученная в Linkurious информация может быть экспортирована в файл изображения, Excel или вышеупомянутый Gephi.

Рис. 3.12. Интерфейс Linkurious.

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

Помимо этого, существует готовый продукт Tableau Server [28], реализованный в том числе на графовой БД Neo4j. Продукт позволяет анализировать информацию в БД и строить на ее основе различные визуализированные отчеты. Это может быть реализовано с помощью интерфейса виджетов, которые хранятся на корпоративном сервере, а доступ к ним осуществляется с помощью различных версий клиентов (мобильные версии для смартфонов и планшетов, полноценные приложения и онлайн-версии).

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

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

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

Для расчета репутации была выбрана модель Кооперация на основе байесовских репутационных игр [13], подробно описанная в главе 2. Входные данные для тестирования модели были взяты из источника [29]. Графическая интерпретация модели была осуществлена с помощью программного пакета Gephi.

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

Входными данными модели является граф социальной сети, а также величина , являющаяся оценкой степени ячеек графа. Социальная сеть представлена сетью цитирования, взятой из источника [29]. Чтобы проинтерпретировать параметр в контексте научных исследователей был выбран индекс Хирша, рассчитанный с помощью калькулятора [31] по поисковому запросу из Google Scholar [30]. В результате "чистки" данных социальная сеть насчитывает 85 ячеек - авторов статей, и 272 связи, являющихся цитированием. Для программной реализации модели был выбран объектно-ориентированный язык программирования C#, поскольку, во-первых, выбранный граф имеет сравнительно небольшой размер, помимо этого математического функционала языка C# достаточно для реализации модели. Граф социальной сети подается на вход анализатора в виде двух таблиц формата.csv, и выводится в том же виде с рассчитанными показателями репутации.

Рис. 3.13. Данные в формате.csv

В работе [13], откуда была взята модель для реализации, также описан алгоритм симуляции модели (рис. 3.13), который и был реализован на языке C#. В ходе реализации были созданы такие абстрактные типы данных, как класс ячейки (Node), ребра (Edge), графа (Graph). В рамках классов разработаны методы, необходимые для вычисления репутации.

Рис. 3.14. Алгоритм модели, предложенный в [17].

В ходе алгоритма каждый игрок осуществляет выбор контрагента для кооперации на основе ожидаемой выгоды (pickCPlayer()). Далее первый игрок выбирает стратегию (rAction), и в случае, если агентом выбрана стратегия Ask, ход переходит к следующему игроку, который, в свою очередь, выбирает свою стратегию поведения (cAction). В результате игры первый игрок получает выигрыш в виде прироста к показателю репутации по отношению к контрагенту. Описанные выше механизмы реализованы с помощью метода класса Graph Game(), подробнее с кодом можно ознакомиться в приложении к работе.

3.3.3 Результаты

На изображениях ниже (рис. 3.15, 3.16, 3.17) представлен результат визуализации социальных сетей с учетом рассчитанных репутационных показателей. На рисунках видно, что в результате одного прогона игры репутация с агентами типа T улучшилась, в то время как с агентами типа U, соответственно, ухудшилась. После неоднократных прогонов игры видно, что взаимодействия с агентами типа T проводилась и далее, в то время как с недобросовестными агентами были прекращены взаимодействия. Такая ситуация подтверждается данными из статьи [13], где были рассмотрены стратегии в долгосрочной перспективе.

Рис. 3.14. Графы социальных сетей до обработки анализатором, после одной игры и после цикла пяти игр (голубым цветом отмечены ячейки типа T, розовым типа U, размер ячеек отображает величину degree модели, желтым цветом отображены связи с отрицательным значением репутации, зеленым связи с положительной репутацией)

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

Заключение

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

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

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

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

1. Fombrun C., Van Riel C. The reputational landscape //Corporate reputation review. - 1997. - С. 1-16.

2. Mui L., Mohtashemi M., Halberstadt A. A computational model of trust and reputation // System Sciences. 2002. P. 2431-2439.

3. Губанов Д.А. Обзор онлайновых систем репутации / доверия. - М: ИПУ РАН, 2009. Интернет-конференция по проблемам управления (www.mtas.ru/forum). -25 с.

4. B. Hogan, Analysing Social Networks Via the Internet / July 18, 2007

5. M. E. J. Newman The structure and function of complex networks / Department of Physics, University of Michigan, Ann Arbor, MI 48109, U.S.A. and Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, U.S.A.

6. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. - Модели репутации и информационного управления в социальных сетях - "Математическая теория игр и ее приложения. - 2009. - Т. 1. №2", C. 209-233

7. Matthew O. Jackson, Social and Economic Networks / Princeton University Press, February 2008

8. [Online resource]/ Глоссарий - URL: http://www.glossary.ru/

9. Akerlof G. The market for "lemons": Quality uncertainty and the market mechanism. - Macmillan Education UK, 1995. - С. 175-188

10. Schillo M., Funk P., Rovatsos M. Using trust for detecting deceitful agents in artificial societies // Applied Artificial Intelligence, 14. 2000. P. 825-848.

11. Sabater J., Sierra C. Review on computational trust and reputation models //Artificial intelligence review. - 2005. - Т. 24. - №. 1. - С. 33-60.

12. A. Abdul-Rahman, S. Hailes / Supporting Trust in Virtual Communities. - Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000

13. JooYoung Lee and Jae C. Oh, "A model for recursive propagations of reputations insocial networks.", in ASONAM, Jon G. Rokne and Christos Faloutsos, Eds. 2013, pp. 666-670, ACM.

14. Petteri Nurmi, "A bayesian framework for online reputation systems.",in AICT/ICIW. 2006, p. 121, IEEE Computer Society

15. JooYoung Lee, Jae C. Oh Convergence of True Cooperations in Bayesian Reputation Game / 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications

16. Ермаков Н.С., Иващенко А.А., Новиков Д.А. Модели репутации и норм деятельности. М.: ИПУ РАН, 2005. - 67 с.

17. Lee, JooYoung, "REPUTATION COMPUTATION IN SOCIAL NETWORKS AND ITS APPLICATIONS" (2014). Dissertations -ALL. Paper 138.

18. Захлебин И.В., Фомичев В.А. Pазpаботка метода семантического поиска специалистов в коpпоpативной базе данных по естественно-языковым запpосам, 2015, Информационные технологии, том 21, №5, с. 323-330

19. Pinyol I., Sabater-Mir J., Cunн G. How to talk about reputation using a common ontology: From definition to implementation //Proceedings of the ninth workshop on trust in agent societies, Hawaii, USA. - 2007. - С. 90-101.

20. [Online resource] / Arbor - официальный сайт фреймворка - URL: arborjs.org.

21. [Online resource] / Custis - информационные системы на заказ - URL: http://www.custis.ru/

22. [Online resource] / Data driven documents - официальный сайт фреймворка - URL: https://d3js.org.

23. [Online resource] / Gephi - makes graphs handy - официальный сайт продукта - URL: https://gephi.org/

24. [Online resource] / Graph Visualization Software - официальный сайт продукта - URL: http://www.graphviz.org/

25. [Online resource] / Linkurious - visualize graph data easily - официальный сайт продукта - URL: http://linkurio.us/

26. [Online resource] / Martin Grandjean DIGITAL HUMANITIES | DATA VISUALIZATION | NETWORK ANALYSIS URL: http://www.martingrandjean.ch/

27. [Online resource] / Neo4j - официальный сайт продукта - URL: neo4j.com.

28. [Online resource] / Tableau Server - официальный сайт продукта - URL: http://www.tableau.com/

29. [Online resource]/ Citation networks - URL: http://vlado.fmf.uni-lj.si/pub/networks/Data/cite/default.htm

30. [Online resource]/ Google Scholar - Академия Google - URL: scholar.google.ru/

31. [Online resource]/ Scholar H-Index Calculator for Google Chrome - URL: https://chrome.google.com/webstore/detail/scholar-h-index-calculato/cdpobfbhbdlpbloccjokjgekjnmifbng

Размещено на Allbest.ru