Ресурсные сети с ограничениями на ёмкость вершин

Л.Ю. Жилякова

РЕСУРСНЫЕ СЕТИ 
РЕСУРСНЫЕ СЕТИ 

С ОГРАНИЧЕНИЯМИ 
С ОГРАНИЧЕНИЯМИ 

НА ЁМКОСТЬ ВЕРШИН
НА ЁМКОСТЬ ВЕРШИН

МОНОГРАФИЯ
МОНОГРАФИЯ

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

УДК 519.711.74
ББК 22.18
         Ж72

Жилякова Л.Ю.
Ресурсные сети с ограничениями на ёмкость вершин [Электронный 
ресурс] : монография / Л.Ю. Жилякова. — М. : РИОР  : ИНФРА-М, 
2018. — 160 с. — DOI: https://doi.org/10.12737/1745-6

ISBN 978-5-369-01745-6 (РИОР)
ISBN 978-5-16-106308-8 (ИНФРА-М, online)

Работа является продолжением исследований, результаты которых опубликованы в книге Л.Ю. Жиляковой и О.П. Кузнецова «Теория ресурсных сетей». — М.: 
РИОР: ИНФРА-М, 2017. Ресурсная сеть представляет собой графовую динамическую модель, в которой вершины в дискретном времени обмениваются однородным ресурсом по каналам с ограниченными пропускными способностями. На 
каждом такте вершины отдают ресурс по одному из двух правил с пороговым 
переключением – в зависимости от его количества. В исходной модели все вершины обладают неограниченной ёмкостью, т.е. могут принимать и хранить произвольное количество ресурса. В модели, предложенной в настоящей работе, 
вершины, аккумулирующие ресурс (аттракторы), имеют ограничения на ёмкость. 
Тем самым реализуется возможность накопления ресурса в множестве вершин, 
названных вторичными аттракторами. Исследованы неоднородные цепи Маркова, порождаемые процессом перераспределения ресурса.
Книга предназначена специалистам по теории графов и исследованию операций, студентам, магистрам и аспирантам, обучающимся по различным направлениям дискретной математики и компьютерных наук.

УДК 519.711.74
ББК 22.18

ISBN 978-5-369-01745-6 (РИОР)
ISBN 978-5-16-106308-8 (ИНФРА-М, online)
©  Жилякова Л.Ю.

Ж72

А в т о р ы :
Жилякова Л.Ю. — д-р физ.-мат. наук, ведущий научный сотрудник Института 
проблем управления им. В.А.Трапезникова РАН (Москва). Является автором более 
100 работ по проблемам искусственного интеллекта и интеллектуальных систем, 
динамической теории графов, гетерогенных нейронных сетей.

Р е ц е н з е н т ы :
Ерусалимский Я.М. – д-р техн. наук, канд. физ.-мат. наук, профессор, профессор кафедры алгебры и дискретной математики Южного федерального университета (Ростов-на-Дону);
Агаев Р.П. – д-р физ.-мат. наук, ведущий научный сотрудник Института проблем управления им. В.А.Трапезникова РАН (Москва).

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

Работа выполнена при финансовой поддержке РФФИ 
(проекты № 15-07-02488, 17-07-00541, 17-20-01180).

L.Yu. Zhilyakova

RESOURCE NETWORKS 
RESOURCE NETWORKS 

WITH LIMITATIONS 
WITH LIMITATIONS 

ON VERTEX CAPACITIES
ON VERTEX CAPACITIES

MONOGRAPH
MONOGRAPH

Moscow
RIOR
INFRA-M

Zhilyakova, L.Yu.
Resource networks with limitations on vertex capacities : monograph. — 
Мoscow : RIOR : INFRA-M, 2018. — 160 p. — DOI: https://doi.
org/10.12737/1745-6

ISBN 978-5-369-01745-6 (RIOR)
ISBN 978-5-16-106308-8 (INFRA-M, online)

The book represents a flow model based on the model “resource network” 
introduced and studied in the monograph by L.Yu. Zhilyakova and O.P. Kuznetsov 
“Theory of Resource Networks” – M. : RIOR: INFRA-M, 2017. Resource network 
is a dynamic model where vertices of directed weighted graph exchange homogeneous 
resource along incident edges in discrete time. Nonnegative weights of edges denote 
their throughputs. In the initial model, all vertices have an unlimited capacity, i.e. can 
receive and store arbitrary amount of resource. In the model proposed in the present 
work, vertices accumulating resource (attractor-vertices) have limitations on their 
capacities. Thus, the possibility of accumulating resource in another set of vertices is 
realized. These vertices were called “secondary attractors”. We showed that the process 
of resource redistribution in such networks is equivalent to an inhomogeneous Markov 
chain and investigated the chains generated by network operation with specified 
limitations.
The book is intended for specialists in graph theory and operations research, 
students, masters and post-graduate students of various mathematical, computer and 
information courses.

