Задача нахождения максимальной клики

Задача нахождения максимальной клики

СОДЕРЖАНИЕ

Введение

.        Метод ветвей и границ для решения ЗМК

.        Алгоритм RPC

.        Модификация алгоритма

.        Обучающая выборка

.        Построение функции-классификатора

.        Вычислительные результаты

Заключение

Список использованной литературы

Приложение 1. Листинг алгоритма, основанного на методе ветвей и границ для решения ЗМК

Приложение 2. Листинг алгоритма RPC

Приложение 3. Предлагаемое изменение в алгоритме RPC

ВВЕДЕНИЕ

максимальная клика алгоритм граф

Задача нахождения максимальной клики в простом неориентированном графе G=(V, E) является классической задачей теории графов. Кликой (или полным подграфом) графа G называется такое подмножество его вершин, что любые две вершины подмножества соединены ребром. Клика, которая не содержится в клике большего размера, называется максимальной по включению. Задача нахождения максимальной клики (ЗМК) состоит в том, что для заданного графа G необходимо найти клику максимального размера (мощности).

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

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

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

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

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

1.      Метод ветвей и границ для решения ЗМК

В рамках данной работы будут рассматриваться алгоритмы, основанные на методе ветвей и границ и использующие в качестве границы вершинную раскраску рассматриваемого графа. Вершинной раскраской графа G = (V, E) называется такая функция , что  для любых двух вершин . Множество вершин, покрашенных в цвет i, будем обозначать . Следующее утверждение связывает кликовое число  (число вершин в максимальной клике графа G), с количеством цветов вершиной раскраски графа G.

Утверждение 1. Если граф G = (V, E) может быть раскрашен в k цветов, то , причем в максимальную клику входит не более одной вершины из каждого цвета.

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

Псевдокод примера алгоритма, использующего метод ветвей и границ, представлен в приложении 1.

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

Опираясь на утверждение 1, алгоритм использует проверку неравенства , как условие отсечения (приложение 1, строка 7). Другими словами, если условие выполняется, то все ветки рассматриваемой подзадачи отбрасываются, так как текущую клику невозможно увеличить. Иначе, вершина v с максимальным цветом добавляется в текущую рассматриваемую клику Q. После чего поиск макcимальной клики происходит среди вершин, соединённых с вершиной v (будем обозначать N(v)) из множества вершин U (приложение 1, строка 11).

Алгоритм продолжает работу до тех пор, пока в множестве U не остаётся вершин. После этого в переменной Q_max остаётся список вершин, входящих в максимальную клику.

2.      Алгоритм RPC

Алгоритм RPC был предложен в [2]. Его псевдокод представлен в приложении 2. Этот алгоритм основан на методе ветвей и границ, а его отличительная особенность состоит в том, что он использует не один алгоритм раскраски для всех подзадач. Для некоторых подзадач используется алгоритм жадной раскраски с перекраской, для некоторых - повторное использование родительской раскраски. Также в алгоритме RPC исходный граф проходит предобработку, состоящую из двух шагов.

Первый шаг предобработки состоит в переименовании вершин. Для уменьшения размера дерева поиска в начале работы алгоритма используется упорядочение вершин (приложение 2, строка 55). В алгоритме RPC вершины упорядочиваются по принципу, который был предложен Матулой в [3]. Сначала во всем графе G ищется вершина v с наименьшей степенью. Далее вершина v становится вершиной с номером n. После чего вершина v удаляется из графа G и в полученном графе ищется вершина с наименьшей степенью. Найденная вершина перенумеруется в (n-1)-ую вершину и процедура повторяется.

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

Далее алгоритм RPC работает по принципу, представленному в главе 1. Существенное отличие заключается в получении раскраски подзадачи.

Алгоритм принимает на вход параметр  - целое неотрицательное число. При  алгоритм RPC совпадает с алгоритмом MCS ([2]), так как для всех подзадач для вычисления верхней границы используется жадная раскраска с перекрашиванием (метод GCH_R). Подробное описание этого алгоритма можно найти в [1]. При  жадная раскраска с перекрашиванием будет применяться для некоторых подзадач, в то время как для других - повторное использование родительской раскраски (метод ROC).

Рис. 1 Повторное использование родительской раскраски

Рассмотрим применение метода ROC на следующем примере. Пусть , ,  и рассматриваемый подграф представлен на рис. 1 (слева). На рис. 1 для каждой вершины указан номер, а также цвет (в скобках). Первый шаг метода ROC состоит в повторном использовании родительской раскраски. Так как в первую очередь алгоритм RPC рассматривает вершину с наибольшим цветом то вершина 9 добавляется в текущую рассматриваемую клику Q. После чего рассматривается подграф, порожденный вершинами, смежными вершине 9. Для этого подграфа метод ROC не ищет новую раскраску, а повторно использует родительскую раскраску (приложение 2, строки 3-8). Результат повторного использования родительской раскраски представлен на рис. 1 (справа).

Рис. 2 Увеличение качества раскраски и сортировка цветов

Далее метод ROC пытается увеличить качество раскраски, то есть уменьшить количество используемых цветов (приложение 1, строки 10-27). В начале метод находит цвет, содержащий только одну вершину w. После чего вершину w пытаются перекрасить в другой цвет. В данном примере вершина 5, которая была покрашена в  цвет 1 (рис. 2), может быть перекрашена в цвет 2. После этого преобразования не осталось вершин, окрашенных в первый цвет, поэтому его можно удалить и перенумеровать цвета. Результат применения увеличения качества раскраски представлен на рис. 2 (по центру).

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

3.      Модификация алгоритма RPC

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

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

Предлагаемые изменения представлены в приложении 3. Предполагается, что уже построена функция predict(args), которая на основе параметров подзадачи возвращает номер класса, к которому принадлежит подзадача. Принадлежность подзадачи к тому или иному классу отражает, какой алгоритм раскраски лучше использовать для соответствующей подзадачи: класс 1 - жадная раскраска с перекраской, класс 2 - повторное использование родительской раскраски, класс 3 - жадная раскраска.

4.      Обучающая выборка

Подграфы, образующиеся в ходе работы алгоритма, обладают специфической конфигурацией, т.к. представляют из себя графы, из которых удалены одна или несколько вершин. Поэтому графы для обучающей выборки не генерируются классическими методами генерации графов. Вместо этого с помощью модели Эрдёша-Реньи генерируются графы, для которых запускается алгоритм RPC. Для генерации графов с помощью модели Эрдеша-Реньи необходимо задать два параметра n и p, где n - число вершин в генерируемом графе, а p - вероятность того, что любые две вершины  и  будут соединены ребром независимо от всех остальных пар вершин. В таблице 2 представлены значения параметров сгенерированных графов.

Таблица 1.

Параметры сгенерированных графов

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

1)      Если один из методов раскраски отбрасывает все дочерние ветки, а остальные - нет, то выбирается тот метод, который отбрасывает все ветки.

2)      Если ни один из методов не отбросил все ветки, выбирается тот метод, для которого количество дочерних веток подграфа минимально.

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

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

Были выбраны следующие параметры подзадачи:

) Раскраска, использованная в родительском узле

) Количество вершин в родительском узле

) Количество цветов в родительском узле

) Размер текущей клики

) Размер найденной максимальной клики

) Разница между размером найденной максимальной клики и текущей клики

5.      Построение функции-классификатора

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

Рис. 3. Распределение подзадач из обучающей выборки

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

Классификатор был построен с помощью пакета rpart среды R, и в дальнейшем интегрирован в код алгоритма RPC.

Отметим, что классификатор использовал только признаки 1, 5 и 7.

6.      Вычислительные результаты

Предлагаемый алгоритм был протестирован на графах библиотеки DIMACS. Всего было рассмотрен 21 граф из этой библиотеки, для каждого из них решалась задача поиска максимальной клики с помощью предложенного алгоритма (модифицированный RPC), и алгоритмов RPC с параметрами 0, 1, 2 и 3. Время работы каждого из алгоритмов представлено в таблице 3.

Таблица 3.

Время работы рассматриваемых алгоритмов на графах из библиотеки DIMACS.

Отметим, что предложенный алгоритм в большинстве случаев работает быстрее алгоритма, использующего только один тип раскраски (RPC, ), но в среднем медленнее, чем алгоритм RPC с другими параметрами. Однако для практического использования необходим метод выбора оптимального значения параметра для конкретного графа. Однако на данный момент этого метода не существует. Таким образом, предложенный алгоритм более пригоден для практического использования, так как показывает приемлемые результаты, но при этом не требует на вход параметр.

В рамках представленной работы была предложена модификация алгоритма RPC, использующая машинное обучение вместо использования параметра. Модифицированный алгоритм был обучен при помощи сгенерированных по модели Эрдёша-Реньи графов и испытан на образцах из библиотеки DIMACS. Предложенный алгоритм показал себя достаточно эффективным, а, учитывая отсутствие входного параметра, ещё и пригодным для практического использования.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.    Tomita E., Seki, T. An efficient branch and bound algorithm for finding a maximum clique. Lecture Notes in Computer Science, 2731, 2003, 278-289

2.      Nikolaev A., Batsyn M., San Segundo P. Reusing the same coloring in the child nodes of the search tree for the maximum clique problem. Lecture Notes in Computer Science, 8994, 2015, 275-280

3.      Matula D.W., Marble G., Isaacson J.D. Graph Coloring Algorithms. Graph Theory and

Computing, Academic Press, New York, 1972, 109-122

ПРИЛОЖЕНИЕ 1

Листинг алгоритма, основанного на методе ветвей и границ для решения ЗМК

1: function main()

2:     

:       

:        maxColor1

:        vV[1]

:        repeat until  

:                 if  then

:                           return

:                 end if

:                

:                

:                 if  then

:                           color(newU, C)

:                 else if  then

:                          

:                  end if

17:             maxColorномер максимального цвета в C

:                 vвершина с номером цвета maxColor

19:             

:        end repeat

: end function

ПРИЛОЖЕНИЕ 2

Листинг алгоритма RPC

1: function ROC (v, C, maxColor, newC)

:       

:        for  to maxColor do

:                

:                 if  then

:                          

:                 end if

:        end for

:       

:        while  and  do

:                 if  then

:                           wвершина, принадлежащая цвету  

:                          

:                           while  and  do

:                                    if  and  and  then

:                                            

:                                    end if

16:                                

:                           end while

:                 end if

19:            

:        end while

:       

:        for  to k do

:                 if  then

24:                      

:                          

:                 end if

:        end for

:        if  then

:                 Сортируем цвета по убыванию мощности и перенумеруем их

31:    end if

: end function

: function clique(U, C)

:        repeat until  

35:             maxColorномер максимального цвета в C

:                 vвершина с номером цвета maxColor

37:             if  then

:                           return

:                

:                

:                 if  then

:                           if  then

:                                    ROC(v, C, maxColor, newC)

:                           else

:                                     GCH_R(newU, newC)

:                           end if

48:             else if  then

:                          

:                  end if

51:             

:        end repeat

53: end function

: function main()

:        Упорядочение и перенумерация вершин

56:   

:        CGCH(V)

:        clique(V, C)

59: end function

ПРИЛОЖЕНИЕ 3.

Предлагаемые изменения в алгоритме RPC

Вместо строк 43-46:

: colorType = predict(args)

2: if colorType = 1 then

3:      GCH_R(newU, newC)

4: else if colorType = 2 then

5:      ROC(v, C, maxColor, newC)

: else if colorType = 3 then

7:      GCH(newU, newC)