Алгоритмы поиска плотных подграфов в графе, о клике. - Использование квази-клик для анализа графа рынка России
О клике.
Определим формально задачу поиска максимальной клики, согласно статьи 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]. С точки зрения рассмотрения графа фондового рынка переход к квази-кликам можно мотивировать тем, что наборы коррелирующих акций могут отличаться между исследуемыми периодами, а также внутри одного периода, в то время как объединение клик может представлять более правдивую картину рынка. Таким образом, существует мнение, что использование квази-клик может дать лучшие результаты для исследуемых промежутков времени.
Похожие статьи
-
Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России
Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Введение - Использование квази-клик для анализа графа рынка России
Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей,...
-
Заключение - Использование квази-клик для анализа графа рынка России
Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска...
-
В статье Network approach for the Russian stock market авторы анализируют данные фондового рынка для России, в том числе используют поиск максимальной...
-
Анализ полученных квази-клик - Использование квази-клик для анализа графа рынка России
Как было замечено в статье Network approach for the Russian stock market, для российского рынка наиболее ценные акции имеют сильные связи между их...
-
Построение графа рынка России - Использование квази-клик для анализа графа рынка России
Для начала работы с алгоритмической частью требуется построить граф рынка. Для того, чтобы проанализировать правильность подхода с применением...
-
Понятие и применение графа рынка - Использование квази-клик для анализа графа рынка России
Динамика характеристик отражающих тенденцию поведения фондового рынка может быть интересна многим участникам фондовой биржи и, в особенности, инвесторам....
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
Экономические и финансовые сети На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства,...
-
Данные о Российском рынке - Использование квази-клик для анализа графа рынка России
История рынка ценных бумаг берет свое начало еще в XV веке, когда государства для привлечения дополнительных денежных средств начали выпускать и...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
В нашем анализе данных показателей рынков под "самородками" понимаются зависимости, отражающие степень эффективности рекламных кампаний. Эксперты часами...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Знаменитая теория полимолекулярной адсорбции Брунауэра, Эммета и Теллера, получившая название теории БЭТ (по первым буквам фамилий ученых), основана на...
-
Выводы - Использование нейродинамики для моделирования производственных процессов предприятия
Исходя из вышеизложенного, можно заключить, что для решения задач прогнозирования наиболее подходит сеть с обратным распространением. Она позволяет...
-
Программное управление Относительно просто может быть сформулирована так называемая задача программного управления. В ней предполагается, что управляющие...
-
Адсорбционные методы исследования свойств поверхности позволяют количественно охарактеризовать происходящие при адсорбции межмолекулярные взаимодействия,...
-
Возьмем данные об инвестициях в основной капитал (млрд. руб.) Год Квартал Номер квартала Значение 2003 I 1 330 II 2 470,4 III 3 608,8 IV 4 773,7 2004 I 5...
-
Описание процессов, происходящих на поверхности, изобилует специальными терминами, и при рассмотрении адсорбционных явлений приходится говорить на языке,...
-
В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...
-
Топологический элементный анализ - Системная революция и принцип дуального управления
Независимые от системы элементы формально выглядят как изолированные вершины графа структуры (ее симплекса). Если некоторый элемент на всех структурах...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Возможны две различных стратегии реструктуризации сферы централизованного теплоснабжения, и, как следствие, различные методики анализа возникающих...
-
Многие растворители могут быть использованы в ESI и выбираются в зависимости от растворимости исследуемых соединений, летучести растворителя и...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
-
Предметом статьи является обоснование необходимости использования математических методов в процессе внутреннего мониторинга операций организациями с...
-
Спецификация модели Почти каждая компонента динамической части модели потребует комментариев, поэтому для каждой компоненты модели будет отведен...
-
Пример успешного использования методов многошагового обучения для задачи управления производством. Рассмотрим простейший вариант, когда производится лишь...
-
Программное управление является приемлемым подходом во многих прикладных ситуациях. На этом принципе основаны, например, простые металлорежущие станки...
-
Применим аппарат. Результаты приведены ниже Таблица 6. индексный анализ Рисунок 4. График сглаженного признака Полиномиальная регрессия Приведем массив...
-
Следует отметить, что не существует особых сил, вызывающих адсорбцию. Адсорбция молекул на поверхности твердого тела происходит за счет сил притяжения со...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
Решетки (структуры) - Формационные основы универсальных алгебр
Понятие решетки (пример 11) играет исключительно важную роль в изучении самых общих алгебр. И это, в первую очередь, связано с иным подходом в...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
Алгоритмы поиска плотных подграфов в графе, о клике. - Использование квази-клик для анализа графа рынка России