Санкт-Петербургский государственный университет
Прикладная математика и информатика
Исследование операций и принятие решений в задачах
оптимизации, управления и экономики
Ульмашев Назар Салаватович
Использование случайных графов в финансовой сфере
Бакалаврская работа
Научный руководитель:
к. ф. -м. н., ст. пр. Абрамовская Т. В.
Рецензент:
к. ф. -м. н., доцент Бухвалова В. В.
Санкт-Петербург
2016
SAINT PETERSBURG STATE UNIVERSITY
Applied Mathematics and Computer Science
Operation Research and Decision Making in Optimisation,
Control and Economics Problems
Ulmashev Nazar
Usage of random graphs in financial analysis
Bachelor’s Thesis
Scientific supervisor:
Senior Lecturer Tatyana Abramovskaia
Reviewer:
Associate Professor Vera Buhvalova
Saint Petersburg
2016
Содержание
1. Введение
4
2. Модель случайного графа с
фиксированным распределением степеней
2.1. Производящие функции . . . . . . . . . . .
2.2. Величина компонент связности . . . . . . .
2.3. Ориентированные графы . . . . . . . . . .
вершин
7
. . . . . . . 7
. . . . . . . 11
. . . . . . . 13
3. Модель кросс-холдинга Гая-Кападия
18
3.1. Общая структура . . . . . . . . . . . . . . . . . . . . . . 18
3.2. Производящие функции . . . . . . . . . . . . . . . . . . 21
3.3. Фазовый переход . . . . . . . . . . . . . . . . . . . . . . 23
4. Алгоритм моделирования случайного графа и запуск
дефолтов
4.1. Общая схема . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Моделирование дискретной случайной величины . . . .
4.3. Преобразование набора вершин в граф . . . . . . . . .
4.4. Моделирование кросс-холдинга . . . . . . . . . . . . . .
4.5. Моделирование дефолтов на полученном графе . . . .
4.6. Программа . . . . . . . . . . . . . . . . . . . . . . . . .
26
26
27
29
30
31
31
5. Результаты
33
3
1. Введение
Существуют системы, в которых элементы тесно и сложно связаны
между собой. Примером такой системы может являться замкнутая
группа людей, в которой один участник заразился некоторой инфекцией. Тогда распространение инфекции в группе зависит от частоты
контактов заболевшего с остальными членами группы, силы иммунитета и прочих факторов. Аналогичным примером может служить
сеть связанных компьютеров, в которой распространяется вирус, или
социальные сети и распространение через них различного вирусного
контента. Подобные эффекты можно увидеть и в финансовой сфере.
Объектом исследования данной работы являются кросс-холдинги.
Кросс-холдинг — это система, состоящая из различных организаций
(например, банков), в которой участники обладают друг перед другом рядом обязательств (взаимные кредиты в случае банков). Аналогом заболевания в таком случае будет служить дефолт банка, т.е.
состояние неплатежеспособности и невозможность отдавать долги.
Таким образом, дефолты могут распространяться от банка к банку,
а неплатежеспособность единственного банка может привести к краху всей системы. Подробно системы кросс-холдингов были описаны
в [1].
В качестве инструмента, который используется для исследования
кросс-холдингов, были выбраны случайные графы с фиксированным
распределением степеней вершин. Дело в том, что графы сами по
себе удобны для представления и изучения различных систем, представимых в виде сетей, а теория случайных графов позволяет изучать некоторые типичные свойства подобных систем. Конкретная
модель случайного графа — с фиксированным распределением сте4
пеней вершин — также была выбрана неслучайно. Несмотря на то,
что, пожалуй, самой известной моделью является модель случайного
графа Эрдёш-Реньи (описана в [2]), она мало подходит для исследования кросс-холлдингов из-за Пуассоновского распределения степеней вершин, которое нехарактерно для изучаемых моделей. Поэтому,
как утверждается в [4], для подобных систем следует использовать
схему, которая позволяет строить граф, основываясь на желаемом
распределении степеней его вершин. Для этих целей была выбрана
модель, предложенная Ньюменом, Строгатцем и Ватсом (мы будем
ссылаться на неё по имени первого автора).
Наложение финансовой составляющей на модель случайного графа Ньюмена приводит нас к модели кросс-холдингов, которая описана в статье Гая-Кападии [3]. В ней аппарат производящих функций
объединяется с понятиям уязвимости банка, и проводятся исследования соответствующих свойств полученных систем.
С практической точки зрения интересен алгоритм программного
моделирования случайного графа с заданным законом распределения. Для его реализации требуется решить несколько проблем: моделирование случайных величин, процесс соединения вершин графа,
отсеивание плохих случаев. Общая схема была взята из статьи [4].
Задача моделирования дискретной случайной величины была решена классическим методом Уолкера (описан в [5]).
Работа состоит из 5 параграфов. Во втором описываются различные модели случайных графов и аппарат производящих функций,
который позволяет их исследовать. В третьем параграфе говорится
о модели кросс-холдинга и о применении в ней теории случайных
графов. Некоторые теоретические результаты, полученные в этих
5
двух параграфах, в дальнейшем сравниваются с данными, полученными в результате моделирования. В четвертом параграфе идёт речь
о непосредственно моделировании случайных графов и экономических процессов на них. В заключительном, пятом, параграфе анализируются результаты проведенного моделирования.
6
2. Модель случайного графа с
фиксированным распределением степеней вершин
Основная проблема модели случайного графа Эрдёш-Реньи заключается в том, что она обладает Пуассоновским распределением степеней вершин. Однако же в моделях, возникающих в реальной жизни (таких как модели кросс-холдингов или модели распространения
эпидемий), это правило обычно не выполняется. Как следствие, необходимо выбрать такую модель случайного графа, в которой распределение степеней вершин было бы необходимым.
2.1. Производящие функции
Подход, который используется для построения модели случайного
графа, будет основан на производящих функциях.
Напомним, что производящие функции — это один из способов задания вероятностного распределения дискретной случайной величины.
Удобство данного способа заключается в относительной простоте вычисления моментов случайной величины.
В случае неориентированного графа, производящая функция может
быть задана следующим образом:
G0 (x) =
∞
pk xk ,
(1)
k=0
где pk — вероятность того, что случайно выбранная в графе вершина будет иметь степень k. Причем распределение нормализованно,
7
поэтому
G0 (1) = 1.
(2)
Зная производящую функцию G0 (x), можно посчитать вероятность
pk :
1 dk G0
.
pk =
k! dxk x=0
(3)
Как было сказано выше, производящие функции удобны при вычислении моментов. Например, нетрудно вычислить математическое
ожидание степени вершины в графе:
z=
kpk = G′0 (1).
(4)
k
Пример.
Возьмем граф с 4 вершинами и следующее распределение степеней
его вершин:
X
1
2
3
P(X) 0.2 0.6 0.2
Кроме того, наложим ограничение на существование петель и кратных рёбер, что приведет к условию P (X = i) = 0, i > 3.
Производящая функция тогда будет выглядеть следующим образом:
G0 (x) = 0.2x + 0.6x2 + 0.2x3 .
8
(5)
Математическое ожидание степени вершины:
z = G′0 (1) = (0.2 + 1.2x + 0.6x2 )x=1 = 1.8.
(6)
Чтобы получить конкретный граф, удовлетворяющий заданному распределению, нужно сначала посчитать значения случайных величин
ξi , i ∈ 1 . . . 4, соответствующих степени каждой из четырёх вершин.
Пусть, например, выпали следующие значения:
i
1 2 3 4
ξi
2 2 1 3
Тогда, соединив некоторым образом вершины в соответствии с полученными степенями (конкретные способы будут указаны позже),
можно получить, например, следующий граф:
1
2
3
4
Средняя степень вершины в данном случае равна 2, что почти совпадает с полученным мат. ожиданием z = 1.8.
Если G0 задает степень случайно выбранной в графе вершины, то
распределение ее непосредственных соседей не совпадает с распределением степеней вершин в графе в целом. Для этого рассмотрим
распределение степеней вершин, которые можно достигнуть пройдя
9
по случайно выбранному в графе ребру. Такое ребро входит в некоторую вершину с вероятностью, пропорциональной степени этой вершины, а значит, распределение её степени будет пропорционально
величине kpk . Нормализованная производящая функция распределения степеней вершин тогда примет следующий вид:
kpk xk
G′0 (x)
k
=x ′
.
Gα (x) =
kpk
G0 (1)
(7)
k
Если случайным образом выбрать в графе вершину и пройти до k её
ближайших соседей, то вероятности степеней всех таких вершин, без
учета ребра, ведущего обратно в исходную вершину, будут распределены в соответствии с функцией Gα (x), деленной на x — последнее для того, чтобы исключить из расчета ребро, по которому мы
пришли в такую вершину. Таким образом, пониженная не единицу
степень вершины, в которую можно попасть двигаясь по случайно
выбранному в графе ребру, распределена в соответствии с функцией:
G′0 (x) 1 ′
= G0 (x).
G1 (x) = ′
G0 (1)
z
(8)
Теперь можно получить производящую функцию для распределения
количества непосредственных соседей вершин, смежных с исходной
(назовём их смежными вершинами второго уровня).
pk [G1 (x)]k = G0 (G1 (x)).
(9)
k
Откуда можно получить и математическое ожидание смежных вер-
10
шин второго уровня:
d
= G′0 (1)G′1 (1) = G′′0 (1).
G0 (G1 (x))
z2 =
dx
x=1
(10)
Возвращаясь к примеру:
z2 = (1.2 + 1.2x)|x=1 = 2.4.
(11)
Фактическое количество вершин второго уровня в полученном графе
(обозначим как deg2 ):
i
1 2 3 4
deg(i)2
3 3 2 2
Таким образом, среднее значение количества вершин второго уровня
равняется 2.5.
Замечание. Несмотря на то, что среднее количество смежных вершин выражается через G′0 (1), а среднее количество смежных вершин
на втором уровне через G′′0 (1), предположение о том, что среднее
количество смежных вершин уровня m может быть вычислено как
(m)
G0 (1), не является верным.
2.2. Величина компонент связности
Предметом рассмотрения в данном разделе является распределение
размеров компонент связности в графе. (Данный параграф представляет исключительно теоретический интерес, поскольку в системах
кросс-холдингов предполагается наличие связных графов).
Для начала введем функцию H1 (x) — производящую функцию для
11
распределения размеров компонент связности (при этом не рассматривается случай наличия в графе гигантской компоненты, т. е. такой наибольшей компоненты, размер которой линейно зависит от
размера графа. Граф не имеет гигантской компоненты, если с ростом количества вершин размер компонент связности остается постоянным), которые можно достичь, если двигаться по случайно выбранному ребру в одном из направлений. Учитывая, что вероятность
возникновения цикла в отдельной компоненте будет пропорциональна N −1 , при больших значениях N этой вероятностью можно пренебречь. Таким образом, компоненты связности, порождаемые производящей функцией H1 (x) может быть представлено в виде рисунка:
Каждая компонента связности имеет древовидную структуру и может состоять либо из единственной вершины v ∈ V , в которую можно попасть двигаясь по иcходному ребру e ∈ E, либо из компонент, в
которые можно попасть двигаясь по смежным с v рёбрам (но не по
e в обратную сторону). Причем эти компоненты будут иметь аналогичное распределение размеров. Теперь обозначим за qk вероятность
того, что вершина v имеет deg(v) = k + 1 (куда входит исходное случайно выбранное ребро и еще k исходящих из этой вершины рёбер).
Тогда верно следующее соотношение:
H1 (x) = xq0 + xq1 H1 (x) + xq2 [H1 (x)]2 + . . .
12
(12)
Причем qk — это коэффициент при xk для функции G1 (x). Таким
образом, с учётом вида G1 (x) в (8):
H1 (x) = x
qk H1k (x) = xG1 (H1 (x)).
(13)
k
Если случайным образом выбрать вершину в графе, то на конце каждого исходящего из неё ребра будет подобная компонента связности
и, таким образом, порождающая функция для размера всей компоненты имеет следующий вид:
H0 (x) = xG0 (H1 (x)).
(14)
В итоге, зная функции G0 (x) и G1 (x), можно решить уравнения (13)
и (14) и найти производящую функцию H0 (x).
2.3. Ориентированные графы
Объектов нашего дальнейшего изучения будут являться ориентированные графы с фиксированным распределением степеней вершин.
Примером такого графа как раз является основной предмет изучения настоящей работы — кросс-холдинг банков.
Ориентированные графы имеют ряд особенностей, которые отличают их от неориентированных графов, и из-за которых требуется
несколько модифицировать аппарат, рассмотренный в предыдущих
пунктах. Во-первых, в ориентированном графе нет понятия степени
вершины в классическом смысле. Вместо этого появляются понятия
полустепеней захода и выхода вершины, определяемые соответственно как число входящих и исходящих вершин. Во-вторых, исчезает по13
нятие компоненты связности, поскольку некоторая вершина может
быть достигнута из исходной, а обратное не обязано быть правдой.
Следует рассматривать отдельно множество всех вершин, достижимых из данной (компонента выхода), и множество всех вершин, из
которых данная вершина достижима (компонента захода). Таким
образом, основная идея модификации введенного аппарата — рассматривать отдельно входящие и исходящие ребра.
Пусть pjk — вероятность того, что случайно выбранная в графе вершина имеет полустепень захода j и полустепень выхода k. Причем
стоит заметить, что эти степени, вообще говоря, не являются независимыми величинами, т.е. pjk ̸= pj pk . Иллюстраций этого свойства
может служить Интернет, для которого узел, имеющий большое количество входящих ребёр, как правило имеет и большое количество
исходящих.
По аналогии с производящими функциями для неориентированных
графов, определим производящую функцию для ориентированного
графа:
G(x, y) =
pjk xj y k .
(15)
jk
Поскольку каждое ребро в ориентированном графе выходит из одной вершины и входит в другую, то входы и выходы из вершины в
среднем сбалансированы.
pjk (j − k) = 0.
jk
14
(16)
А значит:
∂G
∂G
=
= z.
∂x x,y=1
∂y x,y=1
(17)
Где z, как и раньше, — это математическое ожидание полустепени
вершины в графе.
Пример.
Возьмем следующее распределение полустепеней (элементом j-й строки и k-го столбца является pjk ):
1
2
1 0.5 0.2
2 0.2 0.1
Производящая функция тогда примет следующий вид:
G(x, y) = 0.5xy + 0.2x2 y + 0.2xy 2 + 0.1x2 y 2 .
(18)
Аналогично предыдущему примеру возьмем какой-нибудь граф из
данного распределения:
1
2
3
4
15
И вычислим для него математическое ожидание полустепени:
∂G
= 0.5 + 0.4 + 0.2 + 0.2 = 1.3,
z=
∂x x,y=1
(19)
что очень близко к реальному среднему значению полустепени в данном графе, равному 1.25.
Аналогично предыдущим пунктам, можно определить производящие
функции G0 и G1 . Только теперь они будут отвечать исключительно
за исходящие ребра и связанные с ними характеристики. Для входящих ребер заведем аналогичные производящие функции F0 и F1 .
Определим их при помощи уже известной функции G(x, y):
Производящая функция распределения полустепени захода случайно выбранной вершины:
F0 (x) = G(x, 1).
(20)
Производящая функция для полустепени захода вершины, в которую можно попасть, двигаясь по случайно выбранному в графе ребру:
1 ∂G
F1 (x) =
.
(21)
z ∂x y=1
Производящая функция распределения полустепени выхода случайно выбранной вершины:
G0 (y) = G(1, y).
(22)
Производящая функция для полустепени выхода вершины, в которую можно попасть, двигаясь по случайно выбранному в графе реб16
ру:
1 ∂G
.
G1 (y) =
z ∂x x=1
(23)
Выражение для среднего числа соседей второго уровня z2 получим
при помощи уравнений (17) и (10):
2
2
2
∂
G(1,
y)
∂
G(x,
y)
∂
G(x,
y)
′′
.
z2 = G0 (y) =
=
=
∂y 2 x=1
∂y 2 x,y=1
∂y∂x x=1
(24)
Распределение размеров компонент выхода, достижимых из случайно выбранной в графе вершины, задается функцией H0 (y):
H0 (y) = yG0 (H1 (y)),
(25)
где H1 (y) = yG1 (H1 (y)) аналогично случаю неориентированных графов. Аналогичные равенства получаются и для компонент захода.
17
3. Модель кросс-холдинга Гая-Кападия
3.1. Общая структура
Систему из банков удобно представлять в виде ориентированного
графа. В таком случае вершины графа представляют сами банки,
а ребра — межбанковские связи. Входящие рёбра обозначают межбанкоские активы (например деньги, которые другие банки должны
данному банку), а исходящие — долговые обязательства банка. Таким образом, направление ребра однозначно устанавливает должника и кредитора.
Рассмотрим модель Гая-Кападия на ориентированном графе G(V, E),
|V | = N , где N достаточно велико. Для каждого i ∈ V вводятся
следующие величины, отражающие упрощенный балансовый отчёт
каждого банка:
• AIB
i — межбанковские активы.
• AM
i — внешние активы.
• LIB
i — межбанковские пассивы.
• Di — капитал, находящийся на счетах клиентов.
• Ki — собственные средства банка. Вычисляются по формуле:
M
IB
Ki = AIB
i + Ai − Li − Di .
(26)
Теперь нужно задать веса w(e) для каждого e ∈ E. В модели ГаяКападия на межбанковские активы приходится 20 процентов всех
18
активов банка. Если условно принять сумму всех активов банка за 1,
то величина межбанковских активов AIB
i = 0.2. Причем, для каждого банка они распределены равномерно между должниками, и тогда
вес каждого ребра задается следующим образом:
∀e = (v, u) ∈ E : w(e) =
0.2
u |,
|Ein
(27)
u
где Ein
= {e ∈ E|e = (x, u), x ∈ V }
M
M
IB
Поскольку AIB
i + Ai = 1, то Ai = 0.8. Межбанковские пассивы Li
определяются следующим образом:
LIB
i
=
w(e),
(28)
i
e∈Eout
i
где Eout
= {e ∈ E|e = (i, x), x ∈ V }
Банк i будем называть платежеспособным, если:
M
IB
(1 − ϕ)AIB
i + qAi − Li − Di > 0.
(29)
где ϕ - доля банков, у которых имеются обязательства к банку i и
которые при этом оказались неплатежеспособными, а q — цена, по
которой можно продать внешние активы.
Неравенство (29) можно переписать в виде:
ϕ<
Ki − (1 − q)AM
i
, AIB
i ̸= 0.
IB
Ai
(30)
Изначально система находится в равновесии, т. е. все банки являются платежеспособными. Если по каким-то причинам неравенство (29)
19
перестало выполняться, то тогда банк i будем называть неплатежеспособным или, что эквивалентно, объявившем дефолт. Причинами
выхода системы из состояния покоя могут стать различные внешние
факторы: мошенничество (например, как в случае с банком Barigns)
или общее снижение внешних активов вкупе с большими потерями
для одного из банков. А дефолт одного из участников системы может
вызвать целую волну дефолтов, которая будет распространяться по
системе.
Обозначим за ji полустепень захода для банка i. Поскольку каждый
банк теряет 1/ji от своих межбанковских активов при дефолте одной
из связанных с ним компаний, то из (30) следует, что единственный
случай, при котором дефолт может распространиться по системе —
это если один из смежных с i банков оказался неплатежеспособен, а
для самого i верно:
1
Ki − (1 − q)AM
i
<
.
ji
AIB
i
(31)
Введем еще одно определение: банк называется уязвимым, если он
может стать неплатежеспособным при дефолте хотя бы одного из
своих соседей. В противном случае банк будет называться надежным.
Вероятность того, что банк i с полустепенью захода j уязвим:
K − (1 − q)AM
1
i
i
vj = P
<
, ∀j ≥ 1.
j
AIB
i
20
(32)
3.2. Производящие функции
Теперь, имея в распоряжении такое понятие как уязвимый банк, составим формальный степенной ряд с коэффициентами, характеризующими веротяность появления уязвимого банка с полустепенями
захода и выхода, соответственно, j и k
G(x, y) =
vj pjk xj y k .
(33)
jk
Кроме того, можно определить и производящую функцию G0 (y) для
распределения полустепеней выхода уязвимого банка, которая будет
удовлетворять ранее полученному уравнению (22), но с учетом уязвимости банков примет вид:
G0 (y) = G(1, y) =
vj pjk y k .
(34)
vj pjk ≤ 1.
(35)
jk
Стоит также заметить, что:
G0 (1) = G(1, 1) =
jk
Таким образом, G0 (1) дает долю уязвимых банков.
Можно определить и еще одну производящую функцию G1 (y) для
набора вероятностей полустепеней исхода вершины, которую можно
достигнуть, двигаясь по случайно выбранному ребру:
vj jpjk y k
j,k
G1 (y) =
vj rjk y k =
.
jpjk
j,k
j,k
21
(36)
Теперь возьмём некоторый уязвимый банк v и пройдем по случайно
выбранному ребру e = (v, u). Если вершина u является надежным
банком, то остановимся, а если уязвимым, то повторим процедуру.
Все банки, которые можно достигнуть таким образом из исходной
вершины v назовём исходящим кластером уязвимости. Структура
такого кластера представлена на рисунке:
Обозначим за H1 (y) производящую функцию последовательности вероятностей достижения исходящего кластера уязвимости заданного
размера (в смысле количества уязвимых банков, которые он содержит) при движении по случайно выбранному исходящему из уязвимого банка ребру. Как видно из рисунка, суммарная вероятность будет состоять из вероятности попасть в надежный банк, вероятности
попасть в уязвимый банк без исходящих рёбер и т. д. Производящая
функция будет выглядеть следующим образом:
H1 (y) = p̂ + y
vj rjk (H1 (y))k .
(37)
jk
где p̂ — вероятность попасть в надёжный банк.
Подставив в уравнении (36) функцию H1 (y) вместо y и учитывая,
что p̂ = 1 − G1 (1), поскольку G1 (1) — вероятность перейти в один
22
уязвимый банк из другого уязвимого банка, получим:
H1 (y) = 1 − G1 (1) + yG1 (H1 (y)).
(38)
Осталось описать распределение случайной величины, которая отвечает за размер исходящего кластера уязвимости, которому принадлежит случайно выбранный банк. Ему будет соответствовать производящая функция H0 (y). Есть два варианта, которые могут возникнуть при случайном выборе банка в графе: во-первых, выбранный
банк может оказаться надежным. Во-вторых, с вероятностью vj pjk
он может оказаться уязвимым и иметь полустепени захода и выхода j
и k соответственно. Во втором случае каждое исходящее ребро ведёт
в некоторый исходящий кластер уязвимости, чей размер описывается функцией H1 (y). Следовательно, функция H0 (y) будет выглядеть
следующим образом:
H0 (y) = p̄ + y
vj pjk (H1 (y))k = 1 − G0 (1) + yG0 (H1 (y)).
(39)
jk
где p̄ — вероятность того, что выбранный банк оказался надёжным.
3.3. Фазовый переход
Хотя и не всегда можно получить выражение для производящих
функций в явной форме, но зато можно посчитать их моменты. В
частности, средний размер исходящего кластера уязвимости равен:
S = H0′ (1).
23
(40)
Взяв производную в уравнении (39) в точке 1 и учитывая, что производящая функция H1 (y) нормализована, получаем:
H0′ (1) = G0 [H1 (1)] + G0′ [H1 (1)]H1′ (1) = G0 (1) + G0′ (1)H1′ (1).
(41)
Аналогично возьмем производную в уравнении (38):
H1′ (1) =
G1 (1)
.
1 − G1′ (1)
(42)
И, подставляя (42) в (41), получаем:
G1 (1)G0′ (1)
S = G0 (1) +
.
1 − G1′ (1)
(43)
Как видно из (46) при G1′ (1) = 1 происходит фазовый переход, т. к.
в этой точке присутствует особенность. По-другому это равенство,
учитывая (36) и соотношение z = jpjk , можно записать так:
j,k
jkvj pjk = z.
(44)
j,k
где z — средняя полустепень захода (которая, однако, совпадает со
средней полустепенью выхода).
Предположим, что значение z велико. В этом случае наибольшие
значения pjk будет принимать при больших j и k. Таким образом,
левая часть уравнения (44) будет увеличиваться посредством jkpjk ,
но уменьшаться из-за члена vj , поскольку чем больше j, тем меньше
vj — это следует из (32). Значит, уравнение (44) будет иметь либо
2 решения, либо ни одного. В первом случае возникают непрерывный отрезок значений [z1, z2], для которых возможно возникновение
24
волны дефолтов. Если же значение средней степени лежит вне этого
отрезка, то:
• z < z1: член jkpjk слишком мал и сеть недостаточно связна
для распространения заражения (хорошим примером этого случая является сеть без ребер — в ней распространение дефолтов
невозможно).
• z > z2: vj слишком мало, и это означает, что в сети присутствует слишком много безопасных банков, что также не позволит
распространяться волне дефолтов.
25
4. Алгоритм моделирования случайного графа и запуск дефолтов
4.1. Общая схема
Модель случайного графа Ньюмена предполагает наличие заранее
известного закона распределения степеней вершин. Поскольку каждая вершина имеет полустепени захода и выхода, то наша задача промоделировать 2N значений случайной величины при N вершинах
графа. Случайные величины, отвечающие за эти степени, являются,
вообще говоря, независимыми, поэтому достаточно научиться моделировать случайную величину с фиксированным распределением, а
потом получить набор из 2N значений этой случайной величины.
Однако, из полученного набора не всегда возможно собрать граф.
Проверка допустимости осуществляется через равенство:
N
ji =
N
i=1
ki ,
(45)
i=1
где ji — полустепень выхода i-й вершины, а ki — её полустепень захода.
В случае, если данное равенство не выполняется, можно промоделировать набор из 2N значений еще раз. На практике же при при
больших значениях N вычисление подходящего набора может занять слишком много времени, поэтому достаточно изменить несколько значений ui и vi так, чтобы набор оказался допустимым.
26
4.2. Моделирование дискретной случайной величины
В качестве закона распределения степеней вершин для моделирования был выбран степенной закон распределения, который задаётся
следующим образом:
pk = Ck −τ ,
(46)
где C — коэффициент нормировки, а τ — параметр распределения.
Конкретные значения τ были выбраны данные из статьи [6], которые соответствуют финансовым параметрам в России. Причем для
распределений полустепеней входа и захода значения τ различны:
τin = 1.92, а τout = 2.64. Кроме того, распределение было сдвинуто таким образом, чтобы минимальная полустепень вершины была
равна 4.
Для моделирования дискретной случайной величины был выбран метод Уолкера, который описан в [5]. Это один из наиболее удобных
методов моделирования случайной величины. Основная идея заключается в следующем: пусть имеется некоторое дискретное распределение с K исходами. Далее берется равномерное распределение с
таким же количеством исходов. Те исходы i в оригинальном распределении, для которых P (i) > K1 назовём реципиентами, а для которых P (i) < K1 донорами. Причем излишки доноров равны P (i) − K1 .
Для каждого донора, зная его излишки, можно завести массив порогов, который будет указывать на то, какому реципиенту передавать
лишнюю вероятность. Таким образом, один донор может передавать
"лишнюю"вероятность сразу нескольким реципиентам. Имея вычис27
ленный массив порогов, необходимо запустить счетчик случайных
чисел и узнать значение равномерно распределенной случайной величины. Если её значение попадает в ту часть, которая является
излишком для донора, то по массиву порогов вычисляется реципиент, которому нужно передать "лишнюю" вероятность, и считается,
что случайная величина приняла значение, соответствующее этому
реципиенту.
Пример.
Пусть некоторое распределение с 4 исходами задается следующими
вероятностями:
X
A
B
C
D
P(X) 0.1 0.25 0.25 0.4
Здесь исход A - донор с излишком в 0.15. Заведем для него массив
порогов, который в данном случае будет состоять из единственного значения 0.25. Таким образом, если равномерно распределенная
случайная величина попадет на исход A, но превысит пороговое значение (на рисунке соответствует правой части полосы события А),
то будет считаться, что на самом деле выпал исход D.
28
4.3. Преобразование набора вершин в граф
На данном этапе мы располагаем набором из 2N вершин и значениями их полустепеней ji и ki , которые были взяты из заданного
распределения. Теперь требуется построить множество рёбер E графа таким образом, чтобы полустепени полученного графа G(V, E)
vin и vout были в точности такими как и смоделированные значения
ji и ki соответственно. Можно рассмотреть несколько вариантов соединения узлов графа:
• На каждой итерации равномерно и случайно выбирать одну из
вершин, которой нужно входящее ребро, и таким же образом
выбирать вершину, которой нужно выходящее ребро. После этого нужно попытаться их соединить. При этом не всегда будет
возможность поставить ребро между выбранной парой, т. к такое ребро уже может быть в графе (т. е. появляется опасность
возникновения кратных рёбер, которые не предполагаются в моделях кросс-холдингов), или ребро может быть потенциальной
петлёй. Плюсом данного метода является быстрая скорость выбора вершины — O(1) в каждом случае, однако общее время
метода излишне велико из-за того, что на последних итерациях
алгоритм пытается выбрать недопустимые рёбра и приходится
выбирать вершины снова.
• Второй вариант — на каждой итерации составлять список допустимых рёбер. В таком случае при постановке каждого ребра
приходится проводить предподсчет - проверять все пары вершин за O(N 2 ), однако выбор ребра происходит равновероятно из
множества рёбер, которые точно являются допустимыми. Данный метод можно улучшить, если на каждой итерации поль29
зоваться множеством допустимых рёбер из прошлой итерации,
пересчитывая его за O(N ) при хранении множества в виде односвязного списка.
4.4. Моделирование кросс-холдинга
Следующий шаг после расстановки рёбер — присвоить каждому e ∈
E некоторый вес w(e) > 0. Для этого достаточно для каждой вершины вычислить количество входящих в неё рёбер. Для всего графа
нагрузка рёбер будет произведена за
• O(N 3 ), если граф хранится в виде списка смежности.
• O(N 2 ), если граф хранится в виде матрицы смежности.
• O(N |E|), если граф хранится в виде списка рёбер.
Далее необходимо вычислить начальные значения элементов балани AM
сового отчета. Значения AIB
i задаются для каждой вершины
i
одинаково: по 0.2 и 0.8 соответственно. Для подсчёта размера межнужно для каждой вершины подсчитать
банковских пассивов LIB
i
суммарный вес исходящих рёбер. При известном Li немедленно вычисляется и размер депозитов Di и, таким образом, для различных
структур данных, используемых для хранения графа, время подсчёта будет следующее:
• O(N ), для списка смежности.
• O(N ), для матрицы смежности.
• O(|E|), для списка рёбер.
30
4.5. Моделирование дефолтов на полученном графе
Получив некоторый граф из заданного распределения, на нём можно запустить дефолт. Для этого выбирается некоторая вершина (или
сразу несколько вершин) в графе, и соответствующий банк объявляется неплатежеспособным, а все ребра, инцидентные данной вершине, теряют свой вес и пересчитываются балансовые значения для
каждого узла. Далее проверяется условие платежеспособности (29)
для всех смежных банков, и если какие-то банки на этой итерации
объявили дефолт, то та же процедура выполняется и для них. Данный процесс выполняется итеративно до тех пор, пока либо вся система не рухнет, либо распространение дефолтов не остановится.
4.6. Программа
Программа, моделирующая графы и распространение дефолтов на
них, написана на языке С++ и состоит из 5 модулей.
• Dip.cpp — Основной файл программы.
• Edge.h — Заголовочный файл для структуры, объектом которой
является ребро графа.
• walker.h — Заголовочный файл, в котором происходит моделирование случайной величины.
• Graph.h — Заголовочный файл для структуры, объектом которой является граф.
31
• Set− of− degrees.h — Заголовочный файл для структуры, объектом которой является множество степеней вершин.
Код программы доступен по ссылке:
https://github.com/Ulmashev/random_graphs
32
5. Результаты
Ниже представлены графики, иллюстрирующие некоторые результаты моделирования. Для значения каждого параметра была взята выборка из 50 графов. В начале рассмотрим влияние изменения
параметров распределения непосредственно на структуру графа, а
именно на число ребер:
График 1
График 1 иллюстрирует явную линейную зависимость между числом вершин и числом ребер в графе при заданном в (46) распределении.
Далее представлены графики зависимости числа ребер от смещения
параметров τin , τout и максимальной полустепени в графе:
33
График 2
График 3
График 4
34
Далее рассмотрим влияние различных параметров распределения на
количество банков, которые стали неплатежеспособными после дефолта случайно выбранного в графе банка. Это количество выражается в процентном соотношении относительно размера всей системы:
График 5
Как видно из графика 5, процент банков, объявивших дефолт при
таких параметрах распределения, примерно одинаков для всех значений N и находится в районе 42 процентов. Причем, если увеличить
минимальное значение полустепени с 4 до 5, то при тех же параметрах моделирования дефолт исходного банка никак не влияет на
систему.
35
График 6
График 6 иллюстрирует тот факт, что с увеличением τin количество
дефолтов становится чрезвычайно большим, что позволяет сделать
вывод о желательном понижении этого параметра.
График 7
36
Небольшие ограничения максимальной степени (подразумевается как
полустепень захода, так и полустепень выхода) графа не приводят к
существенным изменениям в проценте неплатежеспосбных банков:
График 8
График 9
График 9 показывает, что независимо от количества вершин, мат.
ожидание и среднее значение полустепени захода вершины при данном распределении почти совпадают.
37
Однако значения мат. ожидания и среднего значения полустепени
выхода, напротив, стабильно различаются на достаточно большую
величину:
График 10
В следующих графиках размер выборки был увеличен до 100. Можно посчитать значение vj , которое было выведено в (32), как отношение числа банков системы с полустепенью захода j, для которых
выполнено (31), к общему числу банков с полустепенью захода j. В
графиках представлены зависимости среднего числа различных полустепеней захода j, для которых vj = 1. Причем при q = 1 это
число стабильно равно 2, а значения j при этом равны 4 и 5, т. е. это
две минимально возможные полустени захода. Аналогичные эффекты наблюдаются и для остальных значений q. Эти данные лишний
раз иллюстрируют тот факт, что надежность системы укрепляется
вместе с ростом полустепеней банков.
38
q = 0.95:
График 11
q = 0.9:
График 12
q = 0.5:
График 13
39
Кроме количества банков, которые объявляют дефолт, интересно посмотреть и среднюю глубину волны дефолтов (под глубиной подразумевается наибольшее расстояние от первого банка, объявившего
дефолт, до некоторого другого банка, до которого дошла волна дефолтов):
График 14
Максимальные по выборке значения глубины дефолта:
График 15
40
Список литературы
[1] M. Elliott, B. Golub, M. O. Jackson. Financial Networks and
Contagion. American economic review, vol. 104, no. 10, 2014, pp.
3115-53.
[2] Райгородский А. М. Модели случайных графов. М .: МЦНМО,
2011.
[3] S. Kapadia, P. Gai. Contagion in financial networks. Proceedings of
Royal Society Series A, 466(2120),2010, pp. 2401–2423.
[4] M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs
with arbitrary degree distributions and their applications. Physical
review E 64 (2), 026118, 2001, arXiv:cond-mat/0007235v2.
[5] И. В. Романовский. Моделирование случайных распределений. Конспект лекций по курсу "Дискретный анализ".
http://www.math.spbu.ru/ru/Archive/Courses/jvr/DA_html/
_lec_1_07.html
[6] A.V. Leonidov and E.L. Rumyantsev. "Russian interbank networks:
main characteristics and stability with respect to contagion", Proc.
"Instabilities and Control of Excitable Networks: from macro- to
nano- systems MIPT, 2012, arXiv: 1210.3814
41
Отзывы:
Авторизуйтесь, чтобы оставить отзыв