Приближенное и точное решение различных вариантов задачи кластеризации вершин графа

Во введении обосновывается актуальность темы диссертации, приводятся
постановки исследуемых задач, содержится обзор известных результатов, от-
носящихся к рассматриваемым задачам.
Будем рассматривать только графы без петель и кратных ребер, т.е. обык-
новенные графы. Обыкновенный граф называется кластерным графом, если
каждая его компонента связности является полным графом [12]. Обозначим
через ℳ( ) множество всех кластерных графов на множестве вершин ,
ℳ ( ) – множество всех кластерных графов на , имеющих ровно компо-
нент связности, ℳ6 ( ) – множество всех кластерных графов на , имею-
щих не более компонент связности, 2 6 6 | |.
Если 1 = ( , 1 ) и 2 = ( , 2 ) – обыкновенные помеченные графы на
одном и том же множестве вершин , то расстояние ( 1 , 2 ) между ними
определяется как ( 1 , 2 ) = | 1 Δ 2 |= | 1 ∖ 2 |+| 2 ∖ 1 |.
Через ( ) обозначим окрестность вершины , т.е. множество вершин
графа = ( , ), смежных с вершиной .
Для множеств 1 , . . . , ⊆ таких, что ∩ = ∅ для любых , ∈
{1, . . . , } и 1 ∪ . . . ∪ = , обозначим через ( 1 , . . . , ) кластерный
граф из множества ℳ6 ( ) с компонентами связности, порожденными мно-
жествами 1 , . . . , . Сами множества 1 , . . . , будем называть кластерами.
Некоторые из могут быть пустыми.
В литературе рассматривались три варианта задачи кластеризации вер-
шин графа, ранее известной как задача аппроксимации графов.
Задача GC (GRAPH CLUSTERING). Для произвольного графа =
( , ) найти такой граф * ∈ ℳ( ), что
( , * ) =min ( , ).
∈ℳ( )

Задача GCk ( -GRAPH CLUSTERING). Дан произвольный граф =
( , ) и целое число , 2 6 6 | |. Найти такой граф * ∈ ℳ ( ), что
( , * ) = min ( , ).
∈ℳ ( )
Задача GC6k ([ ]-GRAPH CLUSTERING) формулируется аналогично.
Все варианты задачи кластеризации вершин графов являются – труд-
ными [1, 4, 8, 11, 12].
В 2004 г. Бансал, Блюм и Чаула [4] разработали 3-приближенный алго-
ритм решения задачи GC62 . Агеевым, Ильевым, Кононовым и Телевниным
[1] в 2006 г. было доказано, что для задачи GC62 существует полиномиальная
приближенная схема, a Гиотис и Гурусвами [8] предложили полиномиальную
приближенную схему для задачи GC6k (при любом фиксированном > 2).
В 2008 г. Коулман, Саундерсон и Вирт [7] предложили 2-приближенный алго-
ритм решения задачи GC62 , при этом они указали на сложность полиноми-
альной приближенной схемы из [8], что лишает ее перспективы практическо-
го применения. Для задачи GC2 Ильев, Ильева и Навроцкая [2] разработали
(3 − | 6 | )-приближенный алгоритм.
В главе 1 изучается вариант задачи кластеризации вершин графа с огра-
ниченным числом кластеров.
§1.1 содержит обзор известных результатов для задачи GC62 : 3- прибли-
женный алгоритм BBC (Bansal-Blum-Chawla) [4], процедуру локального по-
иска LS62 (M, X, Y) (Local Search for GC62 ) [7] и 2-приближенный алгоритм
CSW (Coleman-Saunderson-Wirth) [7].
В §1.2 предложен 6-приближенный алгоритм для задачи GC63 , исполь-
зующий идеи алгоритмов BBC и CSW .
Алгоритм NLS63 (Neighbourhood with Local Search for GC63 ).
Вход: граф = ( , ), | |= .
Выход: кластерный граф ∈ ℳ63 ( ).
Шаг 1. Если 6 2, то 1 = , иначе переход на шаг 2.
Шаг 2. Для каждой вершины ∈ выполнить:
Шаг 2.1. Положить 1 = { } ∪ ( ). Если 1 = , то – полный граф
, иначе переход на шаг 2.2.
Шаг 2.2. Обозначить через 1 подграф графа , порожденный множеством
∖ 1 . Приближенно решить задачу GC62 на графе 1 алгоритмом CSW,
полученный кластерный граф обозначить через = ( 2 , 3 ) (возможно,
3 = ∅). Положить = ( 1 , 2 , 3 ).
Шаг 3. Среди графов выбрать ближайший к кластерный граф :

