Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России
Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска максимальной клики в графе является 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 новых, которые бы были соединены со всем вершинами из текущего решения. Данная процедура происходит до тех пор, пока есть кандидаты на добавление.
С точки зрения применения "жадного" алгоритма для поиска квази-клик появляется существенное различие: мы не можем использовать поиск вершины максимальной степени в момент перехода от клики к квази-клике. Это обусловлено тем, что квази-клика является разреженной кликой, и вершина, входящая в решение, не всегда может иметь степень равную количеству вершин в решении, то есть не может быть связана со всеми остальными вершинами решения. Для решения этой проблемы авторы предлагают модифицировать процедуру локального поиска, чтобы позволить ей добавлять в решение вершины с использованием релаксации степени, то есть допуская снижение плотности клик.
Похожие статьи
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Заключение - Использование квази-клик для анализа графа рынка России
Данная выпускная работа была посвящена проблеме поиска плотных подграфов в графе. Основные усилия в ней были направлены на разработку алгоритма поиска...
-
Введение - Использование квази-клик для анализа графа рынка России
Графы, состоящие из вершин и ребер, представляют удобный инструмент моделирования для изучения различных сетевых структур, в том числе, социальных сетей,...
-
В статье Network approach for the Russian stock market авторы анализируют данные фондового рынка для России, в том числе используют поиск максимальной...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Понятие и применение графа рынка - Использование квази-клик для анализа графа рынка России
Динамика характеристик отражающих тенденцию поведения фондового рынка может быть интересна многим участникам фондовой биржи и, в особенности, инвесторам....
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Нахождение квази-клик за заданный период - Использование квази-клик для анализа графа рынка России
К полученному графу рынка мы можем применить алгоритм поиска максимальной квази-клики в графе. Поэтому, для целей практического применения, возникла...
-
Построение графа рынка России - Использование квази-клик для анализа графа рынка России
Для начала работы с алгоритмической частью требуется построить граф рынка. Для того, чтобы проанализировать правильность подхода с применением...
-
Анализ полученных квази-клик - Использование квази-клик для анализа графа рынка России
Как было замечено в статье Network approach for the Russian stock market, для российского рынка наиболее ценные акции имеют сильные связи между их...
-
Экономические и финансовые сети На протяжении долгих лет глобализация ведет к увеличению зависимости различных организаций друг от друга. Правительства,...
-
Данные о Российском рынке - Использование квази-клик для анализа графа рынка России
История рынка ценных бумаг берет свое начало еще в XV веке, когда государства для привлечения дополнительных денежных средств начали выпускать и...
-
Адсорбционные явления чрезвычайно широко распространены в живой и неживой природе. Толщи горных пород и почвы являются огромными колоннами с...
-
Адсорбционные методы исследования свойств поверхности позволяют количественно охарактеризовать происходящие при адсорбции межмолекулярные взаимодействия,...
-
Выводы - Использование нейродинамики для моделирования производственных процессов предприятия
Исходя из вышеизложенного, можно заключить, что для решения задач прогнозирования наиболее подходит сеть с обратным распространением. Она позволяет...
-
Программное управление Относительно просто может быть сформулирована так называемая задача программного управления. В ней предполагается, что управляющие...
-
Алгоритм использует в качестве исходных данных документы, содержащие следующие сведения: X A, k,j, i - измеряемые показатели научной работы; X A, TG,...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Следует отметить, что не существует особых сил, вызывающих адсорбцию. Адсорбция молекул на поверхности твердого тела происходит за счет сил притяжения со...
-
Пример успешного использования методов многошагового обучения для задачи управления производством. Рассмотрим простейший вариант, когда производится лишь...
-
Табличное представление цен действий и состояний задачи имеет естественные ограничения по масштабируемости задачи на большую размерность. В дискретных...
-
Комментарии к третьему разделу курсовой работы В третьем разделе курсовой работы студенту предлагается определить оптимальную стратегию заказа в условиях...
-
Среди различных конфигураций искусственных нейронных сетей встречаются такие, при классификации которых по принципу обучения, строго говоря, не подходят...
-
Программное управление является приемлемым подходом во многих прикладных ситуациях. На этом принципе основаны, например, простые металлорежущие станки...
-
Возьмем данные об инвестициях в основной капитал (млрд. руб.) Год Квартал Номер квартала Значение 2003 I 1 330 II 2 470,4 III 3 608,8 IV 4 773,7 2004 I 5...
-
Знаменитая теория полимолекулярной адсорбции Брунауэра, Эммета и Теллера, получившая название теории БЭТ (по первым буквам фамилий ученых), основана на...
-
Предметом статьи является обоснование необходимости использования математических методов в процессе внутреннего мониторинга операций организациями с...
-
Спецификация модели Почти каждая компонента динамической части модели потребует комментариев, поэтому для каждой компоненты модели будет отведен...
-
Данная глава будет посвящена анализу кассовых сборов фильмов. В начале главы приводится краткая методическая справка об основном статистическом методе,...
-
В нашем анализе данных показателей рынков под "самородками" понимаются зависимости, отражающие степень эффективности рекламных кампаний. Эксперты часами...
-
Применим аппарат. Результаты приведены ниже Таблица 6. индексный анализ Рисунок 4. График сглаженного признака Полиномиальная регрессия Приведем массив...
-
Адсорбция активированный уголь Развитие теории адсорбционных сил еще не достигло такой стадии, когда по известным физико-химическим свойствам газа и...
-
Попытаемся дать общее представление о свойствах и применении адсорбентов на примере весьма распространенных углеродных материалов. Углеродные адсорбенты...
-
Многие растворители могут быть использованы в ESI и выбираются в зависимости от растворимости исследуемых соединений, летучести растворителя и...
-
Описание процессов, происходящих на поверхности, изобилует специальными терминами, и при рассмотрении адсорбционных явлений приходится говорить на языке,...
-
Топологический элементный анализ - Системная революция и принцип дуального управления
Независимые от системы элементы формально выглядят как изолированные вершины графа структуры (ее симплекса). Если некоторый элемент на всех структурах...
-
Итак, в первых двух разделах курсовой работы мы использовали модуль Excel "Поиск решении" для решения задачи общего линейного программирования (1 раздел)...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
Алгоритмы поиска квази-клики в графе. - Использование квази-клик для анализа графа рынка России