Теория ресурсных сетей

НАУЧНАЯ МЫСЛЬ
СЕРИЯ ОСНОВАНА В 2008 ГОДУ



Л.Ю. Жилякова, О.П. Кузнецов



ТЕОРИЯ РЕСУРСНЫХ СЕТЕЙ





znanium.com

Москва РИОР ИНФРА-М

   ФЗ    Издание не подлежит маркировке  
№ 436-ФЗ в соответствии с п. 1 ч. 2 ст. 1

УДК 519.711.74
ББК 22.18
     Ж72
          Авторы:
          Жилякова Л.Ю. — д-р физ.-мат. наук, ведущий научный сотрудник, Институт проблем управления им. В.А. Трапезникова РАН (Москва). Автор более 130 работ по проблемам искусственного интеллекта и интеллектуальных систем, динамической теории графов;
          Кузнецов О.П. — д-р техн. наук, профессор, заведующий лабораторией, Институт проблем управления им. В.А. Трапезникова РАН (Москва). Автор более 150 работ, в том числе двух монографий, по проблемам искусственного интеллекта и интеллектуальных систем, когнитивного анализа ситуаций, логического управления, динамической теории графов
          Рецензенты:
          Чеботарев П.Ю. — д-р физ.-мат. наук, заведующий лабораторией, Институт проблем управления им. В.А. Трапезникова РАН (Москва);
          Дмитриев М.Г. — д-р физ.-мат. наук, профессор факультета компьютерных наук, Национальный исследовательский университет «Высшая школа экономики» (Москва)
       Жилякова Л.Ю., Кузнецов О.П.
Ж72 Теория ресурсных сетей : монография / Л.Ю. Жилякова, О.П. Кузнецов. — М. : РИОР : ИНФРА-М, 2020. — 283 с. — (Научная мысль). — https://doi.org/10.12737/21451
          ISBN 978-5-369-01645-9 (РИОР)
          ISBN 978-5-16-012512-1 (ИНФРА-М, print)
          ISBN 978-5-16-102327-3 (ИНФРА-М, online)
          Излагается разработанная авторами теория ресурсных сетей — сетей, в которых узлы соединены каналами с ограниченными пропускными способностями. По каналам в дискретном времени происходит обмен однородным ресурсом с выполнением закона сохранения. Узлы отдают ресурс в зависимости от его количества по одному из двух правил с пороговым переключением. Дается классификация сетей по топологии и пропускным способностям. Исследуются динамика и асимптотика состояний и потоков для всех классов сетей. Представлен обширный обзор неклассических сетевых моделей.
          Книга предназначена специалистам по теории графов и исследованию операций, студентам, магистрантам и аспирантам, обучающимся по различным математическим, компьютерным и информационным направлениям подготовки.
УДК 519.711.74
                                                          ББК 22.18
Цветные иллюстрации доступны в электронной версии книги в электронно-библиотечной системе ZNANIUM по адресу http://znanium.com.
Ссылку для доступа вы можете получить при сканировании QR-кода, размещенного на обложке
ISBN 978-5-369-01645-9 (РИОР)
ISBN 978-5-16-012512-1 (ИНФРА-М, print)               © Жилякова Л.Ю.,
ISBN 978-5-16-102327-3 (ИНФРА-М, online)                Кузнецов О.П.

L.Yu. Zhilyakova, O.P. Kuznetsov





                RESOURCE NETWORK
                THEORY