( , ) = min ( , ).
∈
Теорема 1.3. Для любого графа = ( , ) имеет место неравенство
( , ) 6 6 ( , * ),
где * ∈ ℳ63 ( ) – оптимальное решение задачи GC63 на графе , а
– кластерный граф, построенный алгоритмом NLS63 .
В §1.3 представлен еще один полиномиальный алгоритм приближенного
решения задачи GC63 с лучшей гарантированной оценкой точности, осно-
ванный на оригинальной идее и не использующий локальный поиск.
Алгоритм DN63 (Double Neighbourhood for GC63 ).
Вход: граф = ( , ), = | |, > 3.
Выход: кластерный граф ∈ ℳ63 ( ).
Шаг 1. Для каждой упорядоченной пары вершин ( , ) ∈ × , ̸= ,
выполнить:
Шаг 1.1. Положить 1 = { } ∪ ( ( ) ∖ { }). Переход на шаг 1.2.
Шаг 1.2. Обозначить через 1 подграф графа , порожденный множеством
∖ 1 . Положить 2 = { } ∪ 1 ( ), 3 = ∖ ( 1 ∪ 2 ) (возможно, 3 = ∅).
Положить = ( 1 , 2 , 3 ).
Шаг 2. Среди построенных графов и графа выбрать ближайший к
кластерный граф ∈ ℳ63 ( ):
( , ) =min{ ( , ), ( , )}.
( , ) ∈ × ,
̸=

Теорема 1.4. При > 3 для любого -вершинного графа = ( , )
имеет место неравенство
( , ) 6 (6 − ) ( , * ),

где * ∈ ℳ63 ( ) – оптимальное решение задачи GC63 на графе , а
– кластерный граф, построенный алгоритмом DN63 .
В главе 2 рассматриваются задачи кластеризации вершин графа с фик-
сированным числом кластеров.
В §2.1 исследуется задача GC2 . Для этой задачи предложены два по-
линомиальных приближенный алгоритма. Первый алгоритм рассматривает
лишь кластерные графы из множества ℳ2 (т.е. лишь допустимые решения
задачи GC2 ).
Алгоритм N2 (Neighbourhood for GC2 ).
Вход: граф = ( , ).
Выход: кластерный граф = ( , ) ∈ ℳ2 ( ).
Шаг 1. Для каждой упорядоченной пары вершин ( , ) ∈ × , ̸= , по-
строить кластерный граф = ( , ) ∈ ℳ2 ( ), где = { } ∪ ( ( ) ∖
{ }), = ∖ .
Шаг 2. Среди всех кластерных графов выбрать ближайший к кла-
стерный граф :
( , ) =min ( , ).
( , ) ∈ × ,
̸=

Теорема 2.1. Для любого графа = ( , ) имеет место неравенство
( , ) 6 3 ( , * ),
где * ∈ ℳ2 ( ) – оптимальное решение задачи GC2 на графе , а –
кластерный граф, построенный алгоритмом N2 .
Пусть = ( , ) – произвольный граф. Для вершины ∈ и множества
⊆ обозначим через + количество таких вершин ∈ , что ∈ .
/ .
Через обозначим число таких вершин ∈ , что ∈
−

