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

[Andrew Conway]

Tamas,

Thank you. It appears that in my original test I was using 0.5.2, but now am running 0.6.  I will update my metrics and note the C layer.

Thank you!

- Drew

On Nov 2, 2009, at 3:35 PM, Tamas Nepusz wrote:

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



_______________________________________________
igraph-help mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help

___________________________________

Drew Conway

Ph.D. Student

Department of Politics, New York University

address@hidden

http://www.drewconway.com/zia

@drewconway