Почему метод igraph cliques() на несколько порядков медленнее, чем justTheCliques?

Question

Я хотел найти все клики в графе среднего размера, но плотно связанном, имеющем 369 узлов и 22 724 ребер. Сначала я просто назвал igraph's Graph.cliques() Метод через интерфейс Python:

cliques = graph.cliques()

Он все еще работает и потребляет более 3 часов чистого процессора на ядре i7-4600U. Поэтому я начал искать другие возможности и вспомнил хороший код, который уже использовал несколько лет назад. Он называется justTheCliques и доступен здесь: https://github.com/aaronmcdaid/MaximalCliques. В описании сказано:

запускает алгоритм Брон-Кербоша в списке ребер

Запуск этого алгоритма дает результат на том же графике в течение нескольких секунд:

justTheCliques edge-list > cliques

Я люблю igraph, и я просто хочу знать, что является основной причиной этого? Играф использует другой алгоритм? Результат должен быть таким же?

Answer 1

Дэвид прав, если вы хотите максимальное количество кликов, то вы должны использовать maximal.cliques(), Я сделал быстрое сравнение, и кажется, что на самом деле igraph на 4-5 быстрее, чем библиотека C++, которую вы использовали, хотя это, вероятно, зависит от вашего графика:

library(igraph)
g <- erdos.renyi.game(369, 22724, type="gnm")
system.time(xx <- maximal.cliques(g))
#   user  system elapsed 
#  1.432   0.012   1.448 
write.graph(g, format = "edgelist", file = "graph.txt")

vagrant@logus:~/cli/MaximalCliques$ time ./justTheCliques graph.txt  > cliques.txt
Network loaded after 0.15 seconds. 369 nodes and 22724 edges. Max degree is 149
processing node: 100 ...
processing node: 200 ...
processing node: 300 ...
388111 cliques found
0   #3
10367   #4
209815  #5
151633  #6
15896   #7
396     #8
4       #9

real    0m6.419s
user    0m5.324s
sys     0m1.036s

Answer 2

Похоже, что igraph использует алгоритм наподобие apriori для реализации .cliques(), 1-клика - это одиночные вершины. K-клики - это объединения двух (k-1)-кликов, разделяющих все, кроме двух вершин, с ребром между ними. Я предполагаю, что этот алгоритм заметно уступает Брону-Кербошу на вашем графике. Если вам нужны только максимальные клики, это выглядит как .maximal_cliques() использует B- K-подобный алгоритм.