Для того, чтобы сформулировать второй приближенный алгоритм, нам
понадобится следующая процедура локального поиска.
Процедура LS2 (M,X,Y,Z1 ,Z2 ) (Local search for 2 components).
Вход: кластерный граф = ( , ) ∈ ℳ2 ( ), 1 ⊆ , 2 ⊆ .
Выход: кластерный граф ′ = ( ′ , ′ ) ∈ ℳ2 ( ).
Итерация 0. Положить 0 = , 0 = .
Итерация ( > 1).
Шаг 1. Для каждой вершины ∈ ∖ ( 1 ∪ 2 ) вычислить следующую
величину ( ) (изменение значения целевой функции при переносе вершины
в другой кластер):
( −1 )−++−
для ∈ −1 ∖ 1 ,
{︂
− ( −1 ) + ( −1 ) − ( −1 )
( ) =
( −1 )−++
− ( −1 ) + ( −1 ) − ( −1 )
−
для ∈ −1 ∖ 2 .
Шаг 2. Выбрать вершину ∈ ∖ ( 1 ∪ 2 ) такую, что
( ) =max ( ).
∈ ∖( 1 ∪ 2 )
Шаг 3. Если ( ) 6 0, то СТОП. Положить ′ = −1 , ′ = −1 , ′ =
( ′ , ′ ). Конец.
Шаг 4. Если ∈ −1 , то положить = −1 ∖ { }, = −1 ∪ { }.
Если же ∈ −1 , то положить = −1 ∪{ }, = −1 ∖{ }. Перейти
на итерацию +1.
Теперь можно описать еще один приближенный алгоритм.
Алгоритм NLS2 (Neighbourhood with Local Search for GC2 ).
Вход: граф = ( , ).
Выход: кластерный граф = ( , ) ∈ ℳ2 ( ).
Шаг 1. Пусть – множество всех допустимых решений, построенных ал-
горитмом N2 . Применить процедуру LS2 к каждому кластерному графу из
множества .
Шаг 2. Среди всех локальных оптимумов, построенных на шаге 1, выбрать
ближайший к кластерный граф .
Теорема 2.2. Для любого графа = ( , ) верно следующее неравенство:
( , ) 6 2 ( , * ),
где ∈ ℳ2 ( ) – решение, построенное алгоритмом NLS2 , а * ∈
ℳ2 ( ) – оптимальное решение задачи GC2 на графе .
В отличие от доказательства гарантированной оценки точности алгоритма
Коулмана, Саундерсона и Вирта [7], доказательство этой теоремы не исполь-
зует технику переключений, неприменимую для задачи GC2 .
В §2.2 исследуются новые задачи и методы кластеризации вершин графа
с частичным обучением.
Задача SSGCk ( -SET SEMI-SUPERVISED GRAPH CLUSTERING). Дан
обыкновенный граф = ( , ) и целое число , 2 6 6 | |. Выделено се-
мейство = { 1 , . . . , } попарно непересекающихся непустых подмножеств
множества . Требуется найти такой граф * ∈ ℳ ( ), что
( , * ) = min ( , ),
∈ℳ ( )
где минимум берется по кластерным графам = ( , ) ∈ ℳ ( ), в кото-
рых все множества семейства являются подмножествами множеств вершин
разных компонент связности (т.е. разных кластеров) графа .
Задача SGCk ( -SEMI-SUPERVISED GRAPH CLUSTERING) формули-
руется аналогично при | 1 |= · · · = | |= 1.
В случае = 2 для задач SGC2 и SSGC2 предложены два полиномиаль-
ных приближенных алгоритма.
Алгоритм NS2 (Neighbourhood semi-supervised for SGC2 and SSGC2 ).
Вход: граф = ( , ), 1 , 2 – непустые непересекающиеся подмножества
множества .
Выход: кластерный граф = ( , ) ∈ ℳ2 ( ), 1 , 2 – подмножества
разных кластеров.
Шаг 1. Для каждой вершины ∈ выполнить:
/ 1 ∪ 2 , то построить два кластерных графа = ( , ) и
(a) Если ∈
= ( , ), где
= { } ∪ (( ( ) ∪ 1 ) ∖ 2 ), = ∖ ,
= { } ∪ (( ( ) ∪ 2 ) ∖ 1 ), = ∖ .
(б) Если ∈ 1 ∪ 2 , то построить граф = ( , ), где
= { } ∪ (( ( ) ∪ ) ∖ ), = ∖ .
Здесь = 1 , = 2 при ∈ 1 , или = 2 , = 1 при ∈ 2 .
Шаг 2. Среди всех кластерных графов, построенных на шаге 1, выбрать
ближайший к кластерный граф = ( , ).
Теорема 2.3. Для любого графа = ( , ) имеет место неравенство
( , ) 6 3 ( , * ),
где * ∈ ℳ2 ( ) – оптимальное решение задачи SGC2 или SSGC2 на графе
, а – кластерный граф, построенный алгоритмом NS2 .
Алгоритм NSLS2 (Neighbourhood semi-supervised with Local Search for SGC2
and SSGC2 ).
Вход: граф = ( , ), 1 , 2 – непустые непересекающиеся подмножества
множества .
Выход: кластерный граф = ( , ) ∈ ℳ2 ( ), 1 , 2 – подмноже-
ства разных кластеров.
Шаг 1. Пусть – множество всех допустимых решений, построенных алго-
ритмом NS2 . Применить процедуру LS2 к каждому кластерному графу из
множества .
Шаг 2. Среди всех локальных оптимумов, построенных на шаге 1, выбрать
ближайший к кластерный граф .
Теорема 2.4. Для любого графа = ( , ) имеет место неравенство
( , ) 6 2 ( , * ),
где * ∈ ℳ2 ( ) – оптимальное решение задачи SGC2 или SSGC2 на графе
, а – кластерный граф, построенный алгоритмом NSLS2 .
В §2.3 исследованы взаимосвязи между задачами GC2 , SGC2 и SSGC2 .
Задача SGCk является частным случаем задачи SSGCk при | 1 |= · · · =
| |= 1. Также, решая задачу SGC2 для каждой упорядоченной пары вер-
шин ( , ) ∈ × некоторого графа = ( , ), мы тем самым можем найти
решение для задачи GC2 , поскольку хотя бы одна из пар вершин ( , ) бу-
дет содержать вершины, принадлежащие разным кластерам оптимального
решения задачи GC2 .
В главе 3 предложены и исследуются точные методы решения задач GC,
GC6k , GCk , SGCk и SSGCk , а также описаны результаты эксперименталь-
ного исследования.
В §3.1 предложены два подхода к нахождению точных решений для раз-
личных вариантов задачи кластеризации вершин графа. Первый подход ос-
нован на следующей универсальной схеме метода ветвей и границ, способной
находить оптимальное решение для любой из рассматриваемых задач для
произвольного графа = ( , ), | |= . Через ( 1 , . . . , ) обозначим раз-
биение подмножества множества вершин графа на множеств, а через
( 1 , . . . , ) – начальное разбиение.
Алгоритм BBM(G, (I1 , . . . , Ik )).
Шаг 1. Положить 1 = 1 , . . . , = ; // = для задачи GC
( −1)
Шаг 2. =2 ;
Шаг 3. = { : ̸= ∅}; // множество индексов непустых кластеров
Шаг 4. = {1, . . . , } ∖ ; // множество индексов пустых кластеров
Шаг 5. Branch((S1 , . . . , Sk ), record, A, B).
Процедура Branch((S1 , . . . , Sk ), record, A, B).
Если 1 ∪ . . . ∪ ̸= :
Шаг 1. Выбрать ∈/ ∖ ( 1 ∪ . . . ∪ );
Шаг 2. Для каждого ∈ :
Шаг 2.1. = Bound((S1 , . . . , Si ∪ {v}, . . . , Sk );
Шаг 2.2. Если ( < ) Branch((S1 , . . . , Si ∪ {v}, . . . , Sk ), record, A, B); Шаг 3. Если ̸= ∅: // выбрать любое пустое множество Шаг 3.1. Взять произвольный ∈ ; Шаг 3.2. = Bound((S1 , . . . , Si ∪ {v}, . . . , Sk ); Шаг 3.3. Если ( < ) Branch((S1 , . . . , Si ∪ {v}, . . . , Sk ), record, A, B); иначе Шаг 4. = Bound((S1 , . . . , Sk ); Шаг 5. Если (updateRecord(record, b, (S1 , . . . , Sk ))) = . Второй подход к поиску оптимальных решений опирается на модели це- лочисленного линейного программирования. В 2005 г. Чарикар, Гурусвами и Вирт [5] предложили модель булева программирования для задачи GC, вве- дя следующие бинарные переменные: соответствует каждой паре вершин и . Если вершины и находятся в одном кластере, то = 0, иначе = 1 при ̸= (по умолчанию = 0). Легко видеть, что если = 0 и = 0, то и = 0, а значит 6 + выполняется для каждой упорядоченной тройки вершин , , . Таким образом, мы можем построить модель булева программирования для задачи GC6k . ∑︁∑︁ +(1 − ) → min ∈ ∈ / 6 + , , , ∈ {1, . . . , } ( + 2)( − 1) 1 2 + . . . −1 6, 1 , . . . , ∈ {1, . . . , } ∈ {0, 1}, , ∈ {1, . . . , } Аналогичные модели построены и для других задач. В §3.2 приводятся результаты вычислительного эксперимента о влиянии локального поиска на точность и время работы алгоритмов. Так, для за- дачи GC62 для сравнения с алгоритмами BBC (Bansal-Blum-Chawla) [4] и CSW (Coleman-Saunderson-Wirth) [7] был предложен эвристический алго- ритм N1LS62 (Neighbourhood with one Local Search for GC62 ). Ключевое изменение этого алгоритма в сравнении с алгоритмом CSW – процедура ло- кального поиска LS62 применяется лишь к лучшему допустимому решению, полученному алгоритмом BBС, что значительно сокращает время его ра- боты. Экспериментальное исследование проводилось в два этапа: предвари- тельный эксперимент на графах малой размерности и основной эксперимент на графах большей размерности. Предварительный эксперимент проводился на графах размерности от 15 до 50 вершин, по 100 графов в серии. Для таких графов алгоритмом BBM и с помощью решателя Gurobi, использующего модель целочисленного линей- ного программирования, удалось найти точные решения. Стоит отметить, что при = 31 время работы решателя Gurobi в среднем было равно 2000 сек., и для графов большей размерности он не использовался. Время работы алгоритма BBM при = 50 в среднем было равно 1781 сек. Точностью алгоритма будем называть отношение значения целевой функ- ции на решении, полученном этим алгоритмом, к оптимальному значению. Ðèñ. 1: Ñðåäíÿÿ òî÷íîñòü àëãîðèòìîâBBC CSW ,èN1LS62íà ãðàôàõ ìàëîé ðàçìåðíîñòè. Обозначим через BBC ( ), CSW ( ) и N1LS62 ( ) точности алгоритмов BBC, CSW и N1LS62 соответственно. По итогам предварительного эксперимента удалось получить представле- ния о характере изменения средней точности алгоритмов (рис 1.). Среднее отклонение от оптимума алгоритма CSW близко к нулю и достигает мак- симального значения 0.06% при = 15. Среднее отклонение от оптимума алгоритма N1LS62 также достаточно близко к нулю и достигает максиму- ма 3.6% при = 25. При том же значении достигает максимума среднее отклонение от оптимума алгоритма BBC и составляет 16%. Очевидно, что точность алгоритма CSW всегда не меньше, чем точность алгоритмов BBC и N1LS62 , поэтому в качестве объекта дальнейшего исследования были вы- браны две случайные величины: BBC ( ) N1LS62 ( ) BBC ( ) =, N1LS62 ( ) =. CSW ( ) CSW ( ) В эксперименте на графах большей размерности (при от 100 до 6000, решалось по 100 задач в серии) исследовалось поведение случайных величин BBC ( ) и N1LS62 ( ). Тенденции изменения средних значений и границ до- верительных интервалов при уровне значимости 0.05 представлены на рис. 2. Комментируя результаты, можно сказать следующее. С ростом обе исследуемые случайные величины уменьшаются, а ши- рина доверительного интервала сужается настолько, что интервалы фак- тически невозможно увидеть на рисунке. Величина N1LS62 ( ) находится в окрестности единицы, что позволяет говорить о том, что точность алгоритма N1LS62 стремится к точности алгоритма CSW с ростом . Учитывая, что Ðèñ. 2: Ñðåäíèå çíà÷åíèÿ ñëó÷àéíûõ âåëè÷èí BBC ( )è N1LS62 ( ). при = 6000 среднее время работы алгоритма N1LS62 составило 149.21 сек, а среднее время работы алгоритма CSW составило 580.68 сек, использование алгоритма N1LS62 является наиболее предпочтительным. Экспериментальное исследование показало, что решения, найденные алго- ритмами CSW и N1LS62 , как правило, очень близки к оптимальным. Для задач GC63 , GC2 и SGC2 были проведены аналогичные экспери- ментальные исследования. В заключении приведены основные результаты диссертации.