Использование квази-клик для анализа графа рынка России

Размещено на http://www.allbest.ru/

Правительство Российской Федерации

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

"Национальный исследовательский университет

"Высшая школа экономики"

Факультет информатики, математики и компьютерных наук

Кафедра информационных систем и технологий

Выпускная квалификационная работа

на тему "Использование квази-клик для анализа графа рынка России"

Студент группы 13 МАГ БИ

Прокофьев А.А.

Руководитель доцент, к.э.н.,

Визгунов Арсений Николаевич



Введение

Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей, сети Интернет, естественных экосистем, телекоммуникационных сетей и других. Не является исключением и финансовый сектор, представляющий огромные сетевые структуры, как в масштабах страны, так и по всему миру. Одной из наиболее интересных задач в таком моделировании является поиск кластеров, иными словами, сильно связанных подмножеств. Хорошим описанием таких структур является клика, определенная как множество вершин, в котором любые две вершины связаны ребром. Основной проблемой является то, что задача нахождения точного решения является NP-сложной.

Поиску максимальной клики в графе посвящены многие работы [1][8][9]. Также существует мнение, что требование любых двух вершин быть связанными слишком строго, когда мы опираемся на реальные экспериментальные данные [17]. Поэтому ряд работ рассматривает "релаксацию" клики, где используется понятие квази-клики, допускающей отсутствие некоторых ребер в решении [9][13][16][17][20].

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

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

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

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

Изучить теоретические аспекты применения графа-рынка;

Осуществить программную реализацию алгоритма поиска максимальных квази-клик в графе;

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

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



1. Использование теории графов для описания фондового рынка России.

1.1 Экономические и финансовые сети

На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства, банки, фирмы владеют акциями, облигациями и долгами друг друга, что ведет к росту оборота ценных бумаг на мировом рынке. Рост числа взаимосвязей между экономическими объектами приводит к сильным зависимостям в их поведении. Ярким примером таких зависимостей является мировой финансовый кризис 2007-2008 годов, начавшийся в США. Обвал на фондовом рынке был вызван бумом и крахом в кредитном и жилищном секторах, а затем и на сырьевых рынках [25]. События мирового финансового кризиса развивались лавинообразно, затронув все страны мира и все финансовые институты, подчеркнув уязвимость современных финансовых отношений. Для России, как сырьевой страны, одним из важных влияющих факторов стало снижение мировых цен на нефть [24].

Все это свидетельствует о ярко выраженных сетевых структурах в мировых финансовых отношениях. Сетевой подход к финансовым системам особенно важен при оценке финансовой устойчивости системы и может играть важную роль при изучении внешних факторов, когда риск для одного узла может сильно повлиять на всю систему [2]. После кризиса 2008 года исследователи начали уделять особое внимание изучению финансовых рынков с точки зрения сетей. Применение сетевого подхода наглядно представляет исследователям картину современных финансовых отношений и позволяет изучать динамику развития возможных сценариев. В работе Contagion in financial networks исследователи демонстрируют модель распространения "инфекций" в финансовых сетях с произвольной структурой, применяя теорию графов [11]. Модель, разработанная авторами, позволяет моделировать сценарий распространения "инфекций" в финансовых сетях, в том числе для рынка межбанковских отношений и для платежных систем. Авторы делают вывод, что высокая связность внутри сети может как снизить вероятность "заражения" сети, так и повысить вероятность широкого распространения при возникновении проблемы.

В работе Financial networks and contagion авторы аналогично моделируют сценарии распространения "инфекции" и каскады неудач среди организаций, связанных через сеть финансовых взаимозависимостей [10]. Исследователи рассматривают процессы интеграции (когда организация становится более зависима от своих контрагентов) и диверсификации (когда организация взаимодействует с большим количеством агентов) и выделяют несколько важных особенностей. Во-первых, что необходимо разделять эти два процесса, так как они имеют совершенно разное влияние на распространение "инфекций" в сети, а во-вторых, то, что необходимо искать компромисс для обоих процессов. Первоначальное увеличение диверсификации в сети позволяет "инфекции" распространяться дальше, но последующее увеличение позволяет сделать организации менее зависимыми друг от друга и остановить распространение. Что касается интеграции, то здесь нужно искать компромисс между увеличением зависимости от других организаций и уменьшением чувствительности к собственным инвестициям.

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

В последние годы популярным методом исследования фондовых рынков является построение и анализ графа рынка, вершинами которого являются акции, торгующиеся на бирже, а вес ребра определяет степень зависимости двух акций друг от друга. Такой подход впервые был предложен в статье On structural properties of the market graph в 2003 году [5].

1.2 Понятие и применение графа рынка

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

Рассмотрим подробнее модель графа рынка, которую используют исследователи в ряде работ [5][6][7]. Основой модели является сеть отражающая взаимозависимости на фондовом рынке, где в качестве меры близости использована корреляция между доходностями акций [14]. Для начала исследования берется набор акций и информация об изменении их цен за определенный период. Далее рассчитываются коэффициенты корреляции между акциями по формуле:

,



где отражает доходность ценной бумаги i в день t по отношению к предыдущему дню t-1 и рассчитывается как

,

- цена акции, показывает среднюю доходность акции i за n дней

,

а определяет дисперсию доходности i-ой акции за n дней

.

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

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

1.3 Данные о Российском рынке

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

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

Рынки ценных бумаг делят на первичный и вторичный [21]. Первичный - рынок, на котором происходит первичное размещение ценных бумаг, вторичный рынок позволяет инвесторам свободно покупать и продавать ценные бумаги. На вторичном рынке происходит обращение ценных бумаг, что формирует интерес инвесторов и позволяет предприятиям получать необходимую финансовую поддержку. Наиболее интересной структурой вторичного рынка является биржевой рынок, который представлен обращением ценных бумаг на биржах. Биржевой рынок отличается от внебиржевого организованностью, а это значит, что существует определенное место, время и правила торговли ценными бумагами [21]. Это позволяет собирать и анализировать статистические данные с торгов, что представляет исследовательский интерес.

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

Становление Российского фондового рынка можно разделить на 4 последовательных этапа: дореволюционный, советский, постсоветский и современный [26]. Первый этап дореволюционный датируется началом XVIII века и связан с учреждением первой биржи в Санкт-Петербурге. Затем происходит бурный рост использования долговых расписок, облигаций, векселей. В советский период появляются акции трудовых коллективов и идет разработка нормативно-правовой базы фондового рынка. Постсоветский период характеризуется активным вмешательством государственных органов в регулирование рынка ценных бумаг. Современный период отсчитывается с 1997 года до настоящего времени и включает в себя череду кризисных ситуаций на рынке, демонстрирующих неэффективность созданной правовой системы по регулированию фондового рынка.

Крупнейшей фондовой биржей России по состоянию на 2015 год является Московская Биржа. Московская Биржа представляет собой биржевой холдинг, образованный 19 декабря 2011 года в результате слияния биржевых групп ММВБ и РТС, основанных в 90-е годы. Московская Биржа входит в двадцатку ведущих мировых площадок по объему торгов ценными бумагами, суммарной капитализации торгуемых акций и в десятку крупнейших бирж производных финансовых инструментов.

Биржевой индекс (фондовый индекс) - это индикатор состояния рынка ценных бумаг, рассчитанный определенным образом на основе корзины наиболее ликвидных обыкновенных акций или облигаций. Биржевые индексы позволяют оценить состояние фондового рынка в едином целом, определить текущий момент в экономическом цикле. Основные индексы Московской Биржи (Индекс ММВБ и Индекс РТС) представляют собой ценовые, взвешенные по рыночной капитализации композитные индексы российского фондового рынка, включающие 50 наиболее ликвидных акций крупнейших и динамично развивающихся российских эмитентов, виды экономической деятельности которых относятся к основным секторам экономики. Ежедневный объем торгов на бирже по состоянию на май 2015 года составляет порядка 1.8 триллионов рублей.

1.4 Способы анализа графа рынка. Нахождение максимальной клики и максимального независимого множества

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

Первым шагом на пути изучения графа рынка является выделение максимальной клики графа и максимального независимого множества. Анализ клик и независимых множеств дает наглядное представление о внутренней структуре фондового рынка. Например, клика в графе рынка может представлять собой группу акций, чьи цены изменяются схожим образом. Например, изменение цены одной акции из группы влияет на цену всех остальных акций группы. Независимые множества, наоборот, могут демонстрировать пример отрицательной корреляции друг к другу, иными словами, могут составлять диверсифицированный портфель акций. Такой подход к изучению графа рынка впервые описан в работе On structural properties of the market graph [5]. Существует 2 понятия максимальной клики - максимальная по размеру и максимальная по включению. Нам нужно различать максимальную клику по размеру и максимальную клику по включению. Клика является максимальной по включению, если не является подмножеством любой другой клики. Клика, максимальная по включению, является максимальной по размеру, если имеет наибольшую мощность (вес) в графе [8].

Другим подходом, дополняющим поиск подмножеств, является статистический анализ графа. В частности, интересными характеристиками являются: максимальная степень вершины графа, распределение коэффициента корреляции в исходной матрице рынка, распределение степени вершин графа в зависимости от выбранного порога корреляции, плотность ребер в графе, вычисление коэффициента кластеризации [6][7]. Коэффициент кластеризации является количественной характеристикой того, на сколько сильно связаны соседние вершины в графе [18]. Коэффициент кластеризации позволяет судить о том, на сколько сильно граф разбит на отдельные кластеры.

Таким образом, исследование рыночного графа сводится к выделению некоторых его структурных характеристик, в частности максимальных клик, их объединений и пересечений, максимальных независимых множеств, а также статистический анализ его числовых параметров. Для целей исследования нам важен поиск клики максимальной по размеру, а также поиск квази-клик максимального размера. Квази-клика представляет собой релаксацию клики, то есть допускает отсутствие некоторого числа ребер в клике. Формально квази-клику можно определить несколькими способами, о которых будет рассказано в следующей главе.



2. Алгоритмы поиска плотных подграфов в графе

Задача о клике.

Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17].

Пусть G=(V,E) - простой неориентированный граф, где V - множество n вершин, а E - множество ребер графа. Для u, v ? V, dG(u, v) - длина кратчайшего пути между вершинами u и v в графе G. d(G) = maxu,v?V dG(u, v) - диаметр графа G. Для множества S, S ? V, существует граф G[S] = (S, E ? S Ч S), который называется подграф графа G на множестве S. Граф G = (V,E) называется полным, если все вершины графа попарно соединены, то есть ?i, j ? V, i ? j, существует ребро (i, j) ? E. Клика C - представляет собой такое подмножество вершин из V, что подграф G[C] графа G, построенный на множестве C, является полным. Как было сказано ранее клика может быть максимальной по включению и максимальной по размеру. Клика называется максимальной по включению, если она не является подмножеством большей клики, и максимальной по размеру, если не существует большей клики в графе. Задача поиска максимальной по размеру клики (the maximum clique problem) заключается в том, чтобы найти клику максимальной мощности в графе G.

Поиск клики в графе является NP-сложной задачей и принадлежит к классу NP-полных задач [15]. Как и для других NP-полных задач, эффективного алгоритма для поиска клики заданного размера на данный момент не найдено [23]. Точное решение требует экспоненциального времени, что сильно затрудняет вычисления для больших объемов входных данных [6].

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

Задача о квази-клике.

Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный момент известно несколько формальных способов определения понятия квази-клики. Согласно статьи On the maximum quasi-clique problem первый и самый распространенный определяется следующим образом [17].

Представим граф G=(V, E), определенный в предыдущем параграфе, и некоторое фиксированное вещественное число г, удовлетворяющее условию 0 < г < 1. Подмножество вершин Q называется г-квази-кликой или просто г-кликой, если плотность ребер графа G[Q], расcчитанная как отношение числа ребер, вошедших в граф, к числу всех возможных ребер на подмножестве Q, по меньшей мере равна г. Для случая г=1 задача поиска квази-клики сводится к задаче поиска максимальной клики. Плотность ребер в графе можно вычислить следующим образом:

где E - количество существующих ребер в графе, V - количество вершин графа.

Согласно другим работам, квази-клику можно определить по-другому [13] [20].

Пусть S подмножество k - вершин графа G, S?V(G), представляющее искомый граф G(S). Подмножество S называется г-квази-кликой для 0<г?1, если для любой вершины v, v?S, degG(S) (v)? [г?(k-1)], где deg(v) - степень вершины v, то есть подграф удовлетворяет условию ограничения минимальной степени вершины [г?(k-1)], заданному исследователем.

Также встречается третий вариант определения квази-клики [9]. Он объединяет первый и второй подходы, а клика называется (л, г)-квази-клика. Таким образом, группа вершин будет являться (л, г)-квази-кликой, если выполняются оба условия - плотность рёбер в графе и минимальная степень вершины в группе. Где л, г - соответствующие пороговые значения для плотности ребер и минимально степени вершины, 0 ? л ? г ? 1. Формально условия можно определить следующим образом:

? v ? V': degV'(v) ? л · (|V'| ? 1)(1)

|E'| ? г · ( |V'| / 2),(2)

где V' - множество вершин подграфа, а E' - множество ребер подграфа.

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

Алгоритмы поиска квази-клики в графе.

Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска максимальной клики в графе является NP-полной, тем не менее, существуют довольно эффективные алгоритмы для поиска точного решения. Это связано с тем, что клика обладает свойством замкнутости - любое подмножество клики также является кликой. К сожалению, это свойство не выполняется для квази-клик, поэтому точные алгоритмы являются довольно сложными. Задача нахождения максимальной квази-клики в графе также является NP-полной, что доказано в работе On the maximum quasi-clique problem [17]. Тем не менее, авторы предлагают полный математический расчет, который может быть использован для нахождения точного решения. Авторы делают акцент на то, что предложенные формулы позволяют находить оптимальные решения для небольших графов.

