Finding cliques in a big graph I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.

The algorithm should be fast, because of the size of the graph.

I had the following idea:


Delete all vertices with a degree of 16 or less.
Iterate over every vertex

try to add another vertex:

If the clique has exactly 17 vertices: Add it to a list
Else: Keep trying to add vertices

If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.



I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?
These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.

Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.

So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.