Введение к работе
Актуальность темы.
Процесс информатизации общества носит глобальный характер. Многие практические задачи, связанные с информационными сетями, можно представить в виде игры с сетевой структурой. Данный раздел теории игр изучает как методы формирования связей между игроками (игры формирования сетей), так и правила определения выигрышей игроков с учётом этих связей. Игроки в сетях, как правило, действуют индивидуально, руководствуясь личными интересами. Поэтому основным аппаратом являются бескоалиционные игры, в которых каждый игрок независимо выбирает свою стратегию. Однако для оптимизации структуры сетей, потоков в них можно и нужно применять методы кооперативной теории игр.
В данной работе предлагается использовать методы кооперативной теории игр для анализа структуры информационных сетей и оптимального распределения ресурсов. Актуальность рассматриваемой темы подтверждается большим вниманием, которое уделяется и кооперативным и сетевым играм.
Цель диссертационной работы заключается в разработке методов кооперативной теории игр с целью их применения для анализа информационных сетей.
Для достижения этих целей в работе решены следующие задачи:
-
Предложена и исследована модель коммуникационной игры, которая может быть использована для оценки значимости вершины в графе.
-
Разработаны алгоритмы вычисления кооперативных решений с использованием производящих функций.
-
Предложен алгоритм распределения памяти на основе п-ядра.
-
Созданы комплексы программ для численной реализации на ЭВМ предложенных алгоритмов и проведены численные эксперименты.
Методы исследования основываются на применении аппаратов кооперативной теории игр и теории графов. Для численного моделирования и программной реализации разработанных алгоритмов используются методы
прикладного программирования.
Научная новизна работы. Результаты диссертационного исследования расширяют сферу применения кооперативных игр. В работе впервые применяются методы кооперативной теории игр для анализа структуры информационных сетей и оптимального распределения информационных ресурсов. Для коммуникационной игры, характеристическая функция которой задаётся специальным образом, предложен делёж и доказано, что он совпадает с вектором Майерсона. Получена производящая функция для вычисления числа всех путей в дереве и числа путей, содержащих определённую вершину. Для коммуникационной игры, ограниченной случайным графом, разработан комплекс программ, с помощью которого можно найти зависимость среднего выигрыша от вероятности появления ребра между любыми двумя вершинами. Предложен теоретико-игровой подход к распределению памяти компьютера. Разработан программный комплекс, позволяющий проводить численные эксперименты.
Практическую ценность работы представляют алгоритмы, использующие производящие функции, которые могут быть применены для автоматизации вычислений. В работе приводятся численные примеры, демонстрирующие полученные результаты.
На защиту выносятся следующие результаты и положения:.
-
Разработана теоретико-игровая модель коммуникационных сетей. Предложен новый метод вычисления характеристической функции.
-
Предложены алгоритмы вычисления вектора Майерсона с использованием производящих функций для сетей в виде деревьев и произвольных графов.
-
Предложен новый метод распределения памяти на основе п-ядра.
-
Разработаны модели и комплекс программ в пакете Mathematica для анализа структуры информационных сетей, в том числе, анализа академических сайтов.
Апробация работы. Основные результаты были представлены на следующих конференциях:
-
VI Московская международная конференция по исследованию операций (ORM-2010), г. Москва, 19-23 октября 2010 г.
-
II Российский Экономический Конгресс (РЭК-2013), г. Суздаль, 18-22 февраля 2013 г.
-
Международная конференция Сетевые игры и Менеджмент NGM2013, г. Петрозаводск, 23-25 июня, 2013 г.
-
VII Международная конференция Теория игр и Менеджмент GTM2013, г. Санкт-Петербург, 26-28 июня, 2013 г.
а также на семинарах кафедры фундаментальной и прикладной математики, теории и методики обучения математике физико-математического факультета Читинского государственного гуманитарно-педагогического университета им. Н. Г. Чернышевского и на семинарах лаборатории математической кибернетики ИПМИ КарНЦ.
Материалы диссертации опубликованы в 4 печатных работах, из них 2 статьи в журналах, входящих в перечень ВАК ведущих периодических изданий [2,3] и тезисы 2 докладов [1,4].
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объём диссертации составляет 111 страниц, включая 6 таблиц, 29 рисунков и два приложения. Библиография включает 69 наименований.
