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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

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

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

Магистерская диссертация

Алгоритмы нахождения плотных подграфов в финансовых сетях

по направлению подготовки 01.04.02 Прикладная математика и информатика

образовательная программа «Интеллектуальный анализ данных»

Кондратьев Никита Сергеевич

Рецензент д.ф.-м.н., профессор кафедры ПМИ А.П. Колданов

Научный руководитель к.ф.-м.н., ст.преподаватель кафедры ПМИ

Е.К. Бацына

Нижний Новгород 2018



• Содержание
• Введение
• Глава 1. Плотные подграфы
• 1.1 Основные определения
• 1.2 Классификация моделей релаксации клики
• Глава 2. Алгоритмы нахождения плотных подграфов
• 2.1 Алгоритмы поиска клик
• 2.1.1 Bron and Kerbosh
• 2.1.2 Carraghan and Pardalos
• 2.1.3 San Segundo, Lopez and Pardalos
• 2.2 Алгоритмы поиска релаксаций клик
• 2.2.1 Quick
• 2.2.2 Degree Decomposition Algorithm
• 2.2.3 GRASP алгоритм для поиска квази-клик
• 2.2.4 Поиск k-ядер
• Глава 3. Применение теории графов для описания фондового рынка
• 3.1 Финансовые сети
• 3.1.1 Граф рынка. Корреляция Пирсона
• 3.1.2 Граф рынка. Одновременная доходность акций, с учетом инфляции
• 3.2 Построение графа рынка
• 3.3 Реализация алгоритмов и их сравнение
• 3.3.1 Оригинальная задача ЦП для поиска максимальной г-квази-клики
• 3.3.2 Degree Decomposition Algorithm
• 3.3.3 Модифицированный Degree Decomposition Algorithm
• 3.3.4 DDA для поиска всех максимальных квази-клик
• 3.3.5 GRASP алгоритм поиска квази-клик
• 3.3.6 Сравнение времени работы реализованных алгоритмов
• 3.4 Анализ полученных квази-клик
• 3.4.1 Размеры квази-клик
• 3.4.2 Состав квази-клик
• Заключение
• Список литературы
• Приложения


Введение

релаксация клик подграф алгоритм

Графы зарекомендовали себя как удобный инструмент для моделирования объектов разной природы, например таких, как: интернет, социальные сети, телекоммуникации, клеточные процессы и другие [7]. В частности, сети нашли широкое применение в моделировании фондовых рынков [1][2][3][4][5][6][8]. Фондовые рынки ежедневно генерируют огромные массивы данных, которые могут быть использованы для построения графа рынка. Поиск плотных подмножеств является наиболее интересной задачей, которую можно поставить при моделировании графа рынка.

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

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

Данная работа посвящена исследованию алгоритмов нахождения плотных подграфов и их применению в анализе финансовых сетей.

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

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

· изучить различные формулировки плотных подграфов;

· изучить различные алгоритмы поиска плотных подграфов;

· реализовать изученные алгоритмы и применить их к финансовым сетям;

· проанализировать результаты работ алгоритмов, произвести их сравнение и произвести анализ реальных данных с фондовых рынков России и США.

Работа носит исследовательский характер. Объектом исследования является рынок ценных бумаг. Предметом исследования являются алгоритмы поиска плотных подграфов.



Глава 1. Плотные подграфы

Существует множество различных определений плотных подграфов, в данной работе упор сделан на «локальные» плотные подграфы - это плотные подграфы, которые могут рассматриваться как автономные сущности вне их окружения. Все они могут быть рассмотрены как релаксации идеально плотного подграфа - клики. Клика - это подграф, имеющий максимально возможное число ребер. В работе Patillo et al.[28] представлена классификация определений плотных подграфов. Далее мною будут приведены различные определения плотных подмножеств, разделенные на категории по их важным свойствам. Понимание этих свойств очень важно в принятии решения, какое из определений плотного компонента применять для решения конкретной задачи.

1.1 Основные определения

Для дальнейшего описания различных плотных подграфов, необходимо ввести основные определения.

Пусть G(V, E) - граф, состоящий из |V| вершин и |E| ребер. Если граф является взвешенным, тогда w(u) - вес ребра u. Невзвешенный граф можно рассматривать как частный случай взвешенного графа, каждое ребро которого имеет вес равный 1. Пусть S и T - подмножества V. Для неориентированного графа, E(S) - множество ребер, принадлежащих подграфу S:

Тогда H_S - подграф, состоящий из вершин S и ребер E(S). E(S, T) - множество ребер из S в T, H_ST - полученный подграф (S, T, E(S, T)). Стоит заметить, что подграфы S и T не обязаны быть несвязными. Если S ? T = ?, то H_ST - двудольный граф, иначе даже возможно условие, когда S = T = V.

Плотный компонент - подграф, удовлетворяющий установленному ограничению плотности. Компонент H_S является максимальным по включению, если ни один другой подграф графа G, являющийся надмножеством H_S, удовлетворяет ограничению плотности. Ниже представлены базовые определения, которые будут использованы в определении метрик плотности:

· G(V, E) - граф, состоящий из множества вершин V и множества ребер E;

· H_S - подграф, состоящий из множества вершин S и множества ребер E(S);

· H_S,T - подграф, состоящий из множества вершин S ? T и множества ребер E(S, T);

· w(u) - вес ребра u;

· N_G(u) - соседние вершины вершины u в графе G: ;

· N_S(u) - соседние вершины вершины u в графе H_S: ;

· д_G(u) - (взвешенная) степень вершины u в графе G: ;

· д_S(u) - (взвешенная) степень вершины u в графе H_S: ;

· d_G(u, v) - кратчайший (взвешенный) путь из вершины u в вершину v в графе G;

· d_S(u, v) - кратчайший (взвешенный) путь из вершины u в вершину v в графе H_S.

Таким образом, плотность подграфа H_S формально можно определить как отношение суммы весов ребер E(S) к числу всех возможных ребер между вершинами из S. Если граф невзвешенный, то сумма весов ребер равна количеству ребер в подграфе H_S, и максимальная плотность равна 1. Если же граф взвешенный, то максимальная плотность не имеет ограничения. Количество всех возможных ребер в неориентированном графе размера n:

Формула плотности для неориентированного невзвешенного графа:

Формула плотности для неориентированного взвешенного графа:

Формула плотности для ориентированного невзвешенного графа:

Формула плотности для ориентированного взвешенного графа:

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

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

Таблица 1 Определения плотных подграфов

Название	Определение	Описание
Клика		Каждая вершина связана с любой другой вершиной из S.
Квази-клика (ограничение по плотности)		S содержит как минимум г|S|(|S| - 1)/2 ребер.
Квази-клика (ограничение по степени вершин)		Каждая вершина имеет как минимум г инцидентных ребер, по отношению к максимальному числу связей.
K-core		Каждая вершина соединена как минимум с k другими вершинами.
K-plex		У каждой вершины отсутстует не более, чем k-1 ребро к ее «соседям».
Kd-клика		Кратчайший путь из любой вершины в любую другую вершину не больше, чем k. Путь может проходить через вершины, не принадлежащие S.
K-club		Кратчайший путь из любой вершины в любую другую вершину не больше, чем k. Путь не может проходить через вершины, не принадлежащие S.
s-defective клика		S содержит как минимум ребер.



1.2 Классификация моделей релаксации клики

В работе Patillo et al.[28] отмечено, что такие свойства графа, как степень вершины, расстояние, диаметр, плотность, связность и доминирующие множества, могут быть использованы для введения различных эквивалентных определений клики. Например, подмножество вершин S из графа G является кликой тогда, и только тогда, когда выполняется любое из следующих условий:

·

·

·

·

·

·

Из условий, описанных выше, видно, что для определения клики, достаточно наложить ограничение на какое-либо свойство подграфа. В таблице ниже (Табл. 2) представлены ограничения на свойства подграфа, образующего клику:

Таблица 2 Определения клики

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

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

Все релаксации клики можно разделить на два класса:

· абсолютные;

· относительные.

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

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



Глава 2. Алгоритмы нахождения плотных подграфов

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

· алгоритмы, выполняющие поиск клик;

· алгоритмы, выполняющие поиск релаксаций клик.

