Кооперативные решения в задачах анализа информационных сетей

• Автор: Трухина, Людмила Ивановна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Петрозаводск
• Количество страниц: 111 с. : ил.

Оглавление
Введение
Глава 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. М-ядро и распределение памяти компьютера
3.1. Оптимальная схема распределения памяти
3.2. 14-ядро в распределении памяти
3.2.1. 14-ядро
3.2.2. Модифицированный алгоритм
3.2.3. Равное деление

3.3. Численные эксперименты
Глава 4. Анализ структуры информационных сетей на примере анализа академических сайтов
4.1. Анализ структуры академических веб-сайтов
4.2. Кластерный анализ
4.3. Анализ веб-графов академических сайтов
Заключение
Литература
Приложение
Приложение
Введение
Актуальность темы.
Процесс информатизации общества носит глобальный характер. Многие практические задачи, связанные с информационными сетями, можно представить в виде игры с сетевой структурой. Данный раздел теории игр изучает как методы формирования связей между игроками (игры формирования сетей), так и правила определения выигрышей игроков с учётом этих связей. Игроки в сетях, как правило, действуют индивидуально, руководствуясь личными интересами. Поэтому основным аппаратом являются бескоалиционные игры, в которых каждый игрок независимо выбирает свою стратегию. Однако для оптимизации структуры сетей, потоков в них можно и нужно применять методы кооперативной теории игр.
Кооперативные игры являются одним из разделов теории игр, которая находит широкое применение в различных областях — экономике, политике, биологии, военном деле, транспорте и т.д. Спектр приложений кооперативных игр в настоящее время огромен и постоянно расширяется. Поэтому изучение кооперативных игр является актуальной задачей. В данной работе предлагается использовать методы кооперативной теории.игр для анализа структуры информационных сетей и оптимального распределения ресурсов.
Основы классической кооперативной теории были заложены Дж. фон Нейманом и О. Моргенштерном [17], а затем развивались в различных направлениях многими авторами. Теория кооперативных игр связана с именами Р. Аума-на, Р. Майерсона, М. Машлера, Э. Мулена, Дж. Нэша, Г. Оуэна, Л. Шепли, Д. Шмайдлера, М. Шубика [15,16,18,29,57,63,64]. Большой вклад в развитие теории кооперативных игр внесли О. Н. Бондарева, Н. Н. Воробьев, Л. А. Петросян, Е. Б. Яновская и другие [5,6,19].
В теории кооперативных игр взаимодействие игроков формализуется с помощью понятия коалиции. Для игры п лиц коалицией является любое непустое

^Е(*->-+с,2-г2)4е(з'г+8 (2 -■’•2) =
£=1 Ь=1 4 '
1 ({п - 1) • га г + (га - 2) • (га - 1) • п ^
га 2

Для остальных игроков
Чу, д) = ^ • (у(М) - У) =
Гга 1) г 1 (п ~1)(та~ 2) 2 (" ~ !) (п - 1)(га - 2) ,,
v ; 2 2 6
1 га — 2 ,
= 2'Г + —‘Г’
г = 2, 3,... ,га.
Сравним с выигрышами игроков, полученными по формуле (1.7)
.. -*4} Лп о га — 1 (Д? _ 1 о
У‘ = Т'Г + Т'Г =—Г + Л1'’' =
га — 1 (га — 1) • (га — 2)
- г + 1=

га — 1 ( га —

А* /1* 1 С
У- = ^1.г + 1^.г2 = -- г+ "~-2- ■ г2 = 1 2 3 ~2 3 Г
1 га — 2 2 = - • г 4 г ,

г = 2, 3,..., га.
Выигрыши, вычисленные по формулам (1.4) и (1.7), совпадают.
Пример 1.5.
В рассматриваемой игре значение вектора Майерсона зависит от числа пу-