Re: [igraph] Algorithm for maximal.cliques in R

[Tamas Nepusz]

> I am running some comparisons of network analysis packages and am  
> curious as to how igraph is calculating maximal cliques in R?
Are you using igraph 0.5.2 or igraph 0.6? I have to admit that the  
approach taken by igraph 0.5.2 and older versions is... hmmm... at  
least suboptimal ;) Basically, maximal.cliques takes the complementer  
of the graph (every edge becomes a non-edge and vice versa) and looks  
for maximal independent vertex sets in the complementer -- this is due  
to the fact that we already had a function for maximal independent  
vertex sets, but we didn't have a routine for maximal cliques. In the  
0.6 tree, I added the Bron-Kerbosch algorithm, which should be _much_  
faster. The algorithm is implemented in C, so all the number crunching  
is done in the C layer, not in R.

Best,
--
Tamas