2.1 Алгоритмы поиска клик

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

2.1.1 Bron and Kerbosh

Перебор всех возможных подмножеств - задача, которая может занять очень много времени. Задача поиска максимальной клики является NP-сложной задачей [14]. Moon и Moser показали [15], что любой граф может содержать до 3^n/3 максимальных клик. Поэтому даже для графов небольшого размера важно найти наиболее эффективным алгоритм.

Один из первых популярных алгоритмов поиска максимальных клик, использующий перебор, был разработан Bron и Kerbosh [16] в 1973 году. Данный алгоритм использует метод ветвей и границ. Основная идея: расширять плотный подграф до тех пор, пока клика не станет максимальной по включению, путем добавления вершин из «списка кандидатов», но при этом не входящих в «список исключений». Ниже представлен псевдо-код алгоритма:



BronAndKerboshCliqueFind(C, Cand, NCand)

if Cand = ? and NCand = ? then

вывести клику, состоящую из вершин C

else

for all do

Cand < Cand \ { v_i };

call BronAndKerboshCliqueFind(C?{v_i},Cand?N(v_i),NCand?N(v_i));

Ncand < NCand ? {v_i};

end for

end if

Авторы экспериментальным путем получили временную сложность алгоритма O(3.14ⁿ), но не смогли доказать этого теоретически.

Makino et al. [17] предложили новый алгоритм, использующий эффективное умножение матриц для перебора всех максимальных клик в обычном графе, или биклик в двудольном графе. Они разработали разные алгоритмы для графов разных видов (обычный граф, двудольный граф, плотный и разреженный граф). В частности, особенно хорошую производительность данный алгоритм показывает на разреженных графах.

2.1.2 Carraghan and Pardalos

В 1990 году был представлен новый алгоритм поиска максимальной клики, который превосходил в скорости работы все известные на тот момент алгоритмы [32].

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

Ключевым понятием в данном алгоритме является понятие глубины. Предположим, что рассматривается вершина . Тогда к глубине 2 относятся все вершины, связанные с вершиной . К глубине 3 относятся все вершины с глубины 2, связанные с первой вершиной из глубины 2. Пусть - текущая рассматриваемая вершина на глубине d и шаге i. Тогда глубина d:

Если выполняется условие , где CBC - текущая лучшая клика, то поиск максимальной клики для текущей рассматриваемой вершины завершается. Если данное условие выполнилось на глубине 1, то алгоритм завершает свою работу, так как была найдена максимальная клика.

2.1.3 San Segundo, Lopez and Pardalos

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

Алгоритм имеет 2 стадии работы: стадия предобработки исходного графа, которая позволяет эффективно уменьшить размерность задачи за полиномиальное время, и стадия поиска решения, которая работает рекурсивно и за экспоненциальное время.

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

Ниже представлен псевдо-код алгоритма:

BBMCSP(G)

1. Вычислить k-ядра K(V)

2.

3.

4. Отсортировать вершины V' по возрастанию ядерного числа

5. while |V'| > 0 do

a.

b.

c.

6. end

7. return S_max

Псевдо-код процедуры INITIAL_SEARCH:

INITIAL_SEARCH(G, v)

1.

2. if |U_v| < |S_max| return

3. col = размер жадной последовательной раскраски U_v

4. if col < |S_max| return

5.

6. Вычислить k-ядра K(W)

7. if K(W) < |S_max| return

8.

9.

10.

11.



2.2 Алгоритмы поиска релаксаций клик

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

2.2.1 Quick

Задача поиска максимальных квази-клик с ограничением на степень вершин является NP-полной [29]. Для эффективного решения данной задачи, был предложен Quick алгоритм [12]. На вход данного алгоритма, помимо исследуемого графа, даются следующие параметры:

· min_size - минимальный размер (кол-во вершин) квази-клики,

· г - относительная плотность квази-клики.

На основе последнего параметра, на степень каждой вершины потенциального решения накладывается следующее ограничение:

Алгоритм Quick использует некоторые техники отбрасывания вершин, основанные на ограничениях на степень и поиске в глубину. Более того, эти техники могут быть использованы и в других алгоритмах, целью которых является поиск максимальных квази-клик.