Существуют эвристики, использующие некоторые допущения. Например, Vertex Support Algorithm или метод опорных векторов, ориентированный на поиск минимального покрытия графа. Найденное решение может быть использовано как начальное множество при поиске квази-клик, что существенно упрощает дальнейшие вычисления [3]. Также применяется алгоритм ветвей и границ (branch-and-bound) [16].

Наиболее популярным алгоритмом является жадный алгоритм (GRASP) для поиска приближенных решений. Алгоритм позволяет находить очень хорошие и зачастую оптимальные решения. Впервые данный подход был предложен в работе On maximum clique problems in very large graphs [1]. Жадный алгоритм ориентирован на поиск максимальных клик и представляет собой итеративный подход, где на каждой итерации строится случайное решение, основанное на "жадном" отборе вершин, которые войдут в решение (рис. 1).

Рисунок 1. Алгоритм GRASP [1].

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

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



3. Применение квази-клики для анализа графа рынка

В статье Network approach for the Russian stock market авторы анализируют данные фондового рынка для России, в том числе используют поиск максимальной клики для выделения и дальнейшего изучения сильно связных акций [19]. Согласно данным результатам на российском рынке существует группа акций, которые стабильно входят в максимальную клику практически во всех исследуемых периодах. С другой стороны, интересным наблюдением является то, что группа акций с наибольшим оборотом на российском рынке представляет собой практически эту же группу акций, в зависимости от выбранного порога корреляции. Таким образом, авторы делают вывод, что для российского рынка набор акций, стабильно входящих в максимальную клику, состоит из наиболее торгуемых акций на фондовой бирже.

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

3.1 Построение графа рынка России

Для начала работы с алгоритмической частью требуется построить граф рынка. Для того, чтобы проанализировать правильность подхода с применением квази-клики, необходимо проанализировать те же данные и те же периоды, что и описанные в работе Network approach for the Russian stock market [19]. Таким образом, в качестве исходных данных были взяты данные о торгах акций на Московской Бирже с 1 сентября 2007 года по 16 сентября 2011 года. Использовались данные о торгах 177 активных акций в течении 1000 дней. Динамика рынка рассматривалась в 11 периодах длительностью 500 дней с пересечением между периодами в 50 дней (табл. 1).

Таблица 1. Разделение данных на 11 периодов по 500 дней.

Period #	Starting date	Ending date
1	09/01/2007	09/11/2009
2	11/13/2007	11/23/2009
3	01/31/2008	02/09/2010
4	04/14/2008	04/22/2010
5	06/27/2008	07/06/2010
6	09/05/2008	09/14/2010
7	11/21/2008	11/24/2010
8	02/09/2009	02/11/2011
9	04/22/2009	04/26/2011
10	07/06/2009	07/08/2011
11	09/14/2009	09/16/2011

Исходные данные были представлены в виде CSV-файла. Для представления данных в виде графа рынка был реализован синтаксический анализатор в виде программного кода (см. Приложение 1). Основными шагами при построении граф рынка являются:

1) Построение матрицы корреляций всех акций между собой;

2) Замена значений, которые больше заданного порога на 1, остальные элементы на 0.

Таким образом, мы получаем граф рынка, представленный в виде матрицы смежности A, где aij=1 означает, что вершины i и j соединены ребром.



3.2 Нахождение квази-клик за заданный период

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

где E - количество существующих ребер в графе, V - количество вершин графа. Таким образом, плотность после добавления новой вершины должна остаться в пределах допустимого значения, то есть не меньше, чем заданный порог плотности:

где Vadj - количество вершин из текущего решения, с которыми связана новая вершина, иными словами число новых ребер, появившихся в решении, после добавления новой вершины. Так E+Vadj представляет собой суммарное число ребер в решении после добавления новой вершины, а измененный знаменатель представляет собой увеличение общего числа вершин на 1. Используя полученную плотность можно судить о том, разрешено ли добавить эту вершину в решение.

Алгоритм по шагам:

1. Выбирается 1 случайная вершина в графе со степенью выше "некоторого порога" - это начало будущей квази-клики.

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

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

Как выяснилось позже, данный подход сильно подвержен воздействию выбора стартовой вершины для работы алгоритма.

На языке Java функция поиска выглядит следующим образом:

private static List<String> findQuasiClique(int[][] marketGraph,

String[] indexes, String startNode) {

// future result

List<String> clique = new ArrayList<String>();

int n_clique_e = 0;

// Getting degree of every vertex

Map<String, Parameters> vertexDegreesMap = getVerticesDegrees(

marketGraph, indexes);

Iterator<String> iter = vertexDegreesMap.keySet().iterator();

// int i = 0;

while (iter.hasNext()) {

String cur = iter.next().toString();

debug("[" + cur + ": " + vertexDegreesMap.get(cur).toString()

+ "]; ");

String startPoint = "";

List<String> currentArray = new ArrayList<String>();

// if start node is empty getting random, otherwise using suggested one

if (startNode.isEmpty()) {

out("Random start node will be used\n");

// Searching for max degree

Iterator<String> iter2 = vertexDegreesMap.keySet().iterator();

String maxDegName = "";

int maxDeg = 0;

while (iter2.hasNext()) {

String cur = iter2.next().toString();

if (vertexDegreesMap.get(cur).getDegree() > maxDeg) {

maxDeg = vertexDegreesMap.get(cur).getDegree();

maxDegName = cur;

debugn("\nName of max degree is " + maxDegName + "; Max degree is "

+ maxDeg);

// Getting 1 random vertex with degree higher then threshold

double degreeThreshold = maxDeg / 2 + maxDeg / 4;

debugn("degreeThreshold: " + degreeThreshold);

Iterator<String> iter3 = vertexDegreesMap.keySet().iterator();

while (iter3.hasNext()) {

String cur = iter3.next().toString();

if (vertexDegreesMap.get(cur).getDegree() >= degreeThreshold) {

currentArray.add(cur);

// debug(cur + ", ");

debugn("currentArray1=" + currentArray.toString());

final Random random = new Random();

int index = random.nextInt(currentArray.size());

debugn("index=" + index);

startPoint = currentArray.get(index);

debugn("startPoint=" + startPoint);

} else {

startPoint = startNode;

// Add start node into the result

clique.add(startPoint);

// Update currentArray with only vertices adjusted to start node

currentArray = vertexDegreesMap.get(startPoint).getAdjVertices();

debugn("currentArray2=" + currentArray.toString());

// now we will be checking all nodes adjusted to our clique iteratively

// we will add only vertices that satisfy our density condition

while (true) {

Iterator<String> iter4 = currentArray.iterator();

List<String> accepted = new ArrayList<String>();

while (iter4.hasNext()) {

String curr = iter4.next();

// skip all node that are already in clique

if (!clique.contains(curr)) {

int numofadjverts = 0;

// check how much vertices from current clique are adjusted

// to current node

List<String> adjNodes = vertexDegreesMap.get(curr)

.getAdjVertices();

for (String s : adjNodes) {

if (clique.contains(s)) {

numofadjverts++;

// Checking if density condition is true and adding vertex

// to

// the list of accepted

if (n_clique_e != 0) {

debugn("Clique.size()=" + clique.size()

+ " n_clique_e=" + n_clique_e

+ " numofadjverts=" + numofadjverts);

debugn("Node=" + curr + ", Expected density="

+ (double) (2 * (n_clique_e + numofadjverts))

/ ((clique.size() + 1) * (clique.size())));

if ((double) (2 * (n_clique_e + numofadjverts))

/ ((clique.size() + 1) * (clique.size()))

>= DENSITY_THRESHOLD) {

accepted.add(curr);

} else {

accepted.add(curr);

if (accepted.size() == 0) {

break;

// Getting one random vertex from accepted list and adding into the

// clique

// and also updating number of edges in our current clique

final Random random2 = new Random();

int index2 = random2.nextInt(accepted.size());

List<String> adjVerts2 = vertexDegreesMap.get(accepted.get(index2))

.getAdjVertices();

int numofadjverts = 0;

for (String s : adjVerts2) {

if (clique.contains(s)) {

numofadjverts++;

// we prevent adding in the list nodes that are already their so

// it should be safe just to add new node

clique.add(accepted.get(index2));

// number of edges in graph is increased on number of new

// connections

n_clique_e += numofadjverts;

debugn("n_clique_e = " + n_clique_e);

debugn("clique = " + clique.toString());

Iterator<String> adjIter = vertexDegreesMap

.get(accepted.get(index2)).getAdjVertices().iterator();

while (adjIter.hasNext()) {

String curr = adjIter.next();

if (!currentArray.contains(curr)) {

currentArray.add(curr);

return clique;

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

Первоначальное тестирование показало, что работа алгоритма на системе с процессором Intel Core i5 3.3Ghz, 8GB RAM, Windows 7 занимает не более 1-ой секунды для графа рынка в 177 акций. В ходе дальнейшего тестирования работы алгоритма было замечено, что результаты разных запусков могут отличаться между собой. Это связано с тем, что алгоритм рандомизирован при выборе начальной вершины и выборе дальнейших вершин на добавление. Было принято решение модифицировать алгоритм, чтобы он мог находить все возможные максимальные квази-клики в заданном периоде. Для этого в качестве начальной вершины передавались все доступные вершины графа, для каждой вершины алгоритм запускался 100 раз и так для каждого из 11-ти периодов:

for (String s : Parser.indexes) {

for (int i = 0; i < 100; i++) {

List<String> qclique = findQuasiClique(marketGraph[q],

Parser.indexes, s);

if (qclique.size() > maxsize) {

maxsize = qclique.size();

maxclique = new ArrayList<List<String>>();

maxclique.add(qclique);

} else if (qclique.size() == maxsize) {

maxclique.add(qclique);

Таким образом, алгоритм срабатывает 177 *100*11=194700 раз за время работы программы. Суммарное время работы для расчета 11 периодов составило 42 секунды. В результате удалось получить устойчивые по количеству и составу квази-клики.

Разработанная программа состоит из 4-х основных модулей:

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

2. Класс Parser позволяет загружать входные данные из CSV-файла. Для синтаксического разбора CSV-файла была использована открытая библиотека opencsv. Затем входные данные обрабатываются и составляется сетевая модель рынка, представляющая матрицу корреляции доходностей ценных бумаг. Полученная матрица приводится к графу рынка, с использованием некоторого порога корреляции, который можно задать в исходном коде программы.

3. Класс Parameters представляет вспомогательную структуру данных. Объект класса Parameters содержит основные характеристики вершины графа, использующиеся при расчете - степень и список соседей.

4. Класс QuasiCliqueFinder является основной частью работы. В этом модуле реализован алгоритм поиска квази-клики. Функция main класса содержит тестовые входные данные, входные данные для графа рынка России, логику их обработки, а также обработку и вывод результатов.

Основной алгоритм использует плотность искомого графа в качестве параметра, поэтому при плотности 100% ожидалось получить все максимальные клики графа для заданных периодов. В качестве порога корреляции был выбран 0.5, указанный в статье Network approach for the Russian stock market, чтобы сравнить результаты на одинаковых входных параметрах [19]. Результаты оказались идентичны описанным в статье, за небольшим исключением. Для периода 3 было найдено 6 максимальных клик, вместо 1. Сравнение результатов при поиске максимальных клик представлены в таблице (табл. 2). Данные, отмеченные серым фоном, - результаты работы моего алгоритма, остальные данные взяты из статьи.

Таблица 2. Количественные характеристики качества работы алгоритма.

Period#	The number of maximum cliques	The number of maximum cliques	The size of maximum clique	The size of maximum clique	The size of union of elements of max cliques	The size of union of elements of max cliques
1	2	2	19	19	21	21
2	3	3	19	19	22	22
3	1	6	19	19	19	24
4	8	8	19	19	27	27
5	3	3	22	22	25	25
6	2	2	22	22	23	23
7	4	4	15	15	17	17
8	3	3	16	16	18	18
9	1	1	16	16	16	16
10	3	3	14	14	16	16
11	9	9	14	14	19	19

Состав найденных клик также был идентичен, за исключением периода 3 (табл. 3).

Таблица 3. Состав объединения максимальных клик за каждый из периодов.

Period#	Stocks in union of maximum cliques	Stocks in union of maximum cliques
1	CHMF, GAZP, GMKN, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	CHMF, GAZP, GMKN, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
2	CHMF, DVEC, GAZP, GMKN, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	CHMF, DVEC, GAZP, GMKN, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
3	AKRN, CHMF, GAZP, LKOH, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TRNFP, URKA, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MMBM, MSNG, MTSS, NLMK, NVTK, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR
4	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, GMKN, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, URKA, VTBR
5	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
6	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TRNFP, VTBR	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TRNFP, VTBR
7	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR	AFKS, AKRN, CHMF, GAZP, GMKN, LKOH, MTSS, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, VTBR
8	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, TATNP, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, TATNP, VTBR
9	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, VTBR
10	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR
11	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TRMK, VTBR	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TRMK, VTBR

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

Убедившись в правильности работы алгоритма для поиска клик, был осуществлен переход к анализу квази-клик. Итеративно запуская алгоритм и постепенно уменьшая порог плотности клики, были собраны данные о качественном и количественном составе квази-клик (табл. 4). Порог корреляции остался зафиксированным на значении 0.5.

Таблица 4. Размер максимальной квази-клики при изменении порога плотности.

Period # Denisty	1	2	3	4	5	6	7	8	9	10	11
1.00	19	19	19	19	22	22	15	16	16	14	14
0.99	19	20	20	21	23	23	16	17	16	15	15
0.98	21	21	21	21	25	24	17	18	16	15	16
0.97	21	22	23	22	25	25	17	18	17	16	17
0.96	22	24	24	24	26	26	17	18	18	16	18
0.95	23	24	25	25	27	27	17	19	18	17	18
0.94	23	25	25	25	28	27	18	19	19	17	19
0.93	24	26	26	26	29	28	18	20	19	17	19
0.92	25	26	27	27	30	29	18	20	19	18	19
0.91	25	27	27	27	30	30	19	20	20	18	20
0.90	26	27	28	28	31	31	19	21	20	18	20
0.85	29	30	31	31	34	34	20	22	22	19	22
0.8	32	33	34	34	37	37	22	24	24	20	23
0.75	35	36	37	37	39	40	23	25	25	21	25
0.7	37	39	39	39	41	42	24	26	27	23	26
0.5	47	48	48	48	50	51	29	32	33	30	33



Как видно из таблицы, с уменьшением порога плотности для квази-клики её размер возрастает и, начиная с порога плотности 0.92, полностью перекрывает размер объединения максимальных клик, полученных в статье Network approach for the Russian stock market.

3.3 Анализ полученных квази-клик

Как было замечено в статье Network approach for the Russian stock market, для российского рынка наиболее ценные акции имеют сильные связи между их доходностями [19]. Таблица 5 содержит акции, торгующиеся в наибольшем объеме на российском рынке - 11 акций, представляющих 91,98% фондового рынка России за весь исследуемый период (табл. 5).

Таблица 5. Доминирующие акции российского рынка в процентном выражении.

	Всего	1	2	3	4	5	6	7	8	9	10
SBER	30,83	21,71	24,66	27,19	29,27	31,79	33,65	34,62	34,75	34,34	33,12
GAZP	24,94	30,47	29,58	27,67	26,37	25,04	23,77	22,43	21,89	22,43	23,08
GMKN	8,56	12,21	10,60	9,54	8,36	8,21	7,57	7,49	7,66	7,53	7,74
LKOH	8,09	11,35	10,45	10,13	9,50	8,13	7,24	6,90	6,66	6,38	6,46
ROSN	5,37	5,04	5,13	5,29	5,43	5,49	5,45	5,34	5,36	5,37	5,53
VTBR	5,00	4,39	4,85	5,04	4,95	4,88	4,92	5,03	5,11	5,20	5,19
SBERP	4,20	2,47	2,91	3,49	3,77	4,12	4,64	4,94	5,07	5,19	4,80
SNGS	1,85	3,06	2,60	2,34	2,14	1,78	1,62	1,50	1,43	1,34	1,36
HYDR	1,22	0,47	0,60	0,71	0,96	1,25	1,41	1,50	1,55	1,58	1,63
TRNFP	0,98	0,34	0,38	0,47	0,65	0,84	1,07	1,26	1,29	1,36	1,44
CHMF	0,94	0,53	0,50	0,60	0,75	0,82	0,93	1,02	1,11	1,17	1,30

Для того, чтобы сделать вывод о полученных результатах, необходимо изучить качественный состав найденных квази-клик. Рассмотрим подробнее состав квази-клик при пороге плотности 0.92, так как в этом случае размер максимальной квази-клики больше либо равен размера объединения максимальных клик за идентичный период (табл. 6).

Таблица 6. Количественный состав квази-клик при плотности 0.92 и корреляции 0.5.

Период	Количество максимальных квази-клик	Размер максимальной квази-клики	Размер объединения	Размер пересечения	Состав пересечения
1	40	25	31	18	GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKB, RASP, ROSN, SBER, SBERP, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
2	54	26	35	19	DVEC, GAZP, LKOH, MSNG, MTSS, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
3	14	27	31	24	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
4	8	27	31	24	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
5	4	30	31	27	AKRN, CHMF, DVEC, FEES, GAZP, LKOH, MSNG, MSSB, MTSS, NLMK, NVTK, OGKA, OGKB, OGKC, OGKE, RASP, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, TATNP, TGKE, TRNFP, VTBR
6	81	29	36	20	AKRN, DVEC, FEES, GAZP, LKOH, MSNG, MTSS, NLMK, NVTK, OGKA, OGKB, ROSN, SBER, SBERP, SNGS, SNGSP, TATN, TATNP, TRNFP, VTBR
7	11	18	23	12	AFKS, CHMF, GAZP, GMKN, LKOH, MTSS, ROSN, SBER, SBERP, SIBN, SNGS, VTBR
8	7	20	22	16	AFKS, CHMF, GAZP, GMKN, LKOH, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, TATNP, VTBR
9	9	19	23	16	AFKS, CHMF, GAZP, GMKN, LKOH, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, TATN, VTBR
10	1	18	18	18	AFKS, CHMF, GAZP, GMKN, LKOH, MAGN, MTLR, MTSS, NLMK, NVTK, ROSN, SBER, SBERP, SIBN, SNGS, SNGSP, TATN, VTBR
11	9	19	22	13	AFKS, CHMF, GAZP, GMKN, MTLR, NLMK, NVTK, ROSN, SBER, SBERP, SNGS, SNGSP, VTBR

Как видим в периодах 1, 2 и 6 количество найденных максимальных квази-клик довольно велико по отношению к другим периодам, в то же время размер объединения и пересечения всех квази-клик отличается много меньше. Это свидетельствует о том, что множество, представляющее объединение всех найденных квази-клик, само является или входит в квази-клику меньшей плотности.

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

Таблица 7. Вхождения доминирующих акции рынка в различные множества (корр. 0.5).

Код акции	Название компании	Количество вхождений в пересечение максимальных квази-клик с плотностью 0.92	Количество вхождений в объединение максимальных квази-клик с плотностью 0.92	Количество вхождений в объединение максимальных клик[19]
SBER	Сбербанк России	11	11	11
GAZP	Газпром	11	11	11
GMKN	Норильский Никель	5	11	8
LKOH	ЛУКОЙЛ	10	11	11
ROSN	Роснефть	11	11	11
VTBR	ВТБ Банк	11	11	11
SBERP	Сбербанк России, акция привилегированная	11	11	11
SNGS	Сургутнефтегаз	11	11	11
HYDR	РусГидро	0	6	0
CHMF	Северсталь	8	11	11



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

Для качественного изучения динамики изменения мощности множества объединения максимальных квази-клик обратимся к Рисунку 2, демонстрирующему изменение размера множества объединения максимальных квази-клик за различные периоды в зависимости от выбранного порога плотности (рис. 2).

Рисунок 2. Зависимость размера множества объединения максимальных квази-клик от порогового значения плотности за различные периоды

Как видно из графика, резкое увеличение динамики размера множества для всех 11 периодов происходит при снижении порога плотности ниже отметки 90%. Это говорит о том, что при анализе сильных зависимостей в графе с применением квази-клик разумно выбирать порог плотности в интервале от 90% до 100% (при пороге корреляции 0.5). В противном случае в максимальную квази-клику могут попадать почти любые вершины графа, что наглядно демонстрирует множество объединения максимальных квази-клик, которое при пороге плотности меньше 90% близко к множеству всех вершин графа.

фондовый рынок экономический финансовый



Заключение

Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска максимальных квази-клик заданной плотности в графе рынка и практическое применение алгоритма для анализа данных фондового рынка России. Была достигнута основная цель работы: получены качественные и количественные характеристики работы алгоритма для российского рынка, которые указывают на преимущества использования релаксации клики.

Для этого была изучена необходимая теоретическая база, рассмотрены алгоритмы поиска плотных подграфов в графе, разработана модификация "жадного" алгоритма для поиска квази-клик в графе. Алгоритм продемонстрировал хорошие результаты работы и был применен к данным о фондовом рынке России. Была разработана программа на языке Java, позволяющая обрабатывать входные данные в виде CSV-файла и получать выходные данные в структурированном виде. Анализ рынка с применением квази-клики показал оправданность применения инструмента. На основе тестовых данных для Российского рынка и представленных 177 акций было выяснено, что значение плотности равное 0.92 является наиболее удобным пороговым значением. Детальное рассмотрение динамики размера множества объединения максимальных квази-клик показало, что разумно выбирать пороговое значение плотности в интервале от 90% до 100%.

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



Список литературы

1. Abello J., Pardalos P. M., Resende M. G. C. On maximum clique problems in very large graphs //AT&T labs Research Technical Report: TR98. - 1998. - Т. 32.

2. Allen F., Babus A. Networks in finance. - 2008.

3. Balaji S., Swaminathan V., Kannan K. A simple algorithm to optimize maximum independent set //Advanced Modeling and Optimization. - 2010. - Т. 12. - №. 1. - С. 107-118.

4. Bautin G. A., Kalyagin V.A., Koldanov A.P., Koldanov P., Pardalos P.M.. Simple measure of similarity for the market graph construction //Computational Management Science. - 2013. - Т. 10. - №. 2-3. - С. 105-124.

5. Boginski V., Butenko S., Pardalos P. M. On structural properties of the market graph //Innovations in financial and economic networks. - 2003. - С. 29-45.