автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Кооперативные решения в задачах анализа информационных сетей

На правах рукописи

Трухина Людмила Ивановна

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

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

г 1 ноя 2013

Петрозаводск — 2013 005538607

005538607

Работа выполнена в ФГБОУ ВПО «Забайкальский государственный университет:

Научный руководитель: доктор физико-математических наук,

профессор

Мазалов Владимир Викторович Официальные оппоненты: Печников Андрей Анатольевич,

доктор технических наук, доцент, ведущий научный сотрудник лаборатории телекоммуникационных систем ФГБУН Институт прикладных математических исследований Карельского научного центра Российской академии наук Седаков Артём Александрович, кандидат физико-математических наук, ФГБОУ ВПО «Санкт-Петербургский государственный университет», старший преподаватель кафедры математической теории игр и статистических решений

Ведущая организация: ФГОУ ВПО «Московский Государственный

Университет имени М.В. Ломоносова»

Защита состоится «25» декабря 2013 г. в 14:00 на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан «М^» ноября 2013 года.

Ученый секретарь диссертационного совета /:->""" В. Воронов

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 статьи в журналах, входящих в перечень ВАК ведущих периодических изданий [2,3] и тезисы 2 докладов [1,4].

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

Содержание работы

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

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

В разделе 1.1 приведены основные понятия и определения, используемые в работе.

Определение 1. Коммуникационной игрой называется тройка < Ы\у\д >, где N — множество игроков, V — характеристическая функция ид— граф.

Для данного графа д и характеристической функции V вектор Майер-сона У {у, д) = (У^ь, <?),..., Уп(у, д)) определяется следующими аксиомами: Аксиома компонентной эффективности. Если 5 связная компонента графа д, то сумма выигрышей игроков коалиции 5 равна ценности всей коалиции, т.е € М\д

(1)

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

Уг(у,д)-Ъ{у,д- у) = У,(у,д) -Уу(у,д-1]). (2)

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

= ^ "(П ^ (3)

то

У(ь,д) =

где ¡р(ьд) — вектор Шепли,

Б\д — множество всех связных компонент коалиции 5, на которые она разбивается графом д.

В разделе 1.2 описаны способ задания характеристической функции и процедура получения дележа.

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

6

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

L

v (S) = air + a2r2 Н----+ акгк + • • • + aLrL = акгк, (4)

к=1

где L — максимальное расстояние между двумя вершинами в данной коалиции;

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

v(i) = 0, Vi е N.

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

и(5) = Z) Z) Wo}r+1С /{^=о}/(4>о}г2 + • • •

¿=1 j=i+l 1=1 j=i+1 ^

г=1 з=г+1

где I — индикатор.

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

Опишем процедуру получения дележа для произвольного игрока г. Шаг 1. Два напрямую связанных игрока получают г. По отдельности они не получат ничего, поэтому каждый из них вправе рассчитывать на половину, т.е. выигрыш составит Но если игрок участвует в нескольких таких связях, то он получит | от каждой. Значит, его выигрыш нужно умножить на количество путей длины 1, содержащих этого игрока.

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

Рассуждая аналогичным образом, и суммируя выигрыши каждого шага, получим делёж:

Ai Ai Ai . ^, Ai

«о

к=Х

где А\ — число путей длины к, содержащих игрока i

В работе доказана следующая теорема.

Теорема 1. Делёж (6) удовлетворяет аксиомам компонентной эффективности и справедливости, и, следовательно, является вектором Майерсона.

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

Рассмотрим дерево gp = (iV, Е) с корнем в вершине р. Введём в рассмотрение производящую функцию

L

Мх) = J2alixk k=1

где apk — число путей, состоящих из к игроков (длины к - 1), содержащих вершину р.

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

Производящая функция вычисляется рекуррентно. В финальных вершинах q дерева др положим

Фч{х) =

Для всех вершин дерева q, не являющихся корнем р, функция равна

+ (7)

где сумма берётся по всем потомкам г = 1,..., й вершины д. Для корня дерева р положим

'^(ж) = х 1 + +

\ «'=1

где сумма берётся по всем потомкам ди г = 1,.... а! вершины р.

В разделе 1.4 показано, что сложность алгоритма для вычисления вектора Майерсона по формуле (6) с использованием производящей функции составляет 0(пй1 + пс), где с — число ненулевых коэффициентов <ртр(х).

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

Работа частично поддержана грантом РФФИ, проект 13-01-91158-ГФЕН-а.

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

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

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

Для любой коалиции 5 можно записать

ь

у(Э) = счг + а2г2 + • • ■ + акгк + • • • + а^ = ^ акгк, (9)

к=1

где Ь — максимальное расстояние между двумя вершинами в данной коалиции;

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

_ у (г) = 0, Ые N.

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

и(5) "ЕЕ ,г/'- + Е Е /К=о}47'2 +

г=1 j=i + l г=1 j=i+l

+ Е Е 7к,=°}/{4=О}-.-«^"1-

г=1 7=»-И

Как уже упоминалось, две вершины могут быть связаны несколькими путями. Чтобы это учесть в данной формуле вместо индикатора /{о*>0} в каждой сумме используется элемент матрицы = 1,.. . , з — 1, который и показывает количество путей.

Делёж для г-го игрока в данной игре может быть найден по формуле аналогичной формуле (6).

где А\ — число кратчайших путей длины к, содержащих игрока г.

Доказана следующая теорема.

Теорема 2. Для игры с коммуникационной структурой, заданной произвольным графом делёж (11) удовлетворяет аксиомам компонентной эффективности и справедливости, и, следовательно, является вектором Майерсона.

В разделе 2.2 показано, что сложность алгоритма вычисления дележа по формуле (11) составляет 0(п3).

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

В разделе 2.4 приведены численные примеры.

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

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

Для графов с двумя и тремя вершинами перебрать все возможные помеченные графы не составляет труда.

Для п = 2 возможны два графа: пустой граф и граф с одним ребром. Среднее значение характеристической функции равно

ир(Л0 = рг + (1 — р) ■ 0 = рг.

Средний выигрыш

уР _ V? — рг

П - - у-

Максимум Удостигается при р = 1 и г = 1 и равен 0,5.

Для п = 3 существует бз = 2^^ = 8 помеченных графов, которые представлены на рис. 1.

Среднее значение характеристической функции равно

г,(Л0 = (1 -р)3 ■ 0 + Зр(1 -р)2г + Зр2(1 -р)(г + 2г2) +р3Зг =

= 3рг + 3р2г2 - 3р3г2.

г1 / ♦! Л!

1 3 V 3 2 \з 2 3 7/ \з 2/ 3 2 \з 1/ \3

• « • •

Рис. 1: Помеченные графы с тремя вершинами.

Средний выигрыш

У? = v(N)/3 = рг+р2г2 - р3г2, г = 1,2,3.

Максимум У^ также достигается при р = 1 и г — 1 и равен 1. Для п = 4 возможных графов уже 64 = = 64. Среднее значение

характеристической функции равно

у(М) = брг + 12р2г2 - 12р3г2 + 12р3г3 - 36р4г3 + 36р5г3 - 12р6г3.

Средний выигрыш

У? = V(Дг)/4 = ^ + Зр2г2 - 3р3г2 + Зр3г3 - 9р4г3 + 9р5г3 - 3р6г3, г = 174.

В данном случае максимум достигается при р = 0,849419 и г = 1 и равен 1,60634.

Для п = 5 существует С5 = = 1024 помеченных графа. Среднее

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

и(ЛГ) = Юрг + 30р2г2 - З0р3г2 + 60р3г3 - 180р4г3+ +120р5г3 + 120р6г3 - 180р7г3 + 60р8г3 + 60Л4 - 360р5г4+

+900р6г4 - 1200р7г4 + 900р8г4 - 360р9г4 + 60р1Ог4.

Средний выигрыш

У[ = 2рг + 6р2г2 - 6р3г2 + 12р3г3 - З6р4г3 + 24р5г3+

+24р6г3 - З6р7г3 + 12р8г3 + 12р4г4 - 72р5г4 + 180р6г4-—240р"г4 + 180р8г4 - 72рэг4 + 12р10г4, г = 175.

В данном случае максимум У? достигается при р = 0,785204 и г = 1 и равен 2,38752.

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

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

Во третьей главе рассматривается теоретико-игровой подход к определению оптимального способа перераспределения памяти компьютера.

Память размера М разбита на п частей. Длины разбиений обозначим

таь т2) • • ■ ,тп, ту + тп2 + • • • + тп = М — целые числа. Информация в

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

12

Р» = 1- (вероятностные характеристики известны). Предполагается, что информация поступает в виде порций единичной длины, и заполнение каждого участка осуществляется с одного конца. Работа начинается с пустой структуры данных. Текущие длины занятых участков обозначим /сь к2,..., кп. Тогда ¿г = т,1 — кг — свободная память г-го участка.

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

В разделе 3.1 описывается оптимальная схема распределения памяти. Пусть свободная память представлена вектором (с!ь ..., ¿п), где > О, г = 1,п. Обозначим через Т(о! ь... ,в,п) среднее время до первого переполнения. Оно удовлетворяет уравнению

п

Т{(11,...,йп) = 1 + ^^№,...,^-1,...,^) (12)

¿=1

с граничным условием Т(с/Ь ..., ¿п) = 0, если хотя бы для одного г ^ = 0. Тогда оптимальный алгоритм перераспределения может быть описан следующим образом. Предположим, что функция Т{д.\, ... ,йп) вычислена для всех наборов ..., <1п). Тогда при заполнении одного из участков, например £¿1 = 0, поступаем следующим образом. Разделяем оставшееся свободное

п

пространство Э = ^ сЦ на новые сегменты ,..., ¿п) таким образом, что-¿=1

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

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

В 1985 году Ауманн совместно с Машлером рассмотрели задачу о

банкротстве на основе одного из текстов, представленных в Талмуде. За-

13

дача о банкротстве определяется как пара (E\d), где Е — состояние, d =

(di, ¿2,..., dn), di < d2 < ■ ■ ■ < du — требования и 0 < E < d\ + d2 H-----1- dn.

Решение данной задачи вектор х = (xi, х2, ■.., хп) действительных чисел, где

Х\ + х2 Н-----1- хп — Е.

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

Пусть произошло переполнение одного из участков. Сформируем кооперативную игру, связанную с задачей распределения памяти. Игроками являются процессы, которым выделена память. Предположим, что потребность в памяти для каждого процесса равна объёму уже заполненной памяти. Тогда по аналогии с задачей о банкротстве требованиями игрока будем считать объём занятой памяти, а суммарную свободную память — "состоянием":

ki, • ■ • 1 кп — размеры заполненных участков — требования каждого игрока;

ki + k2 + ... + kn = К — суммарные требования; di + ¿2 + ••• + dn = D — свободная память — состояние. Тогда характеристическую функцию для каждой коалиции определим так же как в задаче о банкротстве

v(S) = (D- £ (13)

i&N\S

где a+ = max(a, 0). Тогда v(N) = D — объем свободной памяти, который нужно перераспределить между п участками.

Делёж, образующий n-ядро, определяется при помощи коалиционной процедуры. Упорядочим участки памяти по возрастанию требований (занятого объёма). На первом шаге игроки объединяются в две коалиции: {1} — первый участок памяти и {2, ..., п} — остальные участки. Если выполняется неравенство п—- < D < К — п-^, то D делится между {1} и {2, ..., п} по принципу "contested garment т.е. спорное количество делится поровну, и каждый игрок дополнительно получает количество, уступленное другим. Тогда получаем следующий делёж:

X! =---^— + (в -

— выигрыш первого игрока или объём памяти, выделенный первому участку,

£>_(£>_ *!)+ - (Я-¿¿¡) + *2 = ----+ {Е)_ к1) +

— выигрыш коалиции {2, ..., п} или объём памяти, выделенный остальным участкам.

кх

Если В < п~—, то свободная память делится поровну. Если к\

В > К — п—, то назначаются равные потери:

К - В ^ , К - о

= Й1---—, х2 = 2^ кг -

2 ' ^ 2 ' 1=2

На втором шаге коалиция {2, ... , п} разбивается на две: {2} и {3, ..., и} и повторяется вышеописанная процедура для (п — 1) игрока. И т.д. В разделе 3.2.2 приведён модифицированный алгоритм. Оставим в рассмотрении только свободную память. Участки упорядочим по убыванию свободной памяти. Если ¿\ + ¿2 + ■ ■ ■ + <1п = В > ^-гг, то каждому участку г (г = 1,п) выделяется половина его свободной памяти, а вторая половина делится поровну между участками с номерами от г + 1 до п. Таким образом,

й1 ¿2

^2 = —;-г Н--,

2(77 - 1) 2

= , 'гз 2(п - 1) 2(п - 2) 2 '

— — , ^2 «¿я-2 ^п-1

" " 2(гг — 1) + 2(п — 2) + " ' ' ~Г + Если условие не выполняется, то применяется алгоритм равного деления.

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

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

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

В разделе 4.1 описан первый этап, на котором был проведён анализ структуры веб-сайтов на примере официальных веб-сайтов государственных университетов и научных институтов (математической направленности) России.

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

Например, для сайта Института прикладных математических исследований Карельского научного центра РАН (ИПМИ КарНЦ РАН) наибольший вес имеет начальная страница (http://mathem.krc.karelia.ru/). На втором месте находится страница „Фотогалерея". И на третьем месте — "Мероприятия".

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

В Разделе 4.2 для полученного набора векторов проведён кластерный анализ, в результате которого получено два кластера.

1-й кластер: ИМ им. Соболева, СПб ЭМИ, ИПМИ КарНЦ, ЦЭМИ, ИПМ им. Келдыша, МФТИ;

2-й кластер: МИ им. Стеклова, ИНГУ, Томский ГУ, Тюменский ГУ, Уральский ФУ, ТихоокеанскийГУ.

Сайт МФТИ имеет небольшое число страниц первого уровня, что характерно для сайтов институтов РАН, поэтому он находится с ними в одном кластере. Сайт математического института им. Стеклова наоборот, имеет большое число ссылок с главной страницы и попадает в кластер ВУЗов.

В Разделе 4.3 приведены результаты исследования веб-графов сайтов.

Веб-граф сайта — ориентированный граф, в котором вершины соответствуют веб-страницам, а направленные ребра — соединяющим страницы гиперссылкам.

В результате работы программы-краулера были получены матрицы смежности веб-графов сайтов г.

Чтобы вычислить вектор Майерсона, граф должен быть обыкновенным (без кратных рёбер и петель), неориентированным. Поэтому матрицы смежности были преобразованы. Во-первых, элементы матрицы, имеющие значения больше 1 (что означает наличие нескольких гиперссылок между двумя страницами), были заменены на 1. Во-вторых, чтобы сделать граф неориентированным, элементы матрицы, равные единице, были зеркально отражены относительно главной диагонали. Это можно сделать на том основании, что, если с одной страницы на другую есть ссылка, то в качестве обратной ссылки можно считать кнопку „назад" браузера.

Для графа сайта ИПМИ КарНЦ, полученного после вышеописанных преобразований, был вычислен вектор Майерсона.

Наибольший вес имеет начальная страница. На втором месте „Лаборатория теории вероятностей и компьютерной статистики". На третьем месте „Веб-ресурсы ИПМИ". На четвёртом несколько страниц: „История института", „Научная деятельность", „ИПМИ. Проекты", „ИПМИ. Публикации",

'Данные предоставлены Чернобровкиным Д. И., аспирантом Санкт-Петербургского государственного уггиоерситета.

Наибольший вес имеет начальная страница. На втором месте „Лаборатория теории вероятностей и компьютерной статистики". На третьем месте „Веб-ресурсы ИПМИ". На четвёртом несколько страниц: „История института", „Научная деятельность", „ИПМИ. Проекты", „ИПМИ. Публикации", „ИПМИ. Сотрудники1"', „Математические ресурсы Интернет", „Контактная информация". И на пятом месте „ИПМИ. Мероприятия".

Данные результаты достаточно похожи на результаты ранжирования страниц на основе PageRank, приведёнными в работе [5].

В заключении приведены основные результаты работы.

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

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

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

Список публикаций по теме диссертации

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

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

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

4. Mazalov V. Trukhina L. I. Application of the Myerson value for the analisis of the academic sites /'/ Collected abstracts of papers presented on the International Conference Game Theory and Management, St Peterburg, Russia, 2013, Pp. 156-158.

Цитированная литература

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

6. Jackson М. О. Social and economic networks. — Princeton University Press, 2008. - 647 p.

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

Забайкальский государственный университет

04201453196

На правах рукописи

Трухина Людмила Ивановна

КООПЕРАТИВНЫЕ РЕШЕНИЯ В ЗАДАЧАХ АНАЛИЗА ИНФОРМАЦИОННЫХ СЕТЕЙ

05.13.18 — «Математическое моделирование, численные методы и комплексы

программ»

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор

В. В. Мазалов

Петрозаводск - 2013

Оглавление

Введение........................................................................4

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

деревом..........................................................................13

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

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

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

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

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

1.5.1. Цепь..............................................................32

1.5.2. Звезда............................................................33

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

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

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

графом..................................................................39

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

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

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

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

2.4. Примеры................................................................47

2.5. Коммуникационная игра, ограниченная случайным графом ... 51 Глава 3. И-ядро и распределение памяти компьютера......................58

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

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

3.2.1. ]Ч-ядро ..........................................................60

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

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

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

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

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

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

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

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

Заключение ....................................................................96

Литература......................................................................98

Приложение 1.................................104

Приложение 2.................................110

Введение

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

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

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

Основы классической кооперативной теории были заложены Дж. фон Нейманом и О. Моргенштерном [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 рисунков.

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

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

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