Далее будут рассмотрены приведенные техники. Пусть - множество вершин, которые находятся на расстоянии k от вершины v, - количество вершин из X, связанных с вершиной u, и - количество вершин из cand_exts(X), связанные с вершиной u. Все вершины отсортированы в лексикографическом порядке и cand_exts(X) - множество вершин, которое начинается после последней вершины множества X, которые могут быть использованы для расширения множества X. Для того, чтобы сократить число рассматриваемых вершин, вершины, которые не входят в , могут быть удалены из cand_exts(X). Также учитывая ограничение на размер квази-клики, вершины, степень которых меньше, чем тоже могут быть удалены.

Помимо этого, авторы статьи разработали новые техники, позволяющие сокращать пространство поиска.

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

Пусть - минимальная степень вершины из X. Тогда верхняя граница определяется следующим образом:

Полученную верхнюю границу можно использовать для уменьшения пространства поиска следующим образом:

1) Пусть дано множество вершин X и вершина u из множества вершин-кандидатов на расширение. Если выполняется условие, то не существует такого надмножества Y над X, что и подграф с вершинами Y - квази-клика.

2) Пусть дано множество вершин X и вершина u, из множества X. Если выполняется условие , то не существует такого надмножества Y над X, что и подграф с вершинами Y - квази-клика.

Таким образом, можно заранее отбросить подмножества, которые невозможно расширить до квази-клики.

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

Как и в случае с верхней границей, нижняя граница может быть также улучшена:

Полученную нижнюю границу можно использовать для уменьшения пространства поиска следующим образом:

1) Пусть дано множество вершин X и вершина u из множества вершин-кандидатов на расширение. Если выполняется условие, то не существует такого надмножества Y над X, что и подграф с вершинами Y - квази-клика.

2) Пусть дано множество вершин X и вершина u, из множества X. Если выполняется условие , то не существует такого надмножества Y над X, что и подграф с вершинами Y - квази-клика.

Третья техника основывается на поиске критических вершин в множетсве X. Вершина v является критической вершиной множества X, если выполняется условие .

Если такая вершина из множества X существует, то в него сразу добавляются вершины из множества вершин-кадидатов на расширение, которые связаны с критической вершиной. Данная техника позволяет быстрее найти квази-клику.

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

Ниже представлен псевдо-код алгоритма Quick:

Quick(X, cand_exts(X), г, min_size)

· найти критическую вершину u из X и отсортировать вершины в cand_exts(X);

· for all do

o проверить ограничение на размер квази-клики на |X| + |cand_exts(X)|;

o применить технику «предсказание»;

o удалить вершины, которые не входят в

o

o посчитать верхнюю и нижнюю границу на количество вершин, которые будут добавлены к Y;

o рекурсивно удалить неподходящие вершины (используя верхнюю и нижнюю границу);

o применить технику, основанную на поиске критических вершин множества Y;

o рекурсивно применить функцию Quick к полученному множеству Y и множеству кандидатов на его расширение;

· end for

· return г-quasi-cliques;

2.2.2 Degree Decomposition Algorithm

В работе Pastukhov G. et al. [29] был представлен алгоритм поиска максимальных по включению г-квази-клик с ограничением по степени вершин. В основе данного алгоритма лежит следующее наблюдение: если степень каждой вершины в подграфе S графа G не меньше заданного числа k, то подграф S является k-ядром и выполняется следующее неравенство:

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

На основе данного наблюдения, авторы статьи предлагают использовать вместо оригинальной формулировки задачи целочисленного программирования для поиска максимальной г-квази-клики набор моделей г-QC(k), где , V - множество вершин исходного графа.

Оригинальная формулировка задачи нахождения максимальной г-квази-клики как задачи целочисленного программирования г-QC:

Целевая функция:

Ограничения:

Переменные равны 1 тогда и только тогда, когда вершина i входит в максимальную г-квази-клику. Константа должна иметь достаточно большое значение, например, . Ограничение (1a) гарантирует выполнение требования на минимальную степень входящих в решение вершин.

Далее будет приведена формулировка модели г-QC(k), набор которых решает приведенную выше оригинальную модель.

Модель г-QC(k) имеет следующую целевую функцию:

И следующий набор ограничений:

Ограничение (2a) гарантирует, что найденный подграф является k-ядром, в то время как, ограничение (2b) гарантирует, что размер найденного подграфа не превышает .

Таким образом, максимальная г-квази-клика может быть найдена, если решить |V| моделей г-QC(k), где , и после выбрать подграф с наибольшим количеством вершин.

На вход алгоритму Degree Decomposition Algorithm (DDA) дается граф G = (V, E) и параметр , на выходе будет максимальная г-квази-клика.

Псево-код алгоритма DDA:

· currentMax = 0

· S^* = {}

· k =

· repeat

o k = k - 1

o S_k = solve г-QC(k)

o if currentMax < |S_k| then

§ currentMax = |S_k|

§ S^* = S_k

· until

· return S^*

2.2.3 GRASP алгоритм для поиска квази-клик

Наиболее популярным алгоритмом для нахождения приблеженных решений задачи поиска максимальных квази-клик является жадный алгоритм (GRASP). Этот алгоритм зачастую находит оптимальные решения.

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



Рисунок 1 Поиск начального решения

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

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

2.2.4 Поиск k-ядер

Ядерность можно также использовать для нахождения тесно связанных множеств в графе. K-ядро - это максимальный по включению подграф, каждая вершина которого соединена по меньшей мере с k другими вершинами в подграфе.

Клика является k-1 - ядром, где k - число вершин в клике. В то же время, k-ядра, не являющиеся кликами, являются квази-кликами. Например, граф, представленный на Рисунке 1, является 2-ядром, и при этом является 0,8-квази-кликой, так как имеет плотность ребер 0,83.

Рисунок 2 Пример k-ядра

Минимальная плотность k-ядра находится по следующей формуле:

где n - количество вершин в k-ядре. Таким образом, плотность ребер любого k-ядра лежит в интервале от den_min до 1, и если плотность k-ядра меньше, чем г, то найденное k-ядро является г-квази-кликой.

В статье Batagelj et al. [18] приведен алгоритм, временная сложность которого составляет O(m), где m - число ребер в графе. Алгоритм достаточно прост и заключается в следующем: пусть дан граф G = (V, E), если рекурсивно удалить все вершины и инцидентные им ребра, текущая степень которых меньше заранее заданного параметра k, то полученный в итоге граф является k-ядерным.

Далее представлен псевдо-код алгоритма поиска k-ядер в графе:

FindKCores(graph G = (V, E), threshold k)

· отсортировать вершины из множества V в порядке возрастания степени;

· for each в отсортированном порядке:

o core[v] = degree[v];

o for each :

§ if degree[u] > degree[v]

· degree[u] = degree[u] - 1;

· отсортируем вершины в V, с учетом новых степеней.



Глава 3. Применение теории графов для описания фондового рынка

3.1 Финансовые сети

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

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

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

Помимо вышеперечисленных мер близости, для оценивания прибыльности фондового рынка Глотов А. и др. [25] разработали меру близости, основанную на одновременной доходности пары акции за определенный период времени, с учетом инфляции.

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

3.1.1 Граф рынка. Корреляция Пирсона

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

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

где P_i(t) - цена акции, E(R_i) показывает среднюю доходность акции i за n дней:

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

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

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

3.1.2 Граф рынка. Одновременная доходность акций, с учетом инфляции

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

где - индикатор доходности акции i за неделю t = 1, ... , N.

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

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

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

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

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

Также для сравнения работы реализованных алгоритмов были взяты данные с Yahoo Finance о торгах акций из индекса S&P 500 с 4 сентября 2012 года по 19 сентября 2016 года. Данные о торгах представлены в виде CSV-файла, который содержит информацию о дате сделки, идентификаторе акции и цены акции.

Для сбора актуальных данных о торгах был реализован скрипт на языке Python, которое через API, представленное Yahoo Finance, позволяет получить данные о торгах за заданный период времени. Программный код этого скрипта представлен в Приложении 1.

3.3 Реализация алгоритмов и их сравнение

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

· оригинальная задача ЦП для поиска максимальной г-квази-клики (ограничение на степень вершины);

