Графы и пути: максимальные группы Брона-Кербоша
Перевод статьи David Pynes: Graphs & paths: Bron-Kerbosch, maximal cliques.
Зачем
Салли проводит вечеринку. 🎉 Она приглашает Макса, Сью, Тома и Джейка. Затем Том приглашает Райана, который приводит Джесс, а Джесс приводит Лу, который знает друзей Тома. Джейк популярен, поэтому Джейк тоже знает Джесс и Райана. А ещё есть Джо. Джо знает Лу, но не знает Салли, да и остальных тоже. Хотя “технически” он всё ещё гость этой вечеринки. Так как наша вечеринка превратилась в непонятно что, то у нас также имеется 3 случайных человека — Лиз, Тай и Джей. А под конец прибывает вечно опаздывающая Эрин вместе с Эми и Джеком.
Наша задача простая — найти максимально подходящие друг другу группы, в которых все знают друг друга.
Для этого мы применим для социальной сети базовый алгоритм Брона-Кербоша, или, если выражаться другими словами, применим к нашей вечеринке рекурсивный поиск с возвратом О(3^n/3).
Что
Полные NP-задачи быстро становятся сложными, поэтому в качестве примера рассмотрим подграф.
Посмотрите на Джека, Эми, Эрин и Салли.
Здесь имеются две максимальные группы: (1) Эми, Джек и Эрин. (2) Салли и Эрин.
Мы достаточно умны для того, чтобы запомнить эти группы. Компьютеры же достаточно мощны для этого, так что остаётся их обучить.
Какие инструкции нам нужно дать компьютеру, чтобы он начал видеть то же, что и мы?
Начнём с выбора узла. Допустим это будет Джек.
Теперь со стороны Джека сделаем рекурсивный вызов, рассматривая только соседей Джека.
Углубляясь, выбираем случайный из соседних Джеку узлов.
Например, Эми.
Углубляясь ещё больше, мы выбираем узел, который является соседом и для Джека, и для Эми.
Таким узлом будет Эрин.
Во множествах выражение «соседи с Джеком и Эми» известно как пересечение.
Теперь, на глубине трёх уровней, находясь на узле Эрика, мы видим, что больше нет интересных нам пересекающихся узлов.
Обратите внимание, что Салли не является членом этой группы, так как он не знает Джека и Эми.
Базовый пример оценивается как истинный. Группа найдена.
Теперь поиск с возвратом и исключение.
Поднимаемся на один уровень вверх.
Мы нашли максимальную группу для соседства Джека и Эми, но может ли быть ещё одна группа в соседстве Джека и Эрин? Может.
В этот раз мы выберем другого соседа Джека — Эрин, а также исключим Эми, проложив таким образом новый путь.
Сейчас мы на глубине двух уровней и проверяем, есть ли соседние узлы, которые пересекаются с Эрин и Джеком.
Это могла бы быть Эми, но Эми исключена из пересечений.
Теперь базовый пример оценивается как ошибочный, потому что теперь нет группы, которая бы пересекалась с исключённым соседом.
Поднимаемся на уровень вверх.
Мы посетили всех соседей Джека. Теперь мы снова поднимаемся выше, на самый высокий уровень.
На самом высоком уровне мы исключаем Джека и выбираем другой случайный узел.
Давайте используем узел Эми в этот раз.
Двигаемся глубже, рассматриваем соседей Эми, которые не были исключены.
Эми знает Эрин.
Двигаемся глубже и проверяем совместных соседей Эми и Эрин.
Единственным подходящим узлом является Джек, но он исключен, а значит максимальной группы здесь не будет.
Поиск с возвратом: возвращаемся на верхний уровень.
Теперь у нас два исключения — Эми и Джек. Теперь наш поиск продолжается вместе со следующим случайным узлом.
Давайте выберем Эрин.
Эрин рассматривает своего не-исключённого соседа — Салли.
Салли выбрана, рекурсия движется глубже и поиск продолжается.
Оценка базового примера.
(1) Есть ли ещё хоть какие-нибудь дополнительные узлы, которые пересекаются с этим соседством? Нет.
(2) Есть ли ещё хоть какие-нибудь исключённые узлы, которые пересекаются с этим соседством? Нет.
Обратите внимание, что хоть Салли и связана с Эрин, она не связана с Джеком и Эми, поэтому эти узлы не пересекаются.
Мы получили группу.
Теперь мы делаем поиск с возвратом.
Так как Эрин больше ни с кем не связана, то она заносится во множество исключённых узлов (вместе с Джеком и Эми).
Салли связана только с Эрин, а Эрин исключена.
Теперь исключаем Салли.
Больше не осталось никого для исключения. Алгоритм завершён.
Как
Брон-Кербош оперирует с тремя множествами: R, P и X.
R := это множество из узлов максимальной группы.
P := это множество из возможных узлов в максимальной группе.
X := это множество исключённых узлов.Брон-Кербош выполняет следующие операции со множествами R, P и X:
R ⋃ {v} := объединение между R и единичным множеством v.
P ⋂ N(v) := пересечение между P и соседями v.
X ⋂ N(v) := пересечение между X и соседями v.
P \ {v} := разность P и единичного множества v.
X ⋃ {v} := объединение между X и единичным множеством v.Псевдо-код:
BronKerbosch1(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch1(
R ⋃ {v},
P ⋂ N(v),
X ⋂ N(v)
)
P := P \ {v}
X := X ⋃ {v}Подробнее об обозначениях множеств:
ПРИМЕР ОБЪЕДИНЕНИЯ:
Узлы, которые принадлежащие к множеству A или B.
A = {Jack, Amy}
B = {Jack, Sally, Erin}
A ⋃ B = {Jack, Amy, Sally, Erin}ПРИМЕР ПЕРЕСЕЧЕНИЯ:
Узлы, которые принадлежат как множеству A, так и множеству B.
A = {Jack, Amy}
B = {Jack, Sally, Erin}
A ⋂ B = {Jack}ПРИМЕР РАЗНОСТИ:
Узлы, которые принадлежат множеству А и не принадлежат множеству B.
A = {Jack, Amy}
B = {Jack, Sally, Erin}
A \ B = {Amy}
Переводим псевдо-код в код С++:
void bronKerbosch(set<node*> R, set<node*> P, set<node*> X) {
if(P.empty() && X.empty()) {
cout<<"Clique found: ";
set_print(R);
}
set<node*>::iterator v = P.begin();
while(!P.empty() && v!=P.end()){
set<node*> singleton = { (*v) };
bronKerbosch(
set_union(R,singleton),
set_intersection(P,(*v)->friends),
set_intersection(X,(*v)->friends));
P = set_difference(P,singleton);
X = set_union(X,singleton);
if(!P.empty())
v = P.begin();
}
}- Скопируйте этот код в текстовый редактор и сохраните как
main.cpp - Скомпилируйте из командой строки,
g++ main.cpp -std=c++11 -o Bronker.exe - Затем выполните код из командной строки,
./Bronker.exe
После компилирования и выполнения исходного кода, программа сгенерирует вечеринку 🎉 и выведет максимальные группы.
Код
Просмотреть полный C++ код вы можете здесь.
Создать максимальные группы через веб-приложение здесь.
