Кооперативные решения в задачах анализа информационных сетей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Трухина, Людмила Ивановна

• Трухина, Людмила Ивановна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Трухина, Людмила Ивановна

Оглавление

Введение

Глава 1. Вектор Майерсона в коммуникационной игре, ограниченной

деревом

1.1. Основные понятия и определения

1.2. Модель коммуникационной игры, ограниченной деревом

1.3. Производящая функция для числа путей

1.4. Сложность алгоритма

1.5. Частные случаи

1.5.1. Цепь

1.5.2. Звезда

Глава 2. Вектор Майерсона в коммуникационной игре, ограниченной

произвольным графом

2.1. Модель коммуникационной игры, ограниченной произвольным

графом

2.2. Сложность алгоритма

2.3. Частные случаи

2.3.1. Простой цикл

2.3.2. Полный граф

2.4. Примеры

2.5. Коммуникационная игра, ограниченная случайным графом

3.1. Оптимальная схема распределения памяти

3.2. ]Ч-ядро в распределении памяти

3.2.1. ]Ч-ядро

3.2.2. Модифицированный алгоритм

3.2.3. Равное деление

3.3. Численные эксперименты

Глава 4. Анализ структуры информационных сетей на примере анализа

академических сайтов

4.1. Анализ структуры академических веб-сайтов

4.2. Кластерный анализ

4.3. Анализ веб-графов академических сайтов

Заключение

Литература

Приложение 1

Приложение 2

Введение диссертации (часть автореферата) на тему «Кооперативные решения в задачах анализа информационных сетей»

Введение

Актуальность темы.

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

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

Основы классической кооперативной теории были заложены Дж. фон Нейманом и О. Моргенштерном [17], а затем развивались в различных направлениях многими авторами. Теория кооперативных игр связана с именами Р. Аума-на, Р. Майерсона, М. Машлера, Э. Мулена, Дж. Нэша, Г. Оуэна, Л. Шепли, Д. Шмайдлера, М. Шубика [15,16,18,29,57,63,64]. Большой вклад в развитие теории кооперативных игр внесли О. Н. Бондарева, Н. Н. Воробьев, Л. А. Петросян, Е. Б. Яновская и другие [5,6,19].

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

подмножество множества игроков N = {1,..., п} (его принято обозначать 2^). Игроки коалиции могут выбирать совместно стратегии, заключать взаимообя-зывающие соглашения и даже выплачивать побочные платежи в виде компенсаций за участие в коалициях. Игры, в которых существует возможность перераспределения между игроками выигрыша, полученного в результате действий образованной ими коалиции, называются играми с трансферабельной полезностью (ТП-играми). В таких играх игрокам из каждой коалиции важно максимизировать суммарный выигрыш, так как в дальнейшем они могут распределять его между собой произвольным образом.

Классически принято рассматривать кооперативную игру п лиц в форме характеристической функции. Характеристическая функция может иметь самое разнообразное происхождение. Вопрос её возникновения при рассмотрении конкретных моделей может представлять самостоятельный интерес. Характеристическая функция описывает величину выгоды, которую данное подмножество игроков может достичь путем объединения в коалицию. Каждой коалиции б1 из множества всех коалиций ставится в соответствие тот максимальный выигрыш г>(£>), который могут гарантировать себе в сумме все члены коалиции 5 независимо от действий остальных игроков.

Однако, возможны запреты на образование некоторых коалиций, т.е. множество коалиций является не множестврм всех подмножеств ./V, а некоторой его частью. Такое положение весьма характерно для практики из-за различных политических, технических, экономических и даже психологических причин (антимонопольное законодательство, отсутствие каналов связи, личные симпатии и антипатии и т.д.) Поэтому теорию игр ¡с-ограниченной кооперацией можно назвать одним из основных разделов современной теории кооперативных игр.

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

который обобщил значение Шепли на игры с заданной коалиционной структурой. Коалиционные игры рассматривались в работах Ауманна и Дрезе [28], Ауманна и Майерсона [30], Курца [54].