· Degree Decomposition Algorithm для поиска максимальной г-квази-клики (ограничение на степень вершины);

· модифицированный Degree Decomposition Algorithm для поиска максимальной г-квази-клики (ограничение на степень вершины);

· GRASP-алгоритм поиска квази-клик в графе (ограничение на плотность подграфа).

Реализация алгоритма Quick находится в открытом доступе [30] и была взята оттуда.

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

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

· ориентированный и неориентированный графы;

· взвешенный и невзвешенный графы;

· подграфы.

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

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

Задачи целочисленного программирования решались с помощью IBM ILOG CPLEX [31], который является одним из лучших инструментов для решения задач линейного программирования, и имеет интерфейс для вызова из программ, написанных на языке Java.

3.3.1 Оригинальная задача ЦП для поиска максимальной г-квази-клики

Формулировка задачи поиска максимальной г-квази-клики с ограничением на степень вершины представлена в главе 2.2.2.

Алгоритм на вход получает неориентированный невзвешенный граф, строит для него задачу целочисленного программирования, которая решается в IBM ILOG CPLEX. Если оптимальное решение было найдено, то возвращается найденный подграф.

Исходный код алгоритма:

public static <V, E> AsSubgraph solve(Graph<V, E> graph, double gamma) throws IloException {

IloCplex cplex = new IloCplex();

cplex.setOut(null);

int vertexCount = graph.vertexSet().size();

// Add variables

IloIntVar[] vars = cplex.intVarArray(vertexCount, 0, 1);

IloNumVar[] numVars = cplex.numVarArray(vertexCount, 0.0, 1.0);

double mu = gamma * (vertexCount - 1);

double rcv = -1.0 * (mu + gamma);

ArrayList<V> vertexToIndex = new ArrayList<>(vertexCount);

Integer i = 0;

for (V vertex : graph.vertexSet()) {

vertexToIndex.add(i, vertex);

cplex.addEq(vars[i], numVars[i]);

i++;

}

// Set up objective

IloIntVar objVal = cplex.intVar(0, Integer.MAX_VALUE);

IloNumVar objValNum = cplex.numVar(0, Double.MAX_VALUE);

cplex.addEq(objVal, cplex.sum(vars));

cplex.addEq(objVal, objValNum);

cplex.addMaximize(objVal);

// Set up constraints

for (i = 0; i < vertexCount; i++) {

V vertex = vertexToIndex.get(i);

List<V> neighbours = Graphs.neighborListOf(graph, vertex);

IloNumVar[] vVars = new IloNumVar[neighbours.size() + 2];

double[] coefficients = new double[neighbours.size() + 2];

for (int j = 0; j < neighbours.size(); j++) {

int nIndex = vertexToIndex.indexOf(neighbours.get(j));

vVars[j] = numVars[nIndex];

coefficients[j] = 1.0;

}

// Add -mu * xi

vVars[neighbours.size()] = numVars[i];

coefficients[neighbours.size()] = -1.0 * mu;

// Add -gamma*obj

vVars[neighbours.size() + 1] = objValNum;

coefficients[neighbours.size() + 1] = -1.0 * gamma;

cplex.addGe(cplex.scalProd(vVars, coefficients), rcv);

}

cplex.solve();

if (!cplex.getStatus().equals(IloCplex.Status.Optimal)) {

Debug.log("No optimal solution found");

cplex.end();

return null;

}

int finalObjValue = (int) cplex.getObjValue();

Debug.log("Final obj value = " + finalObjValue);

if (finalObjValue > 0) {

Set<V> subGraphVertices = new TreeSet<>();

for (i = 0; i < vertexCount; i++) {

double varValue = cplex.getValue(vars[i]);

// Variable value can be near 1.0, e.g. 0.999999999999 or 1.000000000016

if (varValue > 1.0 - EPS && varValue < 1.0 + EPS) {

subGraphVertices.add(vertexToIndex.get(i));

}

}

cplex.end();

return new AsSubgraph<>(graph, subGraphVertices);

}

cplex.end();

return null;

}

3.3.2 Degree Decomposition Algorithm

Данный алгоритм описан в главе 2.2.2.

Исходный код алгоритма:

public static <V, E> AsSubgraph solve(Graph<V, E> graph, double gamma) throws IloException {

Coreness<V, E> gCoreness = new Coreness<>(graph);

int degeneracy = gCoreness.getDegeneracy();

int currentMax = 0;

AsSubgraph<V, E> result = null;

int k = degeneracy + 1;

Debug.log("Initial k = " + k);

do {

k--;

Debug.log("Solve gamma-QC(k) for k = " + k);

AsSubgraph solution = solveYQCk(graph, gamma, k);

int solutionVerticesCount = 0;

if (solution != null) {

Debug.log("Founded solution: " + solution.toString());

solutionVerticesCount = solution.vertexSet().size();

Debug.log("Current max = " + currentMax + ", solution size = " + solutionVerticesCount);

} else {

Debug.log("Solution not found.");

}

if (solution != null && currentMax < solutionVerticesCount) {

currentMax = solutionVerticesCount;

result = new AsSubgraph<V, E>(graph, solution.vertexSet());

}

Debug.log("Check: " + currentMax + " < " + String.valueOf(Math.floor(k / gamma) + 1));

} while (currentMax < (int) Math.floor(k / gamma) + 1);

return result;

}

Исходный код функции, решающей задачу г-QC(k):

protected static <V, E> AsSubgraph solveYQCk(Graph<V, E> graph, double gamma, int k) throws IloException {

IloCplex cplex = new IloCplex();

cplex.setOut(null);

int vertexCount = graph.vertexSet().size();

ArrayList<V> vertexToIndex = new ArrayList<>(vertexCount);

Integer i = 0;

String[] varNames = new String[vertexCount];

for (V vertex : graph.vertexSet()) {

vertexToIndex.add(i, vertex);

varNames[i] = "x" + vertex.toString();

i++;

}

// Add variables

IloIntVar[] vars = cplex.intVarArray(vertexCount, 0, 1, varNames);

// Set up objective

IloIntVar objVal = cplex.intVar(0, Integer.MAX_VALUE, "objVal");

cplex.addEq(objVal, cplex.sum(vars), "objFun");

cplex.addMaximize(objVal);

// Set up constraints

for (i = 0; i < vertexCount; i++) {

V vertex = vertexToIndex.get(i);

List<V> neighbours = Graphs.neighborListOf(graph, vertex);

IloNumVar[] vVars = new IloNumVar[neighbours.size()];

for (int j = 0; j < neighbours.size(); j++) {

int nIndex = vertexToIndex.indexOf(neighbours.get(j));

vVars[j] = vars[nIndex];

}

cplex.addGe(cplex.sum(vVars), cplex.prod(k, vars[i]), "deg_x" + vars[i].getName());

}

// Add size constraint

int sizeC = (int) (Math.floor(k / gamma) + 1);

cplex.addLe(cplex.sum(vars), sizeC, "sizeConstraint");

cplex.solve();

Debug.log("CPLEX status: " + cplex.getStatus());

if (!cplex.getStatus().equals(IloCplex.Status.Optimal)) {

Debug.log("No optimal solution found");

cplex.end();

return null;

}

int finalObjValue = (int) cplex.getObjValue();

Debug.log("Final obj value = " + finalObjValue);

if (Debug.isDebug()) {

for (i = 0; i < vertexCount; i++) {

System.out.print(String.valueOf(i) + " = " + cplex.getValue(vars[i]));

if (i < vertexCount - 1) {

System.out.print(", ");

}

}

System.out.println(" ");

}

if (finalObjValue > 0) {

Set<V> subGraphVertices = new TreeSet<>();

for (i = 0; i < vertexCount; i++) {

double varValue = cplex.getValue(vars[i]);

// Variable value can be near 1.0, e.g. 0.999999999999 or 1.000000000016

if (varValue > 1.0 - EPS && varValue < 1.0 + EPS) {

subGraphVertices.add(vertexToIndex.get(i));

}

}

cplex.end();

return new AsSubgraph<>(graph, subGraphVertices);

}

cplex.end();

return null;

}

3.3.3 Модифицированный Degree Decomposition Algorithm