Moscow RIOR INFRA-M

         Authors:
         Zhilyakova, L.Yu. — Doctor of Physics and Mathematics, leading researcher, Institute of Control Sciences of RAS (Moscow). Author of more than 130 papers on artificial intelligence, intellectual systems, and dynamic graph theory;
         Kuznetsov, O.P. — Doctor of Engineering, professor, head of laboratory, Institute of Control Sciences of RAS (Moscow). Author of more than 150 works, including two monographs, on artificial intelligence and intelligent system challenges, cognitive situation analysis, logic control, dynamic graph theory
         Reviewers:
         Chebotarev, P.Yu. — Doctor of Physics and Mathematics, head of laboratory, Institute of Control Sciences of RAS (Moscow);
         Dmitriev, M.G. — Doctor of Physics and Mathematics, professor of Faculty of Computer Science, Higher School of Economics (Moscow)




      Zhilyakova, L.Yu., Kuznetsov, O.P.
      Resource network theory: monograph. — Moscow: RIOR: INFRA-M, 2020. — 283 p. — (Science). — https://doi.org/10.12737/21451
          ISBN 978-5-369-01645-9 (RIOR)
          ISBN 978-5-16-012512-1 (INFRA-M, print)
          ISBN 978-5-16-102327-3 (INFRA-M, online)
          Resource network is a dynamic model of redistributing resource among the nodes of directed weighted graph. Nonnegative weights of edges denote their capacities. The nodes can contain unlimited amount of resource. The network operates in discrete time: nodes exchange with their resources along incident edges, keeping the conservation law of total network recourse. A classification of networks is developed. Dynamics and asymptotic behavior of states and flows in networks of every class are described and analyzed. An extensive review of non-classical network models is presented.
          The book is intended for specialists in graph theory and operations research, students, masters and post-graduate students of various mathematical, computer and information specialities.





             Color pictures can be found at http://znanium.com.
      Get the direct link scanning the QR-code on the cover of this book






                                                         © Zhilyakova, L.Yu., Kuznetsov, O.P.

        Оглавление


введение..................................................9
ГЛАВА 1. ОБЗОР ГРАФОВЫХ ДИНАМИЧЕСКИХ
МОДЕЛЕЙ..................................................12
1.1. Потоковые модели....................................14
     1.1.1. Классические потоковые модели................14
     1.1.2. Потоки в сетях с нестандартной достижимостью.20
     1.1.3. Задачи, сводящиеся к статическим потоковым моделям.25
     1.1.4. Динамические задачи. Потоки во времени (flows over time) .... 26
1.2. Случайные блуждания и рассеяние на графах...........27
     1.2.1. Области применения моделей случайного блуждания и рассеяния на графах.......................28
     1.2.2. Конечные цепи Маркова и их классификация.....29
     1.2.3. Графы перехода конечных цепей Маркова........32
     1.2.4. Дискретная модель достижения консенсуса......34
     1.2.5. Неоднородные цепи Маркова....................36
1.3. Целочисленные пороговые модели......................37
     1.3.1. Chip-firing game.............................37
     1.3.2. Вероятностный абак...........................40
     1.3.3. Некоторые результаты для chip-firing game....42
     1.3.4. Модель «абелева куча песка»..................45
     1.3.5. Графовая интерпретация «абелевой кучи» и chip-firing game .... 46
Комментарий к главе 1....................................46
ГЛАВА 2. РЕСУРСНАЯ СЕТЬ ПРЕДВАРИТЕЛЬНОЕ ЗНАКОМСТВО...............................48
2.1. Основные определения................................48
2.2. Полные однородные ресурсные сети....................50
2.3. Классификация ресурсных сетей по топологии..........63
2.4. Классификация ресурсных сетей по пропускным способностям.......................65
Комментарий к главе 2....................................69
ГЛАВА 3. РЕГУЛЯРНЫЕ СЕТИ ФУНКЦИОНИРОВАНИЕ ПРИ МАЛЫХ
РЕСУРСАХ. СТРУКТУРНЫЕ СВОЙСТВА НЕСИММЕТРИЧНЫХ СЕТЕЙ.....................................72
3.1. Предельное состояние регулярной сети при единичном ресурсе.............................73
3.2. Предельное состояние регулярной сети при малых ресурсах .... 75

5

3.3. Регулярные несимметричные сети и их свойства........77
3.4. Пороговое значение Т................................86
3.5. Коэффициент симметричности сети.....................87
3.6. Аттракторы и их классификация.......................89
     3.6.1. Определение потенциальных аттракторов........89
     3.6.2. Классификация аттракторов....................96
     3.6.3. Признаки аттрактивности вершины..............96
Комментарий к главе 3...................................101

ГЛАВА 4. ПОТОКИ И ПРЕДЕЛЬНЫЕ СОСТОЯНИЯ
В РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЯХ ... 103

4.1. Поток ресурса.......................................103
     4.1.1. Поток при малых ресурсах.....................104
     4.1.2. Поток при больших ресурсах...................104
4.2. Семейство сетей, соответствующих одной стохастической
     матрице.............................................115
     4.2.1. Матрицы с большей выходной пропускной способностью вершин-источников.....................117
     4.2.2. Матрицы с большей выходной пропускной способностью вершин-приемников.....................118
     4.2.3. Смена сетью вершины-приемника................120
4.3. Вектор Q 1* и пороговое значение Т..................122
4.4. Свойство аттрактивности и предельное состояние сети.123
4.5. Построение матрицы R с произвольным количеством аттракторов по заданной матрице R '......................127
4.6. Оценка числа сетей с неединственным аттрактором.....130
4.7. Полная сеть с одним приемником и одним источником...131
Комментарий к главе 4....................................133

ГЛАВА 5. РЕГУЛЯРНЫЕ ЭЙЛЕРОВЫ СЕТИ.............................135
5.1. Существование предельного состояния и пороговое значение Т..............................136
5.2. Свойства эйлеровых сетей...................................137
5.3. Предельное состояние сети при единичном и малом ресурсе.....................................139
5.4. Функционирование сети при больших ресурсах.................142
5.5. Предельные состояния и потоки при больших ресурсах.......143
     5.5.1. Предельное состояние сети при неизменной зоне Z (t).143
     5.5.2. Предельное состояние эйлеровой сети. Общий случай.147
     5.5.3. Предельные потоки при больших ресурсах и задача mm нахождения вектора C - случай отсутствия ресурса
         в зоне Z (0)...........................................149

6

    5.5.4. Задача нахождения вектора Сm - случай стационарной зоны Z (t)...................................155
    5.5.5. Задача нахождения вектора Сm - общий случай..159
Комментарий к главе 5....................................169
ГЛАВА 6. ЭРГОДИЧЕСКИЕ ЦИКЛИЧЕСКИЕ СЕТИ.........................................171
6.1. Элементарные циклы и их свойства....................174
6.2. Функционирование произвольных циклических сетей при малых ресурсах...............................190
    6.2.1. Функционирование циклической сети при единичном ресурсе.......................190
    6.2.2. Предельные векторы и циклы d-циклической сети.195
    6.2.3. Достижение глобального равновесия при малых ресурсах .. 199
6.3. Пороговое значение Т и функционирование циклических сетей при больших ресурсах............204
    6.3.1. Пороговое значение Т.........................204
    6.3.2. Критерий аттрактивности и потенциальные аттракторы 207 6.3.3. Предельное состояние и предельный поток при больших
         ресурсах........................................208
Комментарий к главе 6....................................211
ГЛАВА 7. ПОГЛОЩАЮЩИЕ СЕТИ................................214
7.1. Свойства поглощающих ресурсных сетей................214
7.2. Поглощающие сети с единственным предельным состоянием............................218
7.3. Поглощающие сети общего вида. Пороговое значение Т.222
7.4. Предельные состояния в поглощающих сетях............225
    7.4.1. Матрица R'” и ее свойства....................225
    7.4.2. Вектор предельного состояния и его свойства...229
    7.4.3. Нелинейное изменение промежуточных состояний.232
Комментарий к главе 7...................................236
ГЛАВА 8. РАСПРЕДЕЛЕНИЕ РЕСУРСА
МЕЖДУ АТТРАКТОРАМИ В РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЯХ ПРИ БОЛЬШИХ
РЕСУРСАХ.................................................237
8.1. Поглощающая сеть, соответствующая несимметричной, и поправка на регулярность 8W.....................239
8.2. Зависимость 8W от выходных пропускных способностей аттракторов.......................................251

7

8.3. Неоднородная цепь Маркова, динамика стохастических матриц и вычисление SW.................254
8.4. Предельное состояние сети приfsᵤₘ(t) > T...256
8.5. Начальные состояния, не создающие поправку.258
8.6. Оценка поправки SW.........................260
Комментарий к главе 8...........................264

СРАВНЕНИЕ РЕСУРСНЫХ СЕТЕЙ С ДРУГИМИ
ДИНАМИЧЕСКИМИ СЕТЕВЫМИ МОДЕЛЯМИ ... 265