A u t h o r s :
Zhilyakova, L.Yu. — Doctor of Physics and Mathematics, leading researcher, 
Institute of Control Sciences of RAS (Moscow). Author of more than 100 papers 
on artificial intelligence, intellectual systems, and dynamic graph theory;
R e v i e w e r s :
Erusalimskiy, I.M. — Doctor of Engineering, candidate of Physics and 
Mathematics, professor, professor of department of algebra and discrete 
mathematics, Southern Federal University, (Rostov-on-Don); 

©  Zhilyakova, L.Yu.

Agaev R.P. — Doctor of Physics and Mathematics, leading researcher, 
Institute of Control Sciences of RAS (Moscow).

Оглавление

ВВЕДЕНИЕ..............................................................................................7

Благодарности....................................................................................12

ГЛАВА 1. ВВЕДЕНИЕ В ТЕОРИЮ РЕСУРСНЫХ СЕТЕЙ .............13

1.1. Основные определения и обозначения.....................................13

Правила функционирования сети.................................................15
Классификация вершин сети ........................................................16
Поток ресурса.................................................................................20
Входное и выходное соседство вершин ......................................21

1.2. Свойства ресурсных сетей .........................................................21

Вектор предельного состояния при малом ресурсе....................21
Пороговое значение T....................................................................22
Критерий аттрактивности .............................................................23
Предельный поток и предельные состояния при W = Т и при 
большом ресурсе (W > Т)..............................................................23
Поиск аттракторов.........................................................................27

Комментарий к главе 1......................................................................31

ГЛАВА 2. ОПИСАНИЕ СЕТИ С ОГРАНИЧЕНИЯМИ НА 
ЕМКОСТЬ АТТРАКТОРОВ.................................................................32

2.1. Постановка задачи......................................................................32
2.2. Алгоритм функционирования сети с ограничениями .............35

Функционирование сети после насыщения первичных 
аттракторов.....................................................................................36
Маркировка первичных аттракторов...........................................37

2.3.  Исследование потока при ограничениях на аттракторы........43
2.4.  Второе пороговое значение TII. Теорема существования.......47
Комментарий к главе 2......................................................................59

ГЛАВА 3. ИССЛЕДОВАНИЕ ПЕРЕХОДНЫХ ПРОЦЕССОВ В 
СЕТИ С ОГРАНИЧЕНИЯМИ ..............................................................61

3.1. Переходные процессы в сети  с ограничениями......................61
3.2. Исследование матриц перехода.................................................64
3.3. Допустимые преобразования сети и переход от 
псевдостохастических матриц к стохастическим...........................69
3.4. Изменение характеристик сети при допустимых 
преобразованиях ................................................................................77
3.5. Иллюстрации применения допустимых преобразований.......86

План исследования ........................................................................86
Увеличение элементов R0..............................................................89

Уменьшение элементов R0 ............................................................ 92 
Изменение элементов R0 с сохранением их суммы .................... 94 
3.6. Матричные эквиваленты инвариантов ресурсной сети .......... 98 
Комментарий к главе 3 .................................................................... 104 
ГЛАВА 4. ПРЕДЕЛЬНЫЕ ХАРАКТЕРИСТИКИ СЕТИ С 
ОГРАНИЧЕНИЯМИ ........................................................................... 106 
4.1. Неоднородные цепи Маркова .................................................. 107 
4.2. Второе пороговое значение и его свойства ............................ 111 
4.3. Построение расширенной сети, соответствующей сети с 
ограничениями ................................................................................. 116 
4.4. Предельные характеристики сети с ограничениями ............. 119 
Комментарий к главе 4 .................................................................... 126 
Глава 5. ПРИМЕНЕНИЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ  ДЛЯ 
ПОИСКА ВТОРИЧНЫХ АТТРАКТОРОВ И ПРЕДЕЛЬНЫХ 
СОСТОЯНИЙ ...................................................................................... 127 
5.1. План исследования сетей с ограничениями ........................... 128 
5.2. Поиск характеристик сети с одним первичным аттрактором 
при его ограничении ........................................................................ 129 
5.3. Поиск характеристик сети с несколькими первичными 
аттракторами .................................................................................... 138 
Комментарий к главе 5 .................................................................... 150 
ЗАКЛЮЧЕНИЕ .................................................................................... 151 
ЛИТЕРАТУРА ..................................................................................... 153 
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ........................................................... 155 
СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ ........................................ 157 

Очень просто, вместо ветра они ловят 
этими сетями что-то другое.

Милорад Павич, «Хазарский словарь»

ВВЕДЕНИЕ

Предлагаемая вниманию читателя работа представляет собой

продолжение большого исследования, опубликованного в монографии «Теория ресурсных сетей» [8]. Модель «ресурсная сеть»
была создана О.П. Кузнецовым в 2009 г. [12]. Это графовая динамическая потоковая модель, в которой вершины обмениваются однородным ресурсом. Сеть задается ориентированным взвешенным 
графом с постоянной топологией. Ресурс находится в вершинах, 
имеющих неограниченную емкость. Веса ребер обозначают их 
пропускные способности – максимальное количество ресурса, которое может пройти по ребру за один такт дискретного времени.

На каждом такте вершины распределяют ресурс в исходящие 

