Диссертация (1137870), страница 14
Текст из файла (страница 14)
В настоящейотносительнойработе тестируется возможностьиспользования четырех наиболее распространенных на практике классовалгоритмов сегментирования графов:1.на основе центральности ребер;2.спектральные методы поиска;3.поиск пересечения клик;4.методы максимизации модулярности.Для того, чтобы сделать работу более полной ниже приведенократкое описание процедур с использованием обозначений принятых внастоящей работе. В общем случае поиск сообществ предполагаетформализацию некой меры качества разбиения графа на сообщества ипоиск разбиений лучших с точки зрения такой меры.
Подробный обзоркритериев качества идентификации сообществ и подходов к ихмаксимизации приводится в [77].На основе центральности реберВероятно, самый распространенный и известный алгоритм былпредложенвработе[78].Вегоосновесостоитинтуитивно99привлекательная идея о том, что ребра графа, через которые проходитнаибольшее количество (кратчайших) путей между вершинами являются«мостами»,разделяющимисообщества.Процедурапредполагаетследующую последовательность операций:Алгоритм поиска сообществ на основе центральности ребер1.Рассчитать количество кратчайших путей, которое проходит черезкаждое из ребер.2.Удалить ребро с максимальным значением индикатора из п.13.Проверить выполняется критерий остановки поиска сообществ(например, возможно задать их количество априори).4.Если в п. 3 получен отрицательный ответ, то перейти к шагу 2.Источник: [78]Подход был обобщен для случая пересекающихся сообществ вработе [79].Спектральные методыСпектральные методы кластеризации являются современныхклассом алгоритмов.
Один из самых популярных подходов данногокласса был предложен в работе [80]:Алгоритм поиска сообществ на основе анализа спектра матрицы1.Задается взвешенная матрица близости2.Рассчитать3.Найтиуравнения40матрицу Кирхгофа, количество кластеров40сэлементамисобственных векторов являющихся решение следующего, где– матрица с– степенями вершин наВ англоязычной литературе чаще встречается название «Laplacian».100диагонали и 0 вне диагонали.4.Пусть– матрица, содержащая собственные векторыв колонках.5.Пусть6.Следует использовать алгоритм k-средних для кластеризации ..Источник: [80]Пересечение кликНесколько менее популярный и распространенный на практикеметод поиска сообществ заключается в поиске полных графов размераи их кластеров и был предложен в работе [81].
Конкретнее методпредлагает идентифицировать полные графы заданного размера в общемграфе. Затем возможно найти прилежащие полные графы, которыеобозначаются как графы, у которых различается лишь одной вершиной.Последовательно прилежащие клики тогда могут образовывать кластерывершин, которые являются более плотными по сравнению с остальнымграфом.Особенностью данного подхода является то, что он предполагаетвозможностьвершинграфапринадлежатьсразукнесколькимсообществам, скажем, в случае если эта вершина принадлежит к двумнеприлежащим кликам, которые не соединены, опосредовано другимикликами.Максимизация модулярностиИндикатор качества разбиения графа на сообщества под названием«модулярность» был предложен впервые в работе [78].
Интуитивноданный подход отталкивается от представления о том, что интереснымии похожими на сообщества являются группы участников, которые имеют101меньше связей с агентами за пределами группы, чем возможно было быожидать, если бы все связи формировались случайным образом.В следующей части работы предлагается обзор доступных данных,сравнение индикаторов качества алгоритмов и делаются выводыотносительно изолированности идентифицированных сообществ.Структура межбанковского рынкаВ основе настоящего исследования находится массив данныхаккумулированный Банком России на основе отчетности по операциямкредитных организаций на денежном рынке № 0409701.
Данный отчетдает возможность идентифицировать две стороны сделки и основные еепараметры: срок, процентную ставку, валюту. На основе даннойинформации мы конструируем матрицы близостидля каждого изпериодов усреднения41 начиная с января 2011 г. по апрель 2013 ., так чтосила связи между банками и в период усреднения обозначаемаяравна суммарному кредитованию банком банка за указанный период,аналогично,– суммарный объем кредитования банком банка .Для того, чтобы выбрать наиболее подходящий алгоритм длярассматриваемого в работе приложение мы предлагаем использоватьследующий критерий:1) устойчивость – группы банков должны идентифицироваться какодно сообщество стабильно в различные периоды усреднения.2)обособленностьперераспределение41идентифицированныхликвидностивнутрисообществ–идентифицированныхПериодом усреднения называется период за который кредитные организации должны в среднемудерживать определенный уровень корсчета.
Банком России для банков установлен периодусреднения продолжительностью в 1 месяц с 10 по 9 число каждого месяца. Подробная информация опериоде усреднения содержится в Положении Банка России от 29 марта 2004 года № 255-П “Обобязательных резервах кредитных организаций”.102сообществ должно быть сравнительно независимо от внешних длясообществ кредитных организаций3)размеридентифицированныхсообществдолженбытьсущественным, полностью соединенные, но тривиальные по размеру(например, состоящие из двух участников) группы не рассматриваются.Введем обозначение– разбивка вершин-банковграфа, заданного матрицей близости, на сообщества алгоритмом.Такая разбивка представляет собой множество набор групп вершин,которые идентифицированы как сообщества, где– номер сообщества,принадлежность к которому определил для банка в период алгоритм.Для того, чтобы идентифицировать устойчивые сообщества мывводим матрицус элементами, равными числу периодовусреднения, когда банки и были идентифицированы в качестве членоводно и того же сообщества, то есть количеству таких периодов.
Для того, чтобы сделать значения показателя сравнимым длявыборок с различным количеством периодов усреднения, мы делим всеэлементына количество периодов наблюдения и называем данныйпоказатель коэффициентом пересечения. В табл. 6 приведены значениякоэффициента пересечения для рассматриваемых методов поискасообществ и мер силы связи между кредитными организациями.103Таблица 6. Динамика коэффициента пересечения для первыхтрех крупнейших сообществ идентифицированных различнымиалгоритмамиСиласвязи/Методпоискаобъемкредитованиямежду парамибанковколичествосделоккредитованиямеждупаройбанковлогарифмобъема сделоккредитованиямежду парамибанков 42,долязаимствованиябанкомубанкаотсовокупногозаимствованиябанкацентральностиреберспектральныеметодыпересечениякликмаксимизациимодулярности0.0.000.030.070.090.110.150.210.220.0.09660.1826320.040.080.110.070.180.240.0.072160.2080650.040.080.110.0.06595780.1345740.040.050.080.440.480.420.1170.1970.2370.040.090.14Источник: расчет автора.Вторым критерием качества выступает способность алгоритмовидентифицировать относительно закрытые и плотные сообщества, такиесообщества которые предположительно могли бы быть интересны сточки зрения анализа распространения шоков ликвидности.
Мыиспользуем в качестве критерия обособленности выделенных сообществмодулярность,котораясталастандартнымпоказателемкачестваразбиения графа на сообщества в академической литературе и напрактике.что позволяет сделать разницу между оборотами крупных и некрупных участниковмежбанковского рынка менее разительной421041-ое сообщество2-ое сообщество3-е сообществоПояснение: на графике по оси x отложено количество кредитныхорганизаций вошедших в идентифицированное сообщество, по оси x –коэффициент цепного пересечения сообществ. Маркерами показанырезультатов идентификации сообществ различными алгоритмами:1 – максимизация модулярности, 2 – на основе центральности, 3 –пересечения клик, 4 – иерархической кластеризации, 5 – спектральныхметодов.Всего для каждого из методов на графиках приведено по 26 точек, чтосоответствует количеству рассматриваемых периодов усреднения.Красной цифрой указано среднее значение количество членовсообщества и коэффициента цепного пересечения сообществ зарассматриваемые периоды усреднения, ее размер пропорционаленсреднему количеству членов сообщества.Рисунок 22.
Устойчивость идентификации 3 наиболеекрупных сообществ банковРисунок 23. Распределение модулярности сообществ банков,идентифицированных различными алгоритмамиПояснение: на графике приведены оценки плотности вероятностираспределений модулярности рассчитанные на основе значений данногопоказателя рассчитанных для рассматриваемого набора периодов105усреднения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
