|
From: | Tamas Nepusz |
Subject: | Re: [igraph] Algorithm for maximal.cliques in R |
Date: | Mon, 2 Nov 2009 20:35:15 +0000 |
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
[Prev in Thread] | Current Thread | [Next in Thread] |