Counting all cliques of a given size in an undirected graph
Dear all Boost users, I need to count all cliques of a given size in an undirected graph. I am using Boost Graph and I have found the Bron-Kerbosch algorithm implemented in version 1.53 but not documented. My question is two-fold: 1) why the algorithm is somehow hidden? 2) Is this algorithm able to count the occurrencies of cliques of a certain dimension or just the maximal cliques? Best, Andrea Cassioli
On Mon, 1 Jul 2013, Andrea Cassioli wrote:
Dear all Boost users, I need to count all cliques of a given size in an undirected graph. I am using Boost Graph and I have found the Bron-Kerbosch algorithm implemented in version 1.53 but not documented. My question is two-fold:
1) why the algorithm is somehow hidden?
There does not appear to be a documentation page for it, so it's likely one hasn't been written. It is not hidden on purpose otherwise.
2) Is this algorithm able to count the occurrencies of cliques of a certain dimension or just the maximal cliques?
It looks like it only finds maximal cliques that are over the size that you specify. You could get all cliques over a certain size n by enumerating all maximal cliques of size >=n, then choosing all size-n subsets of vertices of the maximal clique. -- Jeremiah Willcock
2) Is this algorithm able to count the occurrencies of cliques of a certain dimension or just the maximal cliques?
I am not familiar with boost implementation, but as far as I am concerned, the algorithm finds the maximum clique in a greedy way. Hence to find subgraph with clique number k one have to find a subgraph with clique number k-1. So, the algorithm "knows" about cliques you are looking for. As a workaround you can change the implementation to make it capable of enumerating all cliques in a graph. I dont think it is a hard task. -- Regards, Stas.
participants (3)
-
Andrea Cassioli -
Jeremiah Willcock -
Stanislav Ivochkin