ребра по двум разным правилам с пороговым переключением. Переключение происходит в зависимости от количества ресурса, содержащегося в вершине. Если это количество превосходит сумму 
весов всех исходящих из нее ребер (взвешенный аналог полустепени исхода), в каждую смежную вершину передастся ресурс, равный пропускной способности соответствующего ребра. В противном случае вершина отдаст весь свой ресурс, разделив его между 
всеми ребрами пропорционально их пропускным способностям. 
Модель параллельна: на каждом такте дискретного времени t вершины, имеющие ресурс, отдают его одновременно. Ресурс перераспределяется с выполнением закона охранения.

В первой статье [12] был описан частный случай – сеть была 

задана полным графом с петлями, все ребра имели одинаковые 
пропускные способности (полная однородная сеть). На этом простом примере наглядно продемонстрированы основные свойства, 
присущие произвольной ресурсной сети: устойчивость при малом 

ресурсе, зависимость от начальных условий при большом ресурсе1, 
наличие интегральной характеристики сети – порогового значения 
ресурса, разделяющего малые и большие значения.  За этой публикацией последовал ряд других, в которых были получены результаты, позволяющие практически полностью описать поведение ресурсных сетей (они обобщены в книге [8]).

Под «описать поведение» подразумевается, что если зафикси
ровать:


топологию сети,


пропускные способности ребер при данной топологии,


значение суммарного ресурса,


начальное распределение ресурса по вершинам2,

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

Из первых двух параметров (топологии и пропускных способ
ностей), для произвольной сети можно определить ее глобальную 
характеристику – пороговое значение ресурса Т. Если суммарный
ресурс в сети не превосходит Т, ее функционирование, начиная с 
некоторого конечного такта, определяется однородной цепью 

1 Впоследствии оказалось, что существуют сети с единственным предельным состоянием при любом суммарном ресурсе и его начальном 
распределении. Однако они являются частным случаем сетей более общего класса, для которых зависимость предельного вектора от начального состояния при большом ресурсе всѐ же имеет место.
2 В сетях из примечания 1 (они будут описаны ниже) начальное распределение не влияет на предельное состояние и предельный поток. В этом 
случае на поведение сети влияют только три первых параметра.

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

При малых ресурсах функционирование сети полностью опре
деляется стохастической матрицей, полученной из матрицы пропускных способностей нормированием строк. Предельное состояние для регулярных сетей (которые будут исследоваться и в этой
работе) всегда существует и единственно; вектор предельного состояния пропорционален вектору предельных вероятностей однородной цепи Маркова. На функционирование сетей с малым ресурсом переносятся все результаты, полученные для случайных 
блужданий и процессов рассеяния на графах [6, 11, 20]. Аппарат
однородных цепей Маркова применяется при моделировании процессов в очень разных предметных областях. К ним относятся
процессы сближения мнений и достижения консенсуса в многоагентных системах [1, 2], информационные процессы и распространение активности в социальных сетях [7], распространение
эпидемий [29], моделирование регуляторных сетей экспрессии генов [4, 13] и многие другие. Разнообразные прикладные приложения, основанные на модели рассеяния на графах, описаны в книге 
[20].

При больших ресурсах ресурсная сеть наследует часть свойств 

целочисленных пороговых моделей, таких как, в частности, игра 
выстреливания фишек, в которой вершины графа обмениваются 
фишками с выполнением закона сохранения. Вершина может выстрелить, если ее суммарное количество фишек больше количества 
выходных ребер. Тогда она посылает по одной фишке вдоль каждого ребра. Классическая игра представляет собой последовательные выстреливания вершин [18, 19]; очередность вершин выбирается случайным образом. Были исследованы и параллельные игры 
выстреливаний [30]. Этот математический аппарат нашел приме

нение при описании процессов, получивших название «самоорганизованная критичность», в частности, в моделях «куча песка», 
«куча риса», описывающих образование на склонах «куч» лавин 
различной величины [16, 17, 24, 25]. 

Ресурсная сеть, объединяя в себе свойства моделей рассеяния и 

пороговых моделей, демонстрирует проявление новых свойств. За 
счет способности вершин отдавать ресурс независимо от его количества  обеспечивается устойчивость и сходимость, которых нет в 
целочисленных пороговых моделях. С другой стороны, некоторые
вершины способны притягивать и накапливать излишки ресурса 
(чего нельзя достичь в однородных марковских процессах). При 
этом все остальные вершины в предельном состоянии не будут 
увеличивать свой ресурс: соответствующие им компоненты предельного вектора при большом ресурсе всегда пропорциональны 
компонентам вектора предельных вероятностей индуцированной 
однородной цепи Маркова с одним и тем же коэффициентом Т и
не превосходят суммарных выходных пропускных способностей 
этих вершин [8]. Вершины, способные при больших ресурсах 
накапливать излишки, были названы аттракторами.

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

пропускная способность входящих в нее ребер 
in
ir
отличается от

суммарной пропускной способности исходящих из нее ребер 
out
ir
. 

В любой несимметричной сети существует хотя бы одна вершина, 
являющаяся активным аттрактором (т.е. способная не просто 
сохранять, но притягивать к себе излишки ресурса). Активными 
аттракторами могут быть только вершины-приемники (те верши