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

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

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

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

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

Похожие статьи




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

Предыдущая | Следующая