вивчається задача кластеризації графа. Для варіанту завдання, в якому число кластерів не перевищує 3, розроблені три наближених алгоритму. Перший алгоритм використовує в якості процедури відомий алгоритм Коулмана Саундерсона Вірта, який наближено вирішує аналогічне завдання з числом кластерів, що не перевершує 2, і багаторазово застосовує локальний пошук. Другий алгоритм заснований на оригінальній ідеї і взагалі не використовує локальний пошук. У третьому алгоритмі процедура локального пошуку застосовується до допустимому рішенням, поверненого другим алгоритмом. отримано апріорні гарантовані оцінки точності всіх трьох алгоритмів, краща з яких дорівнює (6 12 / n), де n число вершин даного графа. Проведено також експериментальне порівняння запропонованих алгоритмів.

Анотація наукової статті з математики, автор наукової роботи - Ильев Віктор Петрович, Ільєва Світлана Діадоровна, Моршінін Олександр Володимирович


Approximate algorithms for graph clustering problem

In the paper, the graph clustering problem is studied. For the version of the problem when the number of clusters does not exceed 3, we develop three approximate algorithms. The first algorithm uses as a procedure the known Coleman Saunderson Wirth algorithm which approximately solves the similar problem when the number of clusters does not exceed 2, and repeatedly applies a local search. On the contrary, our second algorithm is based on an original idea and does not use a local search at all. The main difference between these algorithms is the following. The first algorithm looks over all vertices of a given graph, for each vertex forms the cluster involving this vertex and all its neighbors and on the rest of the vertices forms one or two clusters using the Coleman Saunderson Wirth algorithm. The second algorithm looks over all ordered pairs of vertices of a given graph and for every pair forms two clusters at once, each of which contains only one vertex of this pair with some of its neighbors, placing the rest of the vertices to the third cluster (the third cluster may be empty). Finally, the third algorithm applies the local search only once to the feasible solution returned by the second one. A priori performance guarantees of all approximate algorithms are obtained, the best is equal to (6 12 / n) for the second and the third algorithms, where n is the number of vertices of a given graph. Also, experimental comparing of the developed algorithms was carried out. Experimental testing show that running time of our second and third algorithms is essentially less than running time of the first algorithm. At the same time the third algorithm demonstrated the best results in sense of accuracy of the solutions. Thus, the third algorithm has the best characterstics both from point of view of theoretical analysis and experimental study.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика


    Наукова стаття на тему 'АЛГОРИТМИ наближеного рішення ОДНІЄЇ ЗАВДАННЯ КЛАСТЕРИЗАЦІЇ ГРАФА'

    Текст наукової роботи на тему «АЛГОРИТМИ наближеного рішення ОДНІЄЇ ЗАВДАННЯ КЛАСТЕРИЗАЦІЇ ГРАФА»

    ?2019 Прикладна теорія графів №45

    УДК 519.8

    АЛГОРИТМИ наближеного рішення ОДНІЄЇ ЗАВДАННЯ КЛАСТЕРИЗАЦІЇ ГРАФА

    В. П. Ильев *, С. Д. Ільєва *, А. В. Моршінін **

    * Омський державний університет ім. Ф. М. Достоєвського, Омськ, Росія, ** Інститут математики ім. С. Л. Соболева СО РАН, м Омськ, Росія

    Вивчається задача кластеризації графа. Для варіанту завдання, в якому число кластерів не перевищує 3, розроблені три наближених алгоритму. Перший алгоритм використовує в якості процедури відомий алгоритм Коулмана - Саундерсона - Вірта, який наближено вирішує аналогічне завдання з числом кластерів, що не перевершує 2, і багаторазово застосовує локальний пошук. Другий алгоритм заснований на оригінальній ідеї і взагалі не використовує локальний пошук. У третьому алгоритмі процедура локального пошуку застосовується до допустимому рішенням, поверненого другим алгоритмом. Отримано апріорні гарантовані оцінки точності всіх трьох алгоритмів, краща з яких дорівнює (6 - 12 / n), де n - число вершин даного графа. Проведено також експериментальне порівняння запропонованих алгоритмів.

    Ключові слова: граф, кластеризація, наближений алгоритм, гарантована оцінка точності.

    DOI 10.17223 / 20710410/45/7

    APPROXIMATE ALGORITHMS FOR GRAPH CLUSTERING PROBLEM

    V. P. Il'ev *, S.D. Il'eva *, A. V. Morshinin **

    * Dostoevsky Omsk State University, Omsk, Russia, ** Sobolev Institute of Mathematics SB RAS, Omsk, Russia

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    In the paper, the graph clustering problem is studied. For the version of the problem when the number of clusters does not exceed 3, we develop three approximate algorithms. The first algorithm uses as a procedure the known Coleman - Saunderson - Wirth algorithm which approximately solves the similar problem when the number of clusters does not exceed 2, and repeatedly applies a local search. On the contrary, our second algorithm is based on an original idea and does not use a local search at all. The main difference between these algorithms is the following. The first algorithm looks over all vertices of a given graph, for each vertex forms the cluster involving this vertex and all its neighbors and on the rest of the vertices forms one or two clusters using the Coleman - Saunderson - Wirth algorithm. The second algorithm looks over all ordered pairs of vertices of a given graph and for every pair forms two clusters at once, each of which contains only one vertex of this pair with some of its neighbors, placing the rest of the vertices to the third cluster (the third cluster may be empty). Finally, the third algorithm applies the local search only once to the feasible solution returned by the second one. A priori performance guarantees of all approximate algorithms are obtained, the best is equal to (6 - 12 / n) for the second and the third

    algorithms, where n is the number of vertices of a given graph. Also, experimental comparing of the developed algorithms was carried out. Experimental testing show that running time of our second and third algorithms is essentially less than running time of the first algorithm. At the same time the third algorithm demonstrated the best results in sense of accuracy of the solutions. Thus, the third algorithm has the best characterstics both from point of view of theoretical analysis and experimental study.

    Keywords: graph, clustering, approximation algorithm, performance guarantee.

    Вступ

    У задачі кластеризації потрібно розбити заданий безліч об'єктів на кілька підмножин (кластерів) на основі подібності об'єктів один з одним. Однією з найбільш наочних формалізацій цього завдання є завдання кластеризації графа [1, 2]. У ній об'єктів взаємно однозначно зіставлені вершини графа, а ребра з'єднують вершини, відповідні схожим об'єктів.

    Будемо розглядати тільки звичайні графи, т. Е. Графи без петель і кратних ребер. Звичайний граф називається кластерним графом [3], якщо кожна його компонента зв'язності є повним графом. Нехай M (V)-безліч всіх кластерних графів на множині вершин V; Mk (V)-безліч всіх кластерних графів на V, мають рівно k непорожніх компонент зв'язності; M ^ k (V)-безліч всіх кластерних графів на V, які мають не більше k компонент зв'язності, 2 ^ k ^ | V |.

    Якщо G1 = (V, E1) і G2 = (V, E2) - графи на одному і тому ж безлічі вершин V, то відстань p (G1, G2) між ними визначається як

    p (Gi, G2) = IE1AE2I = | Ei \ E2I + | E2 \ Ei |,

    т. е. p (G1, G2) -це число незбіжних ребер в графах G1 і G2.

    У літературі в основному розглядалися наступні три варіанти завдання кластеризації графа.

    Завдання GC. Для довільного графа G = (V, E) знайти такий граф M * G M (V),

    що

    p (G, M *) = min p (G, M).

    M)

    Завдання GCk. Дан довільний граф G = (V, E) і ціле число k, 2 ^ k ^ | V |. Знайти такий граф M * G Mk (V), що

    p (G, M *) = min p (G, M).

    m emk (v)

    Завдання GC ^ k. Дан довільний граф G = (V, E) і ціле число k, 2 ^ k ^ | V |. Знайти такий граф M * G M ^ k (V), що

    p (G, M *) = min p (G, M).

    m em ^ k (v)

    В останні роки завдання кластеризації графів неодноразово перевідкривається і незалежно вивчалися під різними назвами (Correlation Clustering [4], Cluster Editing [3, 5] та ін.). У цих та інших роботах розглядалися також більш загальні постановки завдань.

    Обчислювальна складність завдань кластеризації графів довгий час залишалася невідомою. У 1986 р М. Кржіванек і Дж. Моравек [6] довели, що завдання ОС є ХР-важкою, проте їх робота залишилася непоміченою. У 2004 р в [4] і незалежно в [3] доведена ХР-трудність завдання ОС. В [4] доведено також, що завдання ОСк є ХР-важкою при будь-якому фіксованому до ^ 2; в 2006 р в [7] опубліковано більш просте доказ цього результату. У тому ж році в [8] доведено, що завдання ОС 2 і ОС ^ 2 ХР-важкі вже на кубічних графах, звідки зроблений висновок, що всі згадані раніше завдання кластеризації графа є ХР-важкими, включаючи і завдання ОС ^ до.

    В [4] наведено 3-наближений алгоритм для задачі ОС ^ 2, в [8] доведено існування рандомизированной полиномиальной наближеною схеми для задачі ОС ^ 2, а в [7] запропонована рандомізованих поліноміальна наближена схема для задачі ОСк (для будь-якого фіксованого до ^ 2), складність якої позбавляє її перспективи практичного застосування. В [9] представлений 2-наближений алгоритм розв'язання задачі ОС ^ 2, заснований на застосуванні процедури локального пошуку до кожного допустимому рішенням, отриманого за допомогою 3-наближеного алгоритму з [4]. Для завдання ОС2 в [10] запропоновано (3 - 6 / | V |) -прібліжённий алгоритм.

    Що стосується завдання ОС, то в [11] показано, що задача ОС є АРХ-важкою, і розроблений 4-наближений алгоритм її вирішення. В [12] запропоновано 2,5-наближений-ний алгоритм для задачі ОС, в [13] - (2,06 - е) -прібліжённий алгоритм.

    Більш детальний огляд відомих результатів за завданнями кластеризації графів можна знайти в [14].

    У п. 1 цієї роботи наводиться короткий огляд відомих результатів для задачі кластеризації графа, в якій число кластерів не перевищує 2. У п. 2 розглядається задача ОС ^ 3, в якій число кластерів не перевищує 3. Для цього завдання запропоновані два поліноміальних наближених алгоритму . Перший 6-прибл-жённий алгоритм використовує в якості процедури відомий алгоритм Коулмана - Саундерсона - Вірта, який наближено вирішує аналогічне завдання з числом кластерів, що не перевершує 2, і багаторазово застосовує локальний пошук. Другий алгоритм заснований на оригінальній ідеї і не використовує локальний пошук. Доведено апріорні гарантовані оцінки точності обох алгоритмів, краща з яких, у другого алгоритму, дорівнює 6 - 12 / п, де п - число вершин графа. У п. 3 запропонований ще один поліноміальний алгоритм наближеного розв'язання задачі ОС ^ 3, в якому процедура локального пошуку застосовується до допустимому рішенням, повернений другим алгоритмом. Наведено також результати експериментального дослідження всіх трьох розроблених алгоритмів.

    1. Наближені алгоритми для завдання ОС ^ 2

    Через Мс (у) позначимо околиця вершини V, т. Е. Безліч вершин графа О = = (V, Е), суміжних з вершиною V. Через Nс ^) позначимо множину вершин графа Про, що не суміжних з V: N = V \ (N0 (V) і {V}).

    Нехай О1 = (V, Е1) і О2 = (V, Е2) - два графа на множині вершин V, п = IV |. Через 0 (01, О2) позначимо граф на множині вершин V з безліччю ребер Е1АЕ2. Зауважимо, що р (О1, О2) -це кількість ребер в графі В (О1, О2).

    Наступне твердження легко доводиться за допомогою леми про рукостискання.

    Лемма 1 [10]. Нехай-мінімум ступенів вершин в графі Д (О1, О2). тоді

    р (ОьО2) ^ ПАТ-т / 2.

    Для множин VI, ..., V З V, таких, що V П 'Ц = 0 для будь-яких г, Е {1, ..., в}, г =, і VI і ... і Vs = V , позначимо через М (VI, ..., К) кластерний граф з)

    з компонентами зв'язності, породженими множинами VI, ..., V ,. Далі безлічі VI, ..., V будемо називати кластерами. Деякі з V можуть бути порожніми.

    Нехай С = (V, Е) -довільний граф. Для вершини V Е V і безлічі А З V позначимо через А + кількість таких вершин і Е А, що (V, і) Е Е; А- число таких вершин і Е А, що ^, і) Е Е.

    Будемо говорити, що кластерний граф М (Vь ..., Vполучен з графа М (VI, ..., V,) шляхом перенесення вершини V Е V з кластера V в кластер V, -, якщо V ^ = V \ {V }, V, = V, і {V} і Vк = ^ для всіх до Е {г, ^}.

    У 2004 р розроблений 3-наближений алгоритм 1 рішення задачі ОС ^ 2 [4].

    Алгоритм 1. BBC

    Вхід: граф G = (V, E). Вихід: кластерний граф M Е M ^ 2 (V). 1: Для кожної вершини v Е V визначити кластерний граф Mv = M (Vi, V2) наступним чином: V1 = {v} U NG (v), V2 = NG (v) (можливо V2 = 0). 2: Серед усіх графів Mv вибрати такий граф M, що p (G, M) = min p (G, Mv).

    v € V

    Справедлива наступна гарантована оцінка точності алгоритму BBC. Теорема 1 [4]. Для будь-якого графа G = (V, E) має місце нерівність

    p (G, M) ^ 3p (G, M *),

    де M * Е M ^ 2 (V) оптимальне рішення задачі GC ^ 2 на графі G; M - кластерний граф, побудований алгоритмом BBC.

    У 2008 р Т. Коулман, Дж. Саундерсон і А. Вірт [9] запропонували 2-наближений алгоритм для задачі GC ^ 2, застосувавши процедуру локального пошуку LS до кожного допустимому рішенням, отриманого на кроці 1 алгоритму BBC (алгоритм 2).

    Алгоритм 2. Процедура LS (M, X, Y)

    Вхід: кластерний граф M = M (X, Y) Е).

    Вихід: кластерний граф M = M (X, Y) Е).

    1: Для кожної вершини v Е X обчислити $ (v) = X- - X + + Y + - Yv-. Вибрати таку вершину v0 Е X, що i (v0) = max i (v).

    vEX

    2: Для кожної вершини u Е Y обчислити $ (u) = Y- - Y + + X + - X-. Вибрати таку вершину u0 Е Y, що i (u0) = max $ (u).

    uEY

    3: Якщо i (v0) ^ 0 і $ (u0) ^ 0, то стоп; покласти X: = X і Y: = Y, інакше перехід на крок 4.

    4: Якщо? (V0) ^ i (u0), то покласти X: = X \ {v0}, Y: = Y U {v0}.

    5: Якщо i (v0) < i (u0), то покласти X: = X U {u0}, Y: = Y \ {u0}. Перехід на крок 1.

    З урахуванням BBC і процедури локального пошуку LS 2-наближений алгоритм Коулмана, Саундерсона і Вірта прийме такий вигляд (алгоритм 3).

    Алгоритм 3. CSW

    Вхід: граф G = (V, E). Вихід: кластерний граф M G M ^ 2 (V). 1: Для кожної вершини v G V:

    2: визначити кластерний граф Mv = M (Vi, V2) наступним чином:

    Vi = {v} U NG (v), V2 = NG (v);

    3: виконати процедуру LS (Mv, Vi, V2). Побудований граф позначити Mv. 4: Серед усіх графів Mv вибрати такий граф M, що p (G, M) = minp (G, Mv).

    v € V

    Справедлива наступна гарантована оцінка точності алгоритму CSW. Теорема 2 [9]. Для будь-якого графа G = (V, E) має місце нерівність

    p (G, M) ^ 2p (G, M *),

    де M * G M ^ 2 (V) оптимальне рішення задачі GC ^ 2 на графі G; M - кластерний граф, побудований алгоритмом CSW.

    2. Наближене рішення задачі GC ^ 3 2.1. 6-Наближений алгоритм для задачі GC ^ 3 Використовуючи ідеї [4, 9], можна побудувати поліноміальний алгоритм 4 наближеного рішення задачі GC ^ 3.

    Алгоритм 4. Ai

    Вхід: граф G = (V, E), | V | = N. Вихід: кластерний граф M1 G M ^ 3 (V). 1: Якщо n ^ 2, то M1: = G, інакше перехід на крок 2. 2: Для кожної вершини w G V:

    3: V1: = {w} U NG (w). Якщо V1 = V, то Mw-повний граф Kn, інакше перехід на крок 4.

    4: Позначити G1 підграф графа G, породжений безліччю V \ V1. Приблизно вирішити задачу GC ^ 2 на графі G1 алгоритмом CSW, отриманий кластерний граф позначити M = M (V2, V3) (можливо, V3 = 0). Покласти Mw: = M (V1, V2, V3). 5: Серед усіх графів Mw вибрати найближчий до G кластерний граф M1:

    p (G, M1) = min p (G, Mw).

    Зауваження 1. Трудомісткість алгоритму Лх дорівнює 0 (п6). Справедлива наступна гарантована оцінка точності алгоритму Лх. Теорема 3. Для будь-якого графа О = (V, Е) має місце нерівність

    р (О, М1) ^ 6р (О, М *),

    де М * €) оптимальне рішення задачі ОС ^ 3 на графі О; М1 - кластерний

    граф, побудований алгоритмом Лх.

    Доведення. Нехай V - вершина мінімальному ступені в графі Б = = Б (С, М *). Розглянемо кластерний граф М Е М ^ з ^), отриманий з М * шляхом перенесення вершин в інші компоненти графа М *: вершини безлічі N0 ^) П N0 (V) перемістимо в компоненту, що містить вершину V, а вершини, що належать безлічі N ( V), перенесемо в будь-яку з компонент, що не містять V. Тоді кластер VI = {V} і N0 ^) -один і той же в М верб М ^.

    Якщо ^ т; п = 0, то кластерний граф М збігається з кластерним графом М *, а значить,

    р (С, М) = р (С, М *) ^ 3р (С, М *).

    нехай > 0. Зауважимо, що при перенесенні вершин значення цільової функції не може збільшитися більш ніж на п ^ т; п, так як перенесення однієї вершини збільшує значення цільової функції не більше ніж на п = IV |. Звідси з урахуванням леми 1 отримуємо

    р (С, М) ^ р (С, М *) + п ^ тт ^ р (С, М *) + 2р (С, М *) = 3р (С, М *).

    Отже,

    р (С, М) ^ 3р (С, М *) (1)

    Доведемо, що р (С, МЬ) ^ 6р (С, М *). Розглянемо кластер VI = ^} іN0 ^). Можливі два випадки:

    а) VI = V .Відповідно до кроком 3 алгоритму А1 вважаємо М ^: = Кп = М. Отже,

    р (С, М ^) = р (С, М) ^ 3р (С, М *) ^ 6р (С, М *).

    б) VI = V. Позначимо через М * оптимальне рішення задачі ОС ^ 2 на графі породжених безліччю V \ V1. Розглянемо кластерний граф М = М і М *, де М (VI)-повний граф на безлічі VI. Очевидно, що

    р (С, М) ^ р (С, М).

    Тоді з урахуванням (1)

    р (С, М) ^ 3р (С, М *). (2)

    Нехай М = М ( "^ 2, V3) допустимая рішення задачі ОС ^ 2 на графі С1, знайдене алгоритмом CSW на кроці 4, якщо на кроці 3 вибрано вершина V. Тоді МЬ = М (^ (безліч V3 може бути порожнім).

    Позначимо через у суму числа відсутніх ребер в підграфі графа С, породжених безліччю вершин VI = {V} і N<0 ^), і величини розрізу (VI, V \ VI) в графі С. Очевидно, що

    р (С, М ") = в + р (С1, М), р (С, М) = в + р (С1, М *). (3)

    Якщо IV \ V !! ^ 2, то М = С1 і р (С1, М) = р (С1, М *) = 0. Тоді з урахуванням (2) і (3)

    р (С, М. ") = р (С, М) ^ 3р (С, М *) ^ 6р (С, М *).

    Нехай IV \ Т / 11 ^ 3. Тоді по теоремі 2

    р (С1, М) ^ 2р (С1, М *).

    В силу (2) і (3) отримаємо

    р (О, М ^) = 5 + р (О1, М) ^ 5 + 2р (О1, М *) ^ 25 + 2р (О1, М *) = = 2 (5 + р (О1, М *)) = 2р (О, М) ^ 6р (О, М *).

    На кроці 5 алгоритму Лх серед всіх графів буде розглянуто граф М ^, де V - вершина мінімальному ступені в графі В = В (О, М *). Звідси виходить необхідна оцінка точності алгоритму Лх. |

    У п. 2.2 представлений ще один поліноміальний алгоритм наближеного розв'язання задачі ОС ^ 3 з кращого гарантованої оцінкою точності, заснований на іншу ідею і не використовує локальний пошук.

    2.2. Наближений алгоритм для задачі ОС ^ 3, н е і з п про л ь з у ю щ і й л про кал ь н и й п о и с ь к

    Лемма 2. Нехай О = (V, Е) - п-верховий граф, п ^ 3, М = М (У1, ..., К), вершина V € V така, що її околиця в графі В = В (О , М) не порожня. Розглянемо кластерний граф М '€), отриманий з графа М наступним чином: або

    довільна вершина і € N0 ^) П N0 (V) перенесена в кластер V, або довільна вершина і € N П N0 (V) перенесена в будь-який з кластерів V, який не містить вершину V. Тоді

    р (О, М ') ^ р (О, М) + (п - 3).

    Доведення. Нехай і € N0 (V). Очевидно, що графи В та В '= В (О, М') відрізняються тільки ребрами виду (і, пекло), ад € V, інші ребра у них збігаються. отже,

    р (О, М ') - р (О, М) = (і) | - (і) |. Так як V € N0 (і), а N0 / (і) З V \ {u, v}, то (і) | ^ 1, (і)) | ^ П - 2, звідки

    р (О, М ') - р (О, М) ^ п - 2 - 1 = п - 3.

    Лемма 2 доведена. |

    Нехай М * = М (V *, V *, К *) €) оптимальне рішення задачі ОС ^ 3 на

    графі О = (V, Е), причому М * = Кп, де п = IV |. Через (V) позначимо ступінь вершини V в графі В = В (О, М *).

    Покладемо = (V): V € V} = ^); позначимо V / той кластер графа М *,

    який містить вершину v1, п1 = IV * |. Нехай? 2 = (V): V € V \ V /} = ^ 2),

    V * -той кластер графа М *, який містить вершину v2. Очевидно, що? 1 ^? 2.

    Так як р (О, М *) дорівнює числу ребер в графі В (О, М *), з леми про рукостискання і леми 1 випливає

    Лема 3. Для довільного п-вершинного графа О = (V, Е) має місце нерівність

    ?1п1 +? 2 (п - п1) п ↑ 1 2 ^ "2", де М * - оптимальне рішення задачі ОС ^ 3 на графі Про.

    Алгоритм 5 заснований на ідеї, відмінною від тієї, що використана в [4, 9] для наближеного розв'язання задачі ОС ^ 2.

    Зауваження 2. Трудомісткість алгоритму Л2 дорівнює 0 (П3).

    р (О, М *)

    Алгоритм 5. A2

    Вхід: граф G = (V, E), n = | Vn ^ 3. Вихід: кластерний граф M2 G M ^ 3 (V). 1: Для кожної впорядкованої пари вершин (u, v) G V х V, такий, що u = v, виконати:

    2: покласти Vi = {u} U (NG (u) \ {v});

    3: позначити через G1 підграф графа G, породжений безліччю V \ V1. Покласти V2 = {v} U Ng1 (v), V3 = V \ (V1 U V2) (V3 може бути порожнім). покласти

    Muv = M (Vi, V2, V3).

    4: Серед побудованих графів Muv і графа Kn вибрати найближчий до G кластерний граф M2 G):

    p (G, M2) = min {p (G, Muv), p (G, Kn)},

    (U, v) ev xV

    де мінімум береться по всім парам (u, v) G V х V, таким, що u = v.

    Справедлива наступна гарантована оцінка точності алгоритму А2. Теорема 4. При п ^ 3 для будь-якого п-вершинного графа С = (V, Е) має місце нерівність

    р (С, М2) ^ ^ 6 -12) р (С, М *),

    де М * Е) оптимальне рішення задачі ОС ^ 3 на графі С; М2 - кластерний

    граф, побудований алгоритмом А2.

    Доведення. Можливі два випадки.

    Випадок 1: М * = Кп. Тоді на кроці 2 алгоритму А2 в якості М2 буде обраний граф Кп, отже,

    р (С, М2) = р (С, М *) ^ ^ 6 -12) р (С, М *).

    Випадок 2: М * = М (V *, V *, V *) = Кп. Нехай, як і раніше, v1, v2 Е V - такі вершини, що = (v2) = причому v1 Е V /, v2 Е V *. Розглянемо кла-

    Стерн граф М Е), отриманий з графа М * шляхом перенесення не більше ніж

    вершин в інші кластери графа М *: вершини безлічі (N<5 ^) \ ^ 2}) П N0 (v1) перенесені в кластер, що містить вершину v1 (тобто в кластер V *), а вершини безлічі NGП N0- в кластер, який не містить ні v1, ні v2 (т. е. в кластер V *). Нехай М = М (V, V, V), де V = і (N «^ 0 \ {v2}) і - кластер, що містить вершину v2.

    якщо > 0, то, застосувавши не більше ніж раз лемму 2, отримаємо

    р (С, М) ^ р (С, М *) + ^ (п - 3). Якщо = 0, то граф М збігається з графом М *, а значить,

    р (С, М) = р (С, М *) = р (С, М *) + ^ (п - 3). Отже, показано, що в будь-якому випадку

    р (С, М) ^ р (С, М *) + (п - 3). (4)

    Зауважимо, що V = V, оскільки V2 € Нехай О1 -подграф графа О, породжений множиною вершин V \ V. Розглянемо кластерний граф М ^ 2 € \ V), побудований в такий спосіб: вершина v2 і всі суміжні з нею вершини графа О1 належать одного кластеру графа М ^ 2, а все несуміжні з v2 вершини - іншому кластеру графа М ^ 2 (цей кластер може бути порожнім).

    Нехай М1 € \ V1) -подграф графа М, породжений множиною вершин

    V \ У1, тобто М1 = М (V2, V). Покладемо В1 = В (О1, М1). Позначимо через? 2 ступінь вершини v2 в графі В1. Очевидно, що кластерний граф М ^ 2 отримано з графа М1 шляхом перенесення? 2 вершин: вершини безлічі N0! ^ 2) П N0 (v2) перенесені в кластер, що містить вершину v2 (тобто в компоненту, породжену множиною V), а всі вершини безлічі Nс1 (v2) П N0 ^ 2) -в кластер, який не містить v2 (т . е. в компоненту, породжену множиною "^ 3).

    Якщо IV \ У1 | ^ 2, то, очевидно, М ^ 2 = О1 і р (О1, М ^ 2) = 0. Якщо при цьому? 2 = 0 то М ^ 2 = М1. Таким чином,

    р (О1, М "2) = р (О1, М1) = р (О1, М1) +? 2 (1 V \ V! | - 3).

    Нехай тепер? 2 > 0. Це можливо тільки при IV \ УЦ = 2. У цьому випадку? 2 = 1. Це означає, що р (О1, М1) = 1. Тоді

    р (О1, М "2) = 0 = р (О1, М1) - 1 = р (О1, М1) +? 2 (IV \ Vl | - 3).

    Тепер розглянемо випадок IV \ V11 ^ 3. Якщо? 2 > 0 то, застосувавши? 2 раз лемму 2, отримаємо

    р (ОьМ, 2) ^ р (О1, М1) + d2 (| V \ Vl | - 3). Якщо? 2 = 0, то графи М ^ 2 і М1 збігаються, отже,

    р (О1, М "2) = р (О1, М1) = р (О1, М1) +? 2 (IV \ Vl | - 3). Отже, показано, що в будь-якому випадку

    р (ОьМ, 2) ^ р (О1, М1) + V \ Vl | - 3).

    Так як граф М отриманий з графа М * шляхом перенесення не більше ніж? 1 вершин в інші кластери, то ^^ ^ IV * I -? 1 = п1 -? 1, звідки

    р (О1, М "2) ^ р (О1, М1) +? 2 (п - п1 +? 1 - 3). (5)

    Покажемо, що? 2 ^? 2. Справді,? 2 = (v2) |,? 2 = (v2) |. Безліч N0 (v2) складається з усіх вершин і, таких, що або і € П (V * і V *), або і € N П V *, а безліч N0 (v2) -з усіх вершин і, таких, що або і € N<2 ^ (v2) П V3, або і € NС1 (v2) П V ;, т. Е.

    N0И = (NG (V2) П (V * і V;)) і П V2 *),

    N01 (V2) = (N01 (V2) П Vз) і (N01 (V2) П V2).

    Очевидно, що V3 З V / і V * і V2 З V *, а так як О1 -подграф графа О, то N0 (v2) З N «^ 2) і N0 (v2) З N0 ^ 2). отже,

    N01И П Vз З NG (V2) П (V * і Vз *), И П V2 З N ^ 2) П V *.

    Значить, N ^ 1 ^ 2) З N0 ^ 2), звідки отримуємо? 2 = (v2) | ^ (V2) | =? 2. Отже,? 2 ^? 2. Тоді з (5) випливає, що

    р (Сь М ^ 2) ^ р (С1, М1) +? 2 (п - щ +? 1 - 3). (6)

    Відповідно до кроком 4 алгоритму А2 покладемо М ^ 2 = МиМ ^ 2, де М-повний граф на безлічі Позначимо через у суму числа відсутніх ребер в підграфі графа С, породжених безліччю вершин ^ і величини розрізу (І, V \ V) в графі С. Очевидно, що

    р (С, М ^ 2) = в + р (С1, М, 2), р (С, М) = в + р (С1, М1).

    Звідси з урахуванням (4) і (6) маємо

    р (С, М ^ 2) = в + р (С1, М ^ 2) ^ в + р (С1, М1) +? 2 (п - щ +? 1 - 3) = = р (С, М) + ? 2 (п - щ +? 1 - 3) ^ р (С, М *) +? 1 (п - 3) +? 2 (п - щ +? 1 - 3),

    т. е.

    р (С, М ^) ^ р (С, М *) +? 1 (п - 3) +? 2 (п - п1 +? 1 - 3). (7)

    Тепер покажемо, що? 2 ^ п1 + п / 2. дійсно,

    ?2 = N ^ 21 = N (V2)) П V *! + N (V2) П (V; і V;!.

    Очевидно, що N (v2) П V *! ^ IV *! = Пь Позначимо = N (v2) П (V * і V *)! і доведемо, що « '^ п / 2. Припустимо гидке: « ' > п / 2. Розглянемо кластерний граф М, отриманий з М * шляхом перенесення вершини v2 з кластера V2 * в кластер V *. Очевидно, що ^ ГГИ V = V2 * і Vз * і графи Б і Б = Б (С, М) відрізняються тільки ребрами виду (і ^ 2), де і Е V2 * і V3 *, інші ребра у них збігаються. отже,

    р (С, М) - р (С, М *) = Nи П (V * і V;)! - Nи П (V; і V;)!.

    Так як

    N5 (V2) П (V; і V;) = (V * і V;) \ ({V2} U N0 (V2)) = (V, і V *) \ (({V2} U N0 (V2) ) П (V * і V;)),

    отримаємо

    N (V2) П (V; і V *)! - NИ П (V; і V *)! = (П - п - - 1) - = п - п - 2 ^ '- 1.

    за припущенням, > п / 2, тому р (С, М) - р (С, М *) < -п1 - 1 < 0, що суперечить оптимальності кластерного графа М *. Отже, ^ п / 2, звідки

    ?2 ^ п1 + п / 2. (8)

    Оцінимо складові з правої частини нерівності (7) з урахуванням (8), леми 3 і нерівності ^? 2.

    а) Дамо оцінку суми р (С, М *) +? 1 (п - 3):

    р (С, М *) +? 1 (п - 3) = р (С, М *) +? 1п (1 - 3 / п) ^ ^ р (С, М *) + 2р (С, М *) (1 - 3 / п) = (3 - 6 / п) р (С, М *).

    б) Оцінимо доданок d2 (n - n + d1 - 3):

    d2 (n - n1 + d1 - 3) = d1n1 - d1 n1 + d2 (n - n1) + d1d2 - 3d2 ^ ^ 2p (G, M *) - d1n1 + d1 d2 - 3d2 ^ 2p (G, M *) - d1n1 + d1 (n1 + n / 2) - 3d2 = = 2p (G, M *) + dm / 2 - 3d2 ^ 2p (G, M *) + dm / 2 - 3d1 = = 2p (G, M * ) + dm / 2 (1 - 6 / n) ^ 2p (G, M *) + p (G, M *) (1 - 6 / n) = (3 - 6 / n) p (G, M *).

    Отже,

    p (G, MvXv2) ^ (6 - 12 / n) p (G, M *).

    На кроці 4 алгоритмом A2 серед всіх графів Muv буде, зокрема, розглянуто і граф MVlV2. Звідси виходить необхідна оцінка точності алгоритму A2. |

    3. Обчислювальний експеримент

    Для порівняння точності наближених алгоритмів Ai і A2 проведений обчислювальний експеримент. Досліджено також алгоритм A3, що є модифікацією алгоритму A2 (в ньому до наближеного рішення, отриманого алгоритмом A2, застосовується процедура локального пошуку). Очевидно, що алгоритм A3 поліноміален і його гарантована оцінка точності не гірше, ніж гарантована оцінка точності алгоритму A2. Всі алгоритми реалізовані на мові програмування C + - + в середовищі JetBrains Clion 2017.3.3. Обчислення проводилися на персональному комп'ютері моделі RT I5N з процесором Intel Core i5-2400, тактовою частотою 3,10 ГГц і об'ємом оперативної пам'яті 8 Гбайт.

    Опишемо клас графів, на яких вироблялися обчислення. Зафіксуємо параметр p? (0,1), випадковий n-вершинний граф G = (V, E) будемо отримувати з використанням наступної процедури. Для кожної пари вершин (u, v) проводиться незалежний випадковий експеримент, результатом якого є наявність ребра uv з ймовірністю p і відсутність ребра з вірогідністю 1 - p. В [15, 16] сімейство n-вершинних графів з таким розподілом позначається G (n, p) і використовується як при теоретичному вивченні графів, так і в експериментальних дослідженнях (модель Ердеша - Рен `ї).

    Параметр p є математичне очікування щільності випадкового графа G = (V, E), яка визначається як 2 | E | / (n (n - 1)). У проведених експериментах використовувалися значення p? {0,33, 0,5, 0,67}.

    На графах малої розмірності (при n від 10 до 20 вершин) алгоритмом повного перебору були знайдені точні рішення. Це дозволило отримати попередні відомості про зміну точності алгоритмів в залежності від параметрів n і p. Для кожної пари значень n і p було вирішено по 50 завдань.

    Далі точністю (відхиленням від оптимуму) наближеного алгоритму будемо називати відношення значення цільової функції, отриманого даним алгоритмом, до її оптимального значення. Позначимо через i1 (n, p), i2 (n, p) і $ 3 (n, p) середні точності алгоритмів A1, A2 і A3 для n-вершинних графів при фіксованому значенні параметра p.

    За підсумками першого експерименту найкращі показники належать алгоритму A3: його середнє відхилення від оптимуму досягає максимуму при значеннях параметрів n = 18, p = 0,33 і становить 3,6%, в той час як алгоритми A1 і A2 при тих же параметрах відхиляються на 7,3 і 12,3% відповідно. При всіх інших значеннях параметрів n і p алгоритм A3 також дає рішення з найменшим середнім відхиленням від оптимуму серед досліджуваних алгоритмів (рис. 1).

    Мал. 1. Середня точність наближених алгоритмів при р = 0,33

    Таким чином, найбільш перспективним наближеним алгоритмом можна вважати алгоритм А3. Для підтвердження того, що він продовжує домінувати і при інших значеннях п, був проведений експеримент на графах більшої розмірності (при п від 50 до 250 вершин). Однак в цьому випадку немає можливості знайти оптимальне рішення за прийнятний час, тому в якості досліджуваних були обрані наступні величини:

    Й1 [п, Р) 63 (п, ру й2 [п, р) 53 (п, р) •

    Вибір таких величин пояснюється тим, що, по-перше, їх обчислення не вимагає знання оптимального рішення, а по-друге, вони дозволяють відповісти на питання, чи дійсно алгоритм А3 дає в середньому кращі рішення, ніж алгоритми Ах і А2, на графах більшої розмірності. Для кожної пари значень п і р було вирішено по 100 задач.

    При всіх значеннях п і р величини (п, р) і ^ 2 (п, р) виявилися більше одиниці. При цьому в кожній вирішеною завданню алгоритм А3 дає значення цільової функції не більше, ніж значення цільових функцій, отриманих алгоритмами Ах і А2 (рис. 2). Це дозволяє зробити висновок про те, що алгоритм А3 продовжує домінувати над алгоритмами Ах і А2 незалежно від значень параметрів п і р. При цьому час роботи алгоритмів А2 і А3 з ростом п збільшується досить повільно (менше 1 с при п = 50 і близько 10 з при п = 250). Для алгоритму Ах зростання кількості вершин зробив істотний вплив на час роботи (менше 1 с при п = 50 і близько 800 з при п = 250).

    З результатів обчислювального експерименту можна зробити висновок, що найкращим алгоритмом наближеного рішення задачі ОС ^ 3 є А3: рішення, отримані цим алгоритмом, найбільш близькі до оптимальних, при цьому час його роботи залишається порівняно невеликим при зростанні кількості вершин.

    Мал. 2. Значення величин d1 (n, p) і d2 (n, p) при p = 0,33

    висновок

    В роботі розглядається задача кластеризації графа, в якій число кластерів не перевищує трьох. Запропоновано три поліноміальних алгоритму наближеного вирішення цього завдання. Перший, 6-наближений алгоритм Ai, багаторазово використовує локальний пошук і заснований на ідеях, які застосовуються для вирішення завдання, в якій число кластерів не перевищує двох. Другий алгоритм A2 заснований на оригінальній ідеї і не використовує локальний пошук. Наближений алгоритм A3 є модифікацією другого і відрізняється тим, що до наближеного рішення, знайденого алгоритмом A2, застосовується процедура локального пошуку. Доведено, що алгоритми A2 і A3 мають гарантовану оцінку точності 6 - 12 / n, де n - число вершин кластерізуемого графа.

    ЛІТЕРАТУРА

    1. Kulis B., BasuS., Dhillon I., and Mooney R. Semi-supervised graph clustering: a kernel approach // Machine Learning. 2009. V. 74. No. 1. P. 1-22.

    2. Schaeffer S. E. Graph clustering // Computer Science Review. 2005. V. 1. No. 1. P. 27-64.

    3. Shamir R., SharanR., And Tsur D. Cluster graph modification problems // Discr. Appl. Math. 2004. V. 144. No. 1-2. P. 173-182.

    4. Bansal N., Blum A, and Chawla S. Correlation clustering // Machine Learning. 2004. V. 56. P. 89-113.

    5. Ben-Dor A., ​​Shamir R., and Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. V.6. No. 3-4. P. 281-297.

    6. Krivanek M. and Moravek J. NP-hard problems in hierarchical-tree clustering // Acta Informatica. 1986. V.23. P. 311-323.

    7. Giotis I. and Guruswami V. Correlation clustering with a fixed number of clusters // Theory of Computing. 2006. V. 2. No. 1. P. 249-266.

    8. Агєєв А. А., Ильев В. П., Кононов А. В., Талевнін А. С. Обчислювальна складність завдання апроксимації графів // Дискрет. аналіз і дослідні. операцій. Сер. 1. 2006. Т. 13. №1. С. 3-11.

    9. Coleman T., Saunderson J., and Wirth A. A local-search 2-approximation for 2-correlation-clustering // LNCS. 2008. V.5193. P. 308-319.

    10. Ильев В. П., Ільєва С. Д., Навроцька А. А. Наближені алгоритми для задач апроксимації графів // Дискрет. аналіз і дослідні. операцій. 2011. Т. 18. №1. C. 41-60.

    11. Charikar M., GuruswamiV., And Wirth A. Clustering with qualitative information // J. Comput. Syst. Sci. 2005. V.71. No.3. P. 360-383.

    12. Ailon N., Charikar M., and Newman A. Aggregating inconsistent information: Ranking and clustering // J. ACM. 2008. V. 55. No. 5. P. 1-27.

    13. Chaw la S., Makarychev K., Schramm T., and Yaroslavtsev G. Near optimal LP algorithm for correlation clustering on complete and complete k-partite graphs // STOC'15 Symp. on Theory of Computing. N.Y .: ACM, 2015. P. 219-228.

    14. Il'evV., Il'evaS., And Kononov A. Short survey on graph correlation clustering with minimization criteria // LNCS. 2016. V.9869. P. 25-36.

    15. Ердеш П., Спенсер Дж. Імовірнісні методи в комбінаториці. М .: Мир, 1976.

    16. Alon N. and Spencer J. The Probabilistic Method. N.Y .: Wiley and Sons, 1992.

    REFERENCES

    1. Kulis B., BasuS., Dhillonl., And Mooney R. Semi-supervised graph clustering: a kernel approach. Machine Learning 2009, vol. 74, no. 1, pp. 1-22.

    2. Schaeffer S. E. Graph clustering. Computer Science Review, 2005, vol. 1, no. 1, pp. 27-64.

    3. Shamir R., Sharan R., and Tsur D. Cluster graph modification problems. Discr. Appl. Math., 2004, vol. 144, no. 1-2, pp. 173-182.

    4. BansalN., Blum A., and Chaw la S. Correlation clustering. Machine Learning, 2004, vol.56, pp.89-113.

    5. Ben-Dor A., ​​Shamir R., and Yakhimi Z. Clustering gene expression patterns. J. Comput. Biol., 1999, vol.6, no. 3-4, pp. 281-297.

    6. Krivanek M. and Moravek J. NP-hard problems in hierarchical-tree clustering. Acta Informatica, 1986, vol.23, pp. 311-323.

    7. Giotis I. and Guruswami V. Correlation clustering with a fixed number of clusters. Theory of Computing, 2006, vol.2, no. 1, pp. 249-266.

    8. Ageev A. A., Il'ev V. P., Kononov A. V., and Talevnin A. S. Computational complexity of the graph approximation problem. J. Appl. Indust. Math., 2007, vol. 1, no. 1, pp. 1-8.

    9. Coleman T., Saunderson J., and Wirth A. A local-search 2-approximation for 2-correlation-clustering. LNCS, 2008, vol.5193, pp. 308-319.

    10. Il'evV. P., Il'evaS. D., and Navrotskaya A. A. Approximation algorithms for graph approximation problems. J. Appl. Indust. Math., 2011, vol.5, no. 4, pp. 569-581.

    11. Charikar M., Guruswami V., and Wirth A. Clustering with qualitative information. J. Comput. Syst. Sci., 2005, vol.71, no.3, pp. 360-383.

    12. Ailon N., Charikar M., and Newman A. Aggregating inconsistent information: Ranking and clustering. J. ACM, 2008, vol. 55, no. 5, pp. 1-27.

    13. Chawla S., Makarychev K., Schramm T., and Yaroslavtsev G. Near optimal LP algorithm for correlation clustering on complete and complete k-partite graphs. STOC'15 Symp. on Theory of Computing, New York, ACM, 2015-го, pp. 219-228.

    14. Il'evV., Il'evaS., And Kononov A. Short survey on graph correlation clustering with minimization criteria. LNCS, 2016, vol.9869, pp. 25-36.

    15. Erdos P. and Spencer J. Probabilistic Methods in Combinatorics. Budapest, Academiai Kiado, 1974.

    16. Alon N. and Spencer J. The Probabilistic Method. New York, Wiley and Sons, 1992.


    Ключові слова: ГРАФ /кластеризації /наближені АЛГОРИТМ /ГАРАНТОВАНА ОЦІНКА ТОЧНОСТІ /GRAPH /CLUSTERING /APPROXIMATION ALGORITHM /PERFORMANCE GUARANTEE

    Завантажити оригінал статті:

    Завантажити