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

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

cliques = graph.cliques()

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

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

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

justTheCliques edge-list > cliques

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


graph algorithm igraph clique clique-problem
person deeenes    schedule 03.09.2014    source источник
comment
В igraph graph.cliques() перечисляет все клики в графе, а justTheCliques перечисляет только максимальные клики. Если вам нужно только максимальное количество кликов, используйте graph.maximal_cliques(), который должен быть таким же быстрым, как и justTheCliques. Размер вывода graph.cliques() экспоненциально больше, поэтому неудивительно, что его вычисление занимает намного больше времени.   -  person Tamás    schedule 04.09.2014

Ответы (2)


arrow_upward
1
arrow_downward

Дэвид прав, если вы хотите максимальное количество кликов, вам следует использовать 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
person Gabor Csardi    schedule 04.09.2014
comment
Спасибо за хорошее сравнение, тогда я буду использовать maximal_cliques() igraph. - person deeenes; 05.09.2014

arrow_upward
2
arrow_downward

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

person David Eisenstat    schedule 03.09.2014
comment
Вы правы, метод igraph maximal_cliques() использует Брон-Кербоша, поэтому он должен быть намного быстрее, чем cliques(). - person Tamás; 04.09.2014
comment
спасибо за объяснение, теперь я понимаю, почему это занимает гораздо больше времени - person deeenes; 05.09.2014