В работе Pastukhov G. et al. [29] также был представлен простой эвристический алгоритм для поиска г-квази-клик, который авторы статьи использовали для быстрого поиска допустимого решения, которое они потом использовали в предложенном алгортиме, основанном на методе ветвей и границ. На вход эвристическому алгоритму подается граф и г, на выходе будет найденная г-квази-клика.

Псевдо-код эвристического алгоритма:

·

· while do

o

o

o

· end

· return V

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

· S^* = heuristicYQC(G, г)

· currentMax = |S^*|

· k =

· while

o k = k - 1

o S_k = solve г-QC(k)

o if currentMax < |S_k| then

§ currentMax = |S_k|

§ S^* = S_k

· end

· return S^*

Таким образом, если эвристика изначально найдет оптимальное решение, то алгоритм может раньше завершить работу с выполненным условием остановки.

Исходный код эвристического алгоритма:

public static <V, E> AsSubgraph<V, E> solve(Graph<V, E> graph, double gamma) {

AsSubgraph<V, E> result = new AsSubgraph<>(graph, graph.vertexSet());

VertexDegreeComparator<V, E> vertexDegreeComparator = new VertexDegreeComparator<>(result);

V minDegVertex = result.vertexSet()

.stream()

.min((v1, v2) -> vertexDegreeComparator.compare(v1, v2))

.get();

while ((double) result.degreeOf(minDegVertex) < gamma * (result.vertexSet().size() - 1)) {

result.removeVertex(minDegVertex);

minDegVertex = result.vertexSet()

.stream()

.min((v1, v2) -> vertexDegreeComparator.compare(v1, v2))

.get();

}

return result;

}

Исходный код модифицированного DDA алгоритма:

public static <V, E> AsSubgraph solve(Graph<V, E> graph, double gamma) throws IloException {

Coreness<V, E> gCoreness = new Coreness<>(graph);

int degeneracy = gCoreness.getDegeneracy();

AsSubgraph<V, E> result = HeuristicYQC.solve(graph, gamma);

int currentMax = result.vertexSet().size();

int k = degeneracy + 1;

Debug.log("Initial k = " + k);

while (currentMax < (int) Math.floor(k / gamma) + 1) {

k--;

Debug.log("Solve gamma-QC(k) for k = " + k);

AsSubgraph solution = solveYQCk(graph, gamma, k);

int solutionVerticesCount = 0;

if (solution != null) {

Debug.log("Founded solution: " + solution.toString());

solutionVerticesCount = solution.vertexSet().size();

Debug.log("Current max = " + currentMax + ", solution size = " + solutionVerticesCount);

} else {

Debug.log("Solution not found.");

}

if (solution != null && currentMax < solutionVerticesCount) {

currentMax = solutionVerticesCount;

result = new AsSubgraph<V, E>(graph, solution.vertexSet());

}

Debug.log("Check: " + currentMax + " < " + String.valueOf(Math.floor(k / gamma) + 1));

}

return result;

}

3.3.4 DDA для поиска всех максимальных квази-клик

Оригинальная версия Degree Decomposition Algorithm на выходе дает только одну максимальную квази-клику, однако в графе может быть несколько разных квази-клик, имеющих максимальный размер. Для анализа данных фондовых рынков полезнее рассматривать все максимальные квази-клики, поэтому DDA алгоритм был доработан таким образом, чтобы он возвращал все максимальные квази-клики.

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

Новая модель г-QC(k) имеет следующую целевую функцию:

И следующий набор ограничений:

Главное отличие от оригинальной модели г-QC(k) состоит в добавлении ограничений (3c), выполнение которых гарантирует, что найденное решение будет отличаться от уже известных.

Псевдо-код DDA для поиска всех максимальных квази-клик:

·

·

· repeat

o

o if then

§

§

o

· until

· return

3.3.5 GRASP алгоритм поиска квази-клик

В качестве алгоритма поиска квази-клик с ограничением на плотность найденного подграфа был выбран улучшенный «жадный» алгоритм из работы Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (C. Tsourakakis et al., 2013).

Как было определено ранее, плотность графа рассчитывается по формуле:

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

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

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

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

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

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

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

public Set<Set<V>> getQuasiCliques(double gamma, int MAX_ITERATIONS, boolean onlyBestStartV) {

...