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

Question

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

cliques = graph.cliques() 

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

запускает алгоритм Брон-Kerbosch на списке края

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

justTheCliques edge-list > cliques 

Я люблю igraph , и я просто хочу знать, в чем главная причина этого? 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-cliques - это объединения двух (k-1) -кликов, разделяющих все, кроме двух вершин с краем между ними. Я полагаю, что этот алгоритм заметно уступает Bron-Kerbosch на вашем графике. Если вам нужны только максимальные клики, похоже, что .maximal_cliques() использует алгоритм B-K-like.