КРАТКИЕ ИТОГИ...................................268
ЛИТЕРАТУРА......................................272
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ............................281
СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ.....................282


8

                           Может, ничто никогда не случается только раз, и, может, все случается не один раз, а расходится, как круги по воде, когда камешек падает в пруд: круги движутся, расширяются; пруд связан тонкой водяной пуповиной со следующим прудом, который он, этот первый пруд, питает и все время питал, пусть даже у того первого пруда иная температура воды, иной молекулярный состав, иная способность видеть, чувствовать, вспоминать, отражать в ином ракурсе бесконечное неизменное небо - все равно водное эхо от падения камешка, которого второй пруд даже и не видел, бежит по его поверхности изначальными кругами, в том же нерушимом ритме.
У. Фолкнер, «Авессалом, Авессалом!»

        ВВЕДЕНИЕ

     Модели распространения ресурсов в сетях с ограниченными пропускными способностями существуют более 60 лет, начиная с потоковой модели Форда-Фалкерсона [59]. Эту модель можно назвать статической, поскольку в ней не рассматривается поведение сети во времени; важно лишь, какой максимальный поток возможен в данной сети, - другими словами, какой максимальный ресурс можно передавать за единицу времени без задержек в промежуточных узлах. В дальнейшем появились различные динамические сетевые модели распространения: модификации потоковых моделей, процессы рассеяния на графах, целочисленные пороговые модели, такие как игра выстреливания фишек (chip-firing game) и др.
     В настоящей книге излагается новая модель распространения однородных ресурсов - ресурсная сеть - и исследуются ее динамические свойства. Ресурсная сеть - это ориентированный граф, ребра которого имеют положительные пропускные способности. В вершинах размещается ресурс; каждая вершина может хранить неограниченное количество ресурса. Сеть функционирует в дискретном времени. Суммарное количество ресурса W на протяжении всего времени функционирования сети не изменяется. Распределение ресурса по вершинам в момент t дискретного времени определяет со

9

стояние сети Q(t). В момент t каждая вершина отдает ресурс другим вершинам по выходящим ребрам по одному из двух правил: если ресурса в вершине Vi не меньше, чем суммарная пропускная способность ее выходящих ребер, вершина отдает «все, что может», т.е. пропускные способности ее выходящих ребер используются полностью; в противном случае вершина отдает весь ресурс, распределяя его пропорционально пропускным способностям. На следующем такте переданный ресурс входит в смежные вершины по входящим ребрам, после чего процесс отдачи повторяется.
     Важной особенностью ресурсных сетей является наличие порогового значения Т суммарного ресурса: поведение сети при «малом» (меньшем Т) и «большом» ресурсе оказывается существенно различным.
     План книги таков. В главе 1 дается краткий обзор динамических графовых моделей и приводятся основные сведения по теории матриц и цепей Маркова, активно используемые в книге. В главе 2 вводятся основные понятия теории, которые иллюстрируются на примере наиболее простого класса ресурсных сетей: полных однородных сетей (сетей, граф которых - полный, а все пропускные способности одинаковы). Предлагается матричная классификация ресурсных сетей по двум основаниям: по топологии, т.е. структуре графа сети, и по пропускным способностям. В последующих главах исследуется поведение различных классов ресурсных сетей. Общая схема исследования для всех классов одинакова: доказывается существование (или отсутствие) предельного состояния (при t ^ ^) и предельного потока, решаются задачи их вычисления при различных начальных состояниях и значениях суммарного ресурса, демонстрируется различие в поведении при малом и большом ресурсе. Однако методы решения этих задач и конкретные результаты для разных классов сетей существенно различны. Заключение содержит краткое резюме основных результатов теории и сравнение ресурсных сетей с другими динамическими сетевыми моделями.
     Наши теоремы вначале были гипотезами, которые, в свою очередь, возникли из множества вычислительных экспериментов. Индуктивному характеру исследования соответствует индуктивный стиль изложения: анализ примеров, как правило, предшествует доказательствам теорем.
     Для облегчения предварительного знакомства мы снабдили каждую главу анонсом ее содержания в начале и кратким комментарием в конце главы. Сводка основных результатов приведена в конце книги.

10