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

[Gábor Csárdi]

Actually if you are using R, I am not sure that the R interface uses
the new maximum clique algorithm.... sorry, no time right now to look
it up.... G.

On Mon, Nov 2, 2009 at 9:39 PM, Andrew Conway <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM