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

Как и для поиска клик существуют алгоритмы поиска квази-клик в графе. Далее мы рассмотрим некоторые из них. Как было сказано ранее, задача поиска максимальной клики в графе является 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).

алгоритм grasp [1]

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

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

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

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




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

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