Другой способ задания ограничения кооперации рассмотрен в известной статье Майерсона [56]. В своей работе он дополнил кооперативную игру графом коммуникаций. Вершинами графа являются игроки. Такие графы часто называют сетями. Сеть является ограничением взаимодействия игроков, т.е. её роль — определить, какие коалиции могут функционировать. Допустимыми коалициям являются те, участники которых могут свободно общаться через данную сеть. Для такого класса игр, названных коммуникационными играми, Майерсон определил и охарактеризовал правило распределения, являющееся обобщением вектора Шепли.

Его работа была одной из первых работ в этом направлении и породила множество исследований таких игр (обзор в [34,66]). Коммуникационная игра остаётся игрой в форме характеристической функции, и доход коалиции зависит только от её состава. Например, гранд-коалиция из трёх игроков {1,2,3} получит одинаковый доход и в случае когда каждый связан друг с другом (полная сеть) и в случае когда связаны только 1 с 2 и 1 с 3.

В 1996 Джексон и Волынски [51] пошли далее и предложили модель сетевой игры, в которой экономические возможности зависят непосредственно от структуры сетей, соединяющих игроков. Одна и та же пара игроков может получать разную полезность в зависимости от того, связаны они напрямую или косвенно. Следовательно, различные формы организации сети могут генерировать различные уровни дохода, даже если они включают одних и тех же игроков. Сетевые игры включают кооперативные игры и коммуникационные игры как специальные случаи. Теория сетевых игр получила свое развитие в работах М. Джексона и А. Ватте [46-50,69], В. Бала [31], Ф. Пэйджа [61,62], С. Куррарини [37], Б. Дутты [39-42] и многих др. В России теорию сетевых игр развивают К. Е. Авраченков, А. Ю. Гарнаев, Д. А. Губанов, М. В. Губко, Д. А.

Новиков, А. Г. Чхартишвили.

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

Кроме вектора Майерсона, было предложено и изучено много других правил распределения для сетевых игр. Смотрите, например, [27,33,34,36,49,66-68]. И хотя выбор правил распределения является весьма большим, вектор Майерсона достаточно популярен и широко используется в качестве схемы выплаты. Чаще всего он применяется в играх формирования сетей.

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

Для определения силы игроков в теории кооперативных игр применяются различные индексы. Первый такой индекс был введён Шепли и Шубиком [65]. Другая концепция измерения силы была предложена Банцафом [32]. Хорошо известны индексы Дигана-Пакела [38], Холера [53]. Данный инструментарий широко использовался при анализе способов оказания влияния в национальных выборных органах власти, а также при изучении выборных органов международных организаций, например, в Совете Безопасности ООН и органах управления Евросоюза. Но они не учитывают возможные ограничения на образование коалиций.

В работе [45] в игру взвешенного голосования введены ограничения взаимодействия игроков с помощью коммуникационной структуры, заданной деревом. Для определения силы влияния в такой игре используется вектор Майерсона.

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

системы. За годы исследования сетей было введено большое количество различных мер важности вершины в сети в соответствии с тем или иным критерием. Например, мера близости (closeness centrality), мера промежуточности, имеющая несколько вариантов определения: промежуточность по кратчайшим путям (shortest-path betweenness), промежуточность случайного блуждания (random-walk betweenness) и центральная промежуточность (betweenness centrality). Эти показатели оказались весьма полезными для анализа и понимания роли, которые играют вершины в сетях различных типов.

Всё больше появляется работ, посвящённых исследованию веб-графа сайта с помощью вебометрических методов. Одной из актуальных задач является задача определения „значимости" вершины (веб-страницы) в веб-графе. Чем больше „значимость" страницы, тем больше внимания должно уделяться ей в процессе поддержки сайта. Для определения значимости вершин веб-графа также существует множество методов. Наиболее известным на сегодняшний день является PageRank (PR), разработанный Ларри Пейджем и Сергеем Брином в 1996 году. hi ! ■

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

Цель диссертационной работы заключается в разработке методов кооперативной теории игр с целью их применения для анализа информационных

сетей. ........

Для достижения этих целей в работе решены следующие задачи:

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

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

3. Предложен алгоритм распределения памяти на основе п-ядра.

4. Созданы комплексы программ для численной реализации на ЭВМ предложенных алгоритмов и проведены численные эксперименты.

Методы исследования основываются на применении аппаратов кооперативной теории игр и теории графов. Для численного моделирования и программной реализации разработанных алгоритмов использовались методы прикладного программирования.

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения:

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

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

3. Предложен новый метод распределения памяти на основе п-ядра.

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

Апробация работы. Основные результаты были представлены на следующих конференциях:

1. VI Московская международная конференция по исследованию операций (ORM-2010), г. Москва, 19-23 октября 2010 г.

2. II Российский Экономический Конгресс (РЭК-2013), г. Суздаль, 18-22 февраля 2013 г.

3. Международная конференция Сетевые игры и Менеджмент NGM2013, г. Петрозаводск, 23-25 июня, 2013 г.

4. VII Международная конференция Теория игр и Менеджмент GTM2013, г. Санкт-Петербург, 26-28 июня, 2013 г.

а также на семинарах кафедры фундаментальной и прикладной математики, теории и методики обучения математике физико-математического факультета Читинского государственного гуманитарно-педагогического университета им. Н. Г. Чернышевского и на семинарах лаборатории математической кибернетики ИПМИ КарНЦ.

По материалам диссертации опубликовано 4 работы, из них — 2 статьи [14,23] и тезисы двух докладов [13,55].

Структура и объем работы. Диссертация состоит из введения, четырёх глав, разбитых на параграфы, заключения, списка используемой литературы и приложений; включает 111 страниц, 6 таблиц, 29 рисунков.

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

В первой главе приводятся необходимые понятия и определения. Затем рассматривается ТП-игра с ограниченной кооперацией, представленной неориентированным графом — деревом. Вершины графа представляют игроков, а рёбра представляют связи между игроками. Характеристическая функция задаётся специальным образом с учётом числа связей и расстояния между вершинами. Разработана процедура получения дележа для данной игры и доказано, что полученный в результате делёж совпадает с вектором Майерсона. Описан алгоритм вычисления данного дележа с использованием производящей функции. Проведён анализ сложности данного алгоритма. Найден вектор Майерсона для частных случаев игры.

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

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

делёж в явном виде. Предложенные алгоритмы сравниваются с оптимальным алгоритмом распределения памяти и с алгоритмом равного деления с помощью численного моделирования.

В четвёртой главе представлены результаты применения предложенной модели коммуникационной игры и вектора Майерсона для анализа структуры веб-сайтов государственных университетов и научных институтов (математической направленности). Отобраны 6 сайтов государственных университетов и 6 сайтов научных институтов. Для каждого сайта вручную, с помощью карты сайта построен неориентированный граф (дерево), отражающий структуру сайта, и вычислен вектор Майерсона. Каждая компонента вектора может быть интерпретирована как оценка „значимости" или „вес" определённой вебстраницы. Для полученного набора векторов проведён кластерный анализ, в результате которого получено два кластера. В один из которых попали все сайты госуниверситетов кроме одного, а во'второй — все сайты научных институтов так же за исключением одного. С помощью программы-краулера получены матрицы смежности веб-графов для части сайтов. Данные матрицы обработаны и на их основе получены неориентированные графы. Для них также вычислен вектор Майерсона. В данном случае вес каждой страницы учитывает наличие всех гиперссылок между страницами.

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

Список использованной литературы включает 69 наименований.

Приложение 1 содержит листинги 'программного комплекса, разработанного в пакете Ма^ета^са, в котором выполнялось численное моделирование.

В Приложение 2 приведены все возможные графы с 4 помеченными вершинами и выигрыши г-го игрока, соответствующие каждому графу.

Глава 1

Вектор Майерсона в коммуникационной игре,

ограниченной деревом

Ситуация, в которой любое подмножество множества N игроков может сформировать коалицию и сотрудничать, получая определенные выплаты, может быть описана кооперативной игрой с трансферабельной полезностью (ТП-игрой). Однако, существует много реальных ситуаций, для которых требуется модель, принимающая во внимание ограничения в сотрудничестве. Рассмотрим ТП-игру с ограниченной кооперацией ^ представленной неориентированным коммуникационным графом, введённую Майерсоном [56] . Вершины графа представляют игроков, а рёбра представляют связи между игроками. Игроки могут взаимодействовать напрямую, только если они связаны. Связь может быть информационной, технологической, транспортной, её наличие может обозначать отношения дружбы или сотрудничества. Вершины могут быть отдельными людьми, организациями, странами или веб-страницами. Это приводит к так называемой коммуникационной (сетевой) игре, заданной тройкой, состоящей из конечного множества игроков, характеристической функции и графа. Хорошо известным решением коммуникационной игры является вектор Майерсона, который характеризуется компонентной эффективностью и справедливостью. Эффективность означает, что для каждого компонента графа общая выплата игрокам равна ценности этого компонента. Понятие справедливости означает, что удаление связи между двумя игроками приводит обоих игроков к одинаковым изменениям в выплате.

1.1. Основные понятия и определения

Пусть N — {1,2,... ,п} множество игроков. Через 2м обозначим множество всех его подмножеств.

Определение 1.1. Кооперативной игрой п лиц будем называть пару

< ЛГ; у >, где N = {1,2,..., п} — множество игроков, а V : 2Ы —К отображение, предписывающее каждой коалиции £ € некоторое численное значение такое, что г>(0) = 0. Функция V называется характеристической функцией кооперативной игры [3, И].

Майерсон первым адаптировал теорию кооперативных игр к структурам, учитывающим информацию о сетевых связях игроков. Он ввёл так называемую коммуникационную игру.

Определение 1.2. Коммуникационной игрой называется тройка

< >, где N — множество игроков, V — характеристическая функция ид— граф. <■>,

Кооперативная структура на множестве игроков N задается посредством графа.

Определение 1.3. Неориентированным графом называется пара д = (./V, Е), где N - конечное множество вершин, Е - множество рёбер. Рёбра представляют неупорядоченные пары^вершин, которые мы будем обозначать у, и Ц 6 Е означает, что вершины I Е N и э е N связаны в графе д.

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

Граф, получаемый удалением из существующего графа д связи у мы будем обозначать д — гз, а граф, получаемый добавлением в граф д связи Ц обозначим 9 + гз-

Определение 1.4. Для графа д последовательность различных вершин {¿1,..., гк\, к > 2 есть путь от до %к, если для всех к = 1,..., к — 1,

44+1 € 9В [2] такой путь называют простым путём, а в [24] простой цепью.

Длина пути I — число рёбер в нём, I = к — 1. Расстоянием между двумя вершинами является длина минимального пути между этими вершинами.

\ ПИЧ , .

Вершины i,j € N называются связными в графе д, если найдется путь {гь..., ik} д, такой что i\ = г и гк = j.

Граф связен, если в нем связны каждые две вершины.

Максимальный связный подграф графа д называется компонентой связности или просто компонентой графа д.

Ребро ij является мостом в графе д, если д — ij имеет больше компонент, чем д.

Для каждого графа д на множестве игроков N и любой коалиции S С N множество ребер {{г, j} € g\i,j £ S} определяет подграф pis.

Коалиция S С N называется связной в графе д, если подграф связен.

Любая коалиция S С N единственным образом разбивается графом д на максимальные связные подкоалиции, называемые компонентами связности. Множество всех связных компонент коалиции S обозначим через S\g.

S\g = {{г|г и j связаны в S через g}\j £ 5}.

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

N\g означает множество всех связных компонент в д.

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

Джексон и Волынски [51] предложили более богатую модель, чем коммуникационная игра, где ценность, производимая игроками, напрямую зависит от структуры сети и определяется функцией стоимости (value function).

Определение 1.5. Функция стоимости это функция v : д —» R, такая что г?(0) = 0, где под 0 подразумевается пустая сеть (сеть, не имеющая связей).

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

Определение 1.6. Сетевая игра это пара < ЛГ; у >, где N — множество игроков, V функция стоимости.

Функция стоимости является компонентно аддитивной, если

у(9) =

д'еЩд

УдеО,д'еЩд.

Определение 1.7. Правило распределения это функция У : (7 XV В!1 такая что ^ Уг(у,д) — у(д).

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

Вектор Майерсона

Майерсон [56] определил и охарактеризовал правило распределения для коммуникационных игр, являющееся обобщением вектора Шепли. Впоследствии это правило было названо вектором Майерсона [30].

Для данного графа д и характеристической функции у вектор Майерсона У {у, д) = (Уг(у, д),..., Уп(у, д)) определяется следующими аксиомами:

Аксиома компонентной эффективности. Если Я связная компонента графа д, то сумма выигрышей игроков коалиции 5 равна ценности всей коалиции, т.е \/в е ЛГ|<7

^2Ъ(у,д) = у(3). (1.1)

ieS

Аксиома справедливости. Уд, Уг? Е д оба игрока одинаково получают выгоду или теряют от создания связи

Уг(у, д) - У{(у, д - %з) = УАу, д) - У^у, д - г?').

> К ; ! I I ■ 1 и и

(1.2)

Если для любой игры V и любого графа g определить характеристическую функцию как

vg(S) = Y, VS (1-3)

KeS\g

ТО

Y(v,g) = (f(vg),

где ip(vg) — вектор Шепли.

Джексон и Волынски [51] предложили обобщение вектора Майерсона в контексте сетевых игр. Это правило распределения задаётся следующим образом.

Yi(v,g)= £ (1.4)

ScN\{i}

где a=\S\, n = \N\.

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

1.2. Модель коммуникационной игры, ограниченной деревом Характеристическая функция '

Рассмотрим игру, в которой граф является деревом Г, состоящим из п вершин, а характеристическая функция задаётся подобно схеме, предложенной Джексоном 1 [50,51]: каждая прямая связь — путь длиной 1 — приносит игрокам доход г, где 0 < г < 1. Кроме того, игроки также извлекают выгоду

11 ' ' '

из косвенных (непрямых) связей, но уже меньшую. За каждый путь длиной 2 коалиция получает г2, за путь длиной 3 — г3 и т. д. Для любой коалиции S

ХВ модели связей (connections model), введённой Джексоном и Волынски, таким образом задаётся полезность каждого игрока. Кроме того, в модель включена стоимость поддержания связи.

можно записать

L

v(S) = air + a2r2 + • • • + akrk + • • • + aLrL = ^ akrk, (1.5)

k=i

где L — максимальное расстояние между двумя вершинами в данной коалиции (диаметр графа g\s)-,

— число путей длины к в данной коалиции.

v(i) = 0, Vi е N.

Пример 1.1.

Для дерева на Рисунке 1.1 длина максимального пути между игроками в гранд-коалиции (радиус дерева) L — 4; пути длины 1: {1,2}, {1,3}, {2,4}, {2,5}, {3,6}, т.е. ai = 5, длины 2: {1,2,4}, {1,2,5}, {4,2,5}, {2,1,3}, {1,3,6}, а2 = 5, длины 3: {3,1,2,4}, {3,1,2,5}, {2,1,3,6}, а3 = 3 и длины 4: {4,2,1,3,6}, {5,2,1,3,6}, а4 = 2. Характеристическая функция для гранд-коалиции равна

v(N) = 5г + 5г2 + 3 г3 + 2 г4.

Для коалиции Б = {1,2,4,5} максимальное расстояние между игроками Ь = 2; число путей длины 1: а\ = 3, длины 2: а2 = 3 и характеристическая функция равна

г>(5) = 3 г + 3 г2.

Коалиции 5 = {2,4,5,3,6} не является связной. Она разбивается графом д на две коалиции: Б\д — {{2,4,5}, {3,6}}. В первой максимальное расстояние равно 2, число путей длины 1: а\ = 2, длины 2: й2 = 1. Во второй максимальное расстояние равно 1 и есть только один путь длины 1. Тогда с учётом формулы 1.3 характеристическая функция равна

Характеристическая функция может быть вычислена с использованием матрицы смежности.

Определение 1.8. Матрицей смежности графа д с п вершинами называется квадратная матрица порядка п, элементы которой определяются следующим образом:

Список литературы диссертационного исследования кандидат наук Трухина, Людмила Ивановна, 2013 год

Литература

1. Аксенова Е. А. Оптимальное управление двумя параллельными стеками / Е. А. Аксенова, А. В. Соколов // Дискретная математика. — 2007. — Т. 19, вып. 1. — С. 67-75.

2. Алексеев В. Е. Графы. Модели Вычислений. Структуры Данных / В. Е. Алексеев, В. А. Таланов. — Нижний Новгород : Изд-во Нижегородского университета, 2004. — 294 с.

3. Васин А. А. Теория игр и модели математической экономики / А. А. Васин, В. В. Морозов. - М. : МАКС Пресс, 2005. — 272 с.

4. Васин А. А. Исследование операций (учебное пособие) / А. А. Васин, П. С. Краснощеков, В. В. Морозов. — М.: Издательский центр Академия, 2008.

- 278 с.

5. Воробьев Н. Н. Основы теории игр. Бескоалиционные игры / Н. Н. Воробьев. — М. : Наука, 1984.

6. Воробьев Н. Н. Теория игр для экономистов-кибернетиков / Н. Н. Воробьев.

- М. : Наука, 1985. — 272 с.

7. Горбунов А. Л. Марковские модели посещаемости веб-сайтов. // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску. — Екатеринбург : Изд-во Урал, ун-та, 2007. — С. 65-73.

8. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн. — 2-е изд. — М.: «Вильяме», 2006. — 1296 с.

9. Мазалов В. В. Об одном методе динамического распределения нестраничной памяти. // Программирование. — 1995. — № 4. — С. 183-185.

10. Мазалов В. В. Оптимальное распределение памяти компьютера для пуас-соновских потоков / В. В. Мазалов, М. Тамаки, С. В. Винниченко // Автоматика и телемеханика. — 2008. — № 9. — С. 69-75.

11. Мазалов В. В. Математическая теория игр и приложения: учебное пособие / В. В. Мазалов. — С-Пб. : Лань, 2010. — 448 с.

12. Мазалов В. В. О рейтинге официальных сайтов научных учреждений северо-запада России / В. В. Мазалов, А. А. Печников // Управление большими системами. — М.:ИПУ РАН, 2009. — Выпуск 24. — С.130-146.

13. Мазалов В. В. ]Ч-Ядро и распределение памяти компьютера / В. В. Мазалов, Л. И. Трухина // Труды 6-й Московской международной конференции по исследованию операций (СЖМ 2010): Москва, 19-23 октября 2010 г. — М. : МАКС Пресс, 2010. - С. 345-346.

14. Мазалов В. В. п-Ядро и распределение памяти компьютера / В. В. Мазалов, Л. И. Трухина // Вычислительные технологии. — 2011. — том 16, №6.

- С. 48-53.

15. Мулен Э. Теория игр с примерами из математической экономики / Э. Му-лен. - М. : Мир, 1985. — 200 с.

16. Мулен Э. Кооперативное принятие решений: аксиомы и модели / Э. Мулен.

- М.: Мир, 1991. - 464 с.

17. Нейман Д. Теория игр и экономическое поведение / Д. Нейман, О. Мор-генштерн. — М. : Наука, 1970. — 709 с.

18. Оуэн Г. Теория игр / Г. Оуэн. - М. : Мир, 1971. — 230 с.

19. Петросян Л. А. Теория игр / Л. А. Петросян, Н. А. Зенкевич, Е. А. Семина.

- М. : Высшая школа, 1998. — 300 с.

20. Печников А. А. Модель университетского Веба. // Вестник Нижегородского университета им. Н.И. Лобачевского. — 2010. — №6. — С. 208-214.

21. Печников А. А. Об исследованиях веб-графа сайта / А. А. Печников, Д. И. Чернобровкин // Материалы конференции «Управление в технических, эргатических, организационных и сетевых системах». — СПб. : «Концерн «ЦНИИ «Электроприбор», 2012. - С. 1069-1072.

22. Печников А. А. Адаптивный краулер для поиска и сбора внешних гиперссылок / А. А. Печников, Д. И. Чернобровкин // Управление большими системами. Выпуск 36. — М.: ИПУ РАН, 2012. - С. 301-315.

23. Трухина Jl. И. Принцип дележа для коммуникационной игры. // Учёные записки Заб. гос. гум.-пед. унив-та им. Н.Г. Чернышевского, серия Физика, математика, техника, технология. — 2012. — №3(44). — С.126-132.

24. Харари Ф. Теория графов / Ф. Харари. — М. : Мир, 1973. — 301 с.

25. Харари Ф. Перечисление графов / Ф. Харари, Э. Палмер. — М. : Мир, 1977. - 326 с.

26. Almind Т., Ingwersen P. Informetric Analyses on the World Wide Web: Methodological Approaches to "Webometrics"// Journal of Documentation. - 1997. - no. 53(4). - Pp. 404-426.

27. Amer R., Carreras F. Games and Cooperation Indices // International Journal of Game Theory. - 1995. - no. 24(3). - Pp.239-258.

28. Aumann R., Dreze A. Cooperative Games with Coalition Structure // International Journal of Game Theory. — 1974. — Vol. 4. — Pp. 217-237.

29. Aumann R., Maschler M. Game-teoretic analysis of a bankruptcy problem from the Tulmud // Journal of Economic Theory. — 1985. — no. 36. — Pp. 195-213.

30. Aumann R., Myerson R. Endogenous Formation of Links Between Players and Coalitions: An Application of the Shapley Value, In: Roth, A. (ed.) The Shapley Value. — Cambridge University Press.— 1988.— Pp. 175-191.

31. Bala V., Goyal S. A Strategic Analysis of Network Reliability // Review of Economic Design. — 2000. — no. 5. — Pp. 205-228.

32. Banzhaf J.F. Weighted voting doesn't work: mathematical analysis // Rutgers Law Review. - 1976. - no. 19. - Pp. 317-343.

33. Borm P., Owen G., Tijs S. On the Position Value for Communication Situations // SIAM Journal on Discrete Mathematics. — 1992. — no. 5(3). — Pp. 305-320.

34. Borm P., van den Nouweland A., Tijs S. Cooperation and Communication Restrictions: A Survey. In R.P. Gilles and P.H.M. Ruys (eds.) Imperfections and Behavior in Economic Organizations, Kluwer Academic Publisher, Boston, 1994.

35. Broder A., Kumar R., Maghouli F., Raghavan P., Rajagopalan S., Stata R., Tomkins A., Wiener J. Graph structure in the web // Journal of Computer Networks. - 2000. — no. 33(1-6). - Pp. 309-320.

36. Calvo E., Lasaga J., van den Nouweland A. Values of games with probabilistic graphs // Mathematical Social Sciences. — 1999. — no. 37. — Pp. 79-95.

37. Currarini S., Morelli M. Network Formation with Sequential Demands // Rev. Econom. Design. — 2000. - no 5. — Pp. 229-250.

38. Deegan J., Packel E. W. A new index of power for simple n-person games // International Journal of Game Theory — 1978. — no. 7. — Pp. 113-123.

39. Dutta B., Jackson M. O. The Stability and Efficiency of Directed Communication Networks // Rev. Econom. Design. — 2000. — no. 5. — Pp. 251-272.

40. Dutta B., Jackson M. O. On the Formation of Networks and Groups // Networks and Groups: Models of Strategic Formation, Heidelberg: SpringerVerlag.— 2003.

41. Dutta B., Mutuswami S. Stable Networks // J. Econom. Theory. — 1997. — no. 76. - Pp. 322-344.

42. Dutta B., van den Nouweland A., Tijs S. Link Formation in Cooperative Situations // Int. J. Game Theory. — 1998. — no. 27. — Pp. 245-256.

43. Erdôs P., Rényi A. On random graphs I // Publ. Math. Debrecen. — 1959. — Vol. 6. - Pp. 290-297.

44. Erdôs P., Rényi A.' On the evolution of random graphs // Publ.Math. Inst. Hungar. Acad. Sci. - 1960. - Vol. 5. - Pp. 17-61.

45. Fernandez J. R., Algaba E., Bilbao J. M., Jimenez A., Jimenez N., Lopez J. J. Generating functions for computing the Myerson Value // Annals of operation research. — 2002. — no. 109. — Pp. 143-158.

46. Jackson M. O., Watts A. The Existence of Pairwise Stable Networks // Seoul J. Econom. - 2001. - Vol. 14. - no. 3. - Pp. 299-321.

47. Jackson M. 0., Watts, A. The Evolution of Social and Economic Networks // J. Econom. Theory. - 2002. - Vol. 106. - no. 2. - Pp. 265-295.

48. Jackson M. O. The Stability and Efficiency of Economic and Social Networks // Advances in Economic Design. — 2003.

49. Jackson M. O. Allocation Rules for Network Games. Games and Economic Behavior. -2005. - no. 51(1).- Pp. 128-154.

50. Jackson M. O. Social and economic networks. — Princeton University Press, 2008. - 647 p.

51. Jackson M. O., Wolinsky J. A strategic model of social and economic networks // Journal of Economic Theory. — 1996. — no. 71(1). — Pp. 44-74.

52. Jamison R. E. Alternating Whitney sums and matchings in trees, part 1 // Discrete Mathematics.— 1987. — no. 67. — Pp. 177-189.

53. Holler M. J., Forming coalitions and measuring voting power // Political Studies. - 1982. - no. 30. - Pp. 262-271.

54. Kurz M. Coalition value, in the Shapley value // Essays in honor of Lloyd S. Shapley. — Cambridge university press, 1988. — Pp. 155-173.

55. Mazalov V. Trukhina L. Application of the Myerson value for the analysis of the academic sites // Collected abstracts of papers presented on the International Conference Game Theory and Management, St. Petersburg, Russia. — 2013. — Pp. 156-158.

56. Myerson R. B. Graphs and cooperation in games // Mathematics of Operations Research. - 1977. - no. 2. - Pp. 225-229.

57. Myerson R. B. Game Theory: Analysis of Conflict.— London: Harvard Univ. Press, 1997. - 569 p.

58. Newman M. E. J. A measure of betweenness centrality based'on random walks http : //aps. arxiv. org/pdf/cond-mat/0309045.pdf

59. Owen G. Values of games with a priori unions // In: R. Henn, O. Moeschlin, eds., Mathematical economics and game theory. — Essays in honor of Oskar

Morgenstern. Lecture Notes Econ. and Math.Syst. Berlin: Springer, 1977. — Vol. 141. — Pp. 76-88.

60. Padgett J. F., Ansell C. K. Robust action and the rise of the Medici, 1400-1434 // Am. J. Sociol. - 1993. - no. 98. -Pp. 1259-1319.

61. Page F. Farsighted Stability in Network formation // Group Formation in Economics: Networks, Clubs, and Coalitions. — Cambridge: Cambridge University Press, 2003.

62. Page F., Wooders M., Kamat S. Networks and Farsighted Stability. — DP University of Warwick, 2001.

63. Schmeidler D. The nucleolus of a characteristic function game // SIAM. Journal of Applied Mathematics. —1969. — no. 17. — Pp. 1163-70.

64. Shapley L. S. A value for n-person games // Annals of Mathematical studies,

- 1953. - no. 28. - Pp. 307-317.

65. Shapley L. S., Shubik M. A method for evaluating the distribution of power in a committee system // American Political Science Review. — 1954. — no. 48.

- Pp. 787-792.

66. Slikker M. Link Monotonie Allocation Schemes // International Game Theory Review. - 2005. - no. 7(4). - Pp. 473-489.

67. Slikker M., . Gilles R. P, Norde H., Tijs S. Directed Networks, Allocation Properties and Hierarchy Formation // Mathematical Social Sciences. — 2005.

- no. 49(1). - Pp. 55-80.

68. Talman D., Yamamoto Y. Average Tree Solutions and Subcore for Acyclic Graph Games // Journal of the Operations Research Society of Japan. — 2008,- no. 51(3). - Pp. 187-201.

69. Watts A. A Dynamic Model of Network Formation // Games and Econom. Behavior. - 2001. - no. 34. - Pp. 331-341.