qp.get.cliques {qp} | R Documentation |
It finds the set of cliques, i.e. maximal complete subsets of vertices, of an undirected graph taken as an incidence matrix.
qp.get.cliques(I, binary=TRUE)
I |
incidence matrix |
binary |
flag to switch to the compiled C code |
It uses the algorithm described in Bron and Kerbosch (1973) and returns a list where each member is a vector of vertices forming a clique in the given graph. Beware that the problem of finding the set of cliques is NP-hard and the time of computation of this algorithm grows exponentially in the graph density.
Robert Castelo and Alberto Roverato
Castelo, R. and Roverato, A. (2006). A robust procedure for Gaussian graphical model search from microarray data with p larger than n, J. Mach. Learn. Res., accepted
Bron, C. and Kerbosch, J (1973). Finding all cliques of an undirected graph, Commun. ACM, 16:575–577
data(jmlr06data) I <- qp.graph(qp.out.bd5.N20.q10,threshold=0.9) cliquelist <- qp.get.cliques(I) sprintf("the graph has %d cliques\n",length(cliquelist))