Cliques and clique communities

[david-crespo]

I'd like to try and implement the very neat k-clique communities algorithm used in NetworkX. But that relies on a general clique-finding algorithm. The first pass at that might as well imitate Boost's implementation of Bron-Kerbosch. If I can't get that to work, I'll try NetworkX's implementation and we can worry about optimization later.

Does that sound all right?

[lindahua]

It sounds a great idea to me.

[gaborcsardi]

I found that this heuristics makes finding maximal cliques much faster: http://arxiv.org/abs/1006.5440.

[david-crespo]

I have what I believe to be a working version of networkx's find_cliques here. However, on a large graph (~50k nodes, ~1M edges) performance is noticeably terrible — probably over 100x worse than networkx.

Since the algorithm is based around one big while loop, it's not obvious how to optimize. I wonder whether some of my constructors are slow, or whether putting in stricter typing might give a performance benefit. The code is still very much in the style of Python.

[kmsquire]

I would try parametrizing your Dict and Set constructors.

[lindahua]

What about you make a pull request with your codes? We may probably provide some help in improving the efficiency.

[pozorvlak]

It looks to me like this breaks down into the following tasks:

• [x] Implement a general clique-finding algorithm - merged in #62.
• [ ] Profile and speed up maximal_cliques, possibly using the heuristics in the paper @gaborcsardi linked to.
• [ ] Implement a k-cliques algorithm that uses maximal_cliques to find the initial set of cliques.

Anyone want to have a go at the open tasks?