igraph의 cliques() 메소드 순서가 justTheCliques보다 느린 이유는 무엇입니까?

Question

369 개의 ​​노드와 22,724 개의 가장자리를 가진 중형의 크기가 크고 밀도가 높은 모든 그래프를 찾고 싶었습니다. 파이썬 인터페이스를 통해 우선 단순히라는 igraph의 Graph.cliques() 방법 :

cliques = graph.cliques() 

아직 실행중인 및 i7-4600U 코어보다 3 시간 순 CPU 시간을 소비했다. 그래서 나는 다른 가능성을 돌보고 몇 년 전에 이미 사용한 멋진 코드를 기억했다. 그것은 justTheCliques라고 불리며 여기에서 사용할 수 있습니다 : https://github.com/aaronmcdaid/MaximalCliques. 설명은 말한다 :

이

justTheCliques edge-list > cliques 

내가 사랑하는 igraph :

는 에지리스트

에 브론 - Kerbosch 알고리즘이 알고리즘을 실행하면 몇 초 내에서 동일한 그래프에 결과를 제공을 실행 , 그리고 나는이 사실을 알기를 원합니다.이 뒤에있는 근본적인 이유는 무엇입니까? 이 그래프는 다른 알고리즘을 사용합니까? 결과는 동일해야합니까?

Answer 1

David가 맞습니다. 최대한의 파벌을 원한다면 maximal.cliques()을 사용해야합니다. 나는 빠른 비교를했고, 아마 당신의 그래프에 달려 있지만, 그 igraph, 당신이 사용하는 C++ 라이브러리보다 더 빨리 사실 4-5 인 것 같다 ', igraph에서

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) 개의 파생물의 결합체이다. 나는이 알고리즘이 당신의 그래프에서 Bron-Kerbosch보다 현저하게 열등하다고 가정합니다. 최대의 파벌 만 필요로한다면 .maximal_cliques()은 B - K와 같은 알고리즘을 사용하고있는 것처럼 보입니다.