3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 7
    $\begingroup$ I would guess that there is no known algorithm which works in reasonable amount of time with every graph with that many vertices and edges. Therefore, if there is an algorithm which works fast enough with your graph, it must depend on the details of your graph. This means that whether a particular algorithm is “better” or not depends on the information you did not provide in the question. $\endgroup$
    – Tsuyoshi Ito
    Commented May 1, 2011 at 21:07
  • 1
    $\begingroup$ Depending on the structure of the graph, the algorithm in the paper of Jennifer Debroni, Wendy Myrvold, myself et al recently in SODA might have a shot at finding them. What it needs to work well is related to why the maximal cliques in your graph have at most 17 vertices. $\endgroup$
    – Peter Shor
    Commented May 7, 2011 at 2:38

5 Answers 5

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Note that only about 34.6% of all possible edges exist in the graph. So, if the graph is similar to a graph generated by choosing uniformly among all edges (note, this is a big assumption) then each set of 17 nodes has probability of about $2.6 \times 10^{-63}$ of being a clique. As such, it's likely that the problem will not be listing the cliques, but rather verifying that one does not exist. $\endgroup$
    – bbejot
    Commented May 2, 2011 at 4:25
  • 1
    $\begingroup$ Yes, but it is impossible to tell without more info. $\endgroup$
    – Joe Fitzsimons
    Commented May 2, 2011 at 14:34
10
$\begingroup$

Eppstein and Strash (2011) show that for a graph $G$ with degeneracy $d$ all maximal cliques can be listed in time $O(dn3^{d/3})$, where the degeneracy is the smallest number such that every subgraph of $G$ contains at least one vertex of degree $d$. The degeneracy is usually small, and in their paper they provide experimental results on graphs of comparable size, so you may be able to solve your problem using their algorithm.

D. Eppstein, D. Strash, Listing All Maximal Cliques in Large Sparse Real-World Graphs, 10th International Conference on Experimental Algorithms, 2011.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that it is easy and fast to obtain all 17-cliques from maximal cliques -- if they are not too big! On $K_n$, you are back to the old problem. But then, why list all 17-cliques if you have a much more concise representation for them? $\endgroup$
    – Raphael
    Commented May 2, 2011 at 5:50
  • 8
    $\begingroup$ Thanks, but our algorithm is intended primarily for graphs in which the numbers of edges and vertices are relatively close to each other. It doesn't sound like that is the case here. $\endgroup$
    – David Eppstein
    Commented May 2, 2011 at 15:07
  • 1
    $\begingroup$ @David: I see; having minimum degree 2000, the above graph will have $d\geq 2000$. $\endgroup$
    – Marcus Ritt
    Commented May 3, 2011 at 10:50
8
$\begingroup$

Give Cliquer a try.

http://users.tkk.fi/pat/cliquer.html

It's true your graph is huge, but sometimes it works. And it doesn't take long to try it as this software is already (and well) coded :-)

Nathann

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Yes. Cliquer to the rescue. Take your graph and split it into 8,568 graphs; one for each node and it's neighbors. Also, as you make a graph for each node and it's induced neighborhood remove it from the super graph; thus the problem graphs will get smaller and smaller as you go. Also, do some pre-cleaning by iteratively removing all nodes in these smaller graphs that do not have 16 neighbors. $\endgroup$
    – Chad Brewbaker
    Commented May 6, 2011 at 21:28
1
$\begingroup$

The 1985 paper by Nešetřil and Poljak linked in this answer to a similar question suggests that you can search for the subgraph $K_{3\ell+i}$ in time $O(n^{i+\ell ω})$, where $ω$ is the matrix multiplication constant. Wikipedia says only Strassen’s algorithm with $ω \approx 2.807$ is usable in practice. This would give you roughly $O(n^{14.037})$ for finding your $K_{17}$, I believe.

Probably still not useful to solve your actual problem, but at least “better” than the naive $O(n^{17})$…

Improve this answer
$\endgroup$
-3
$\begingroup$

I'm not seeing why the CLRS (p. 617) version of Strongly-Connected-Components() doesn't solve your problem. And it's just 2 DFS's to find all cliques of any size. So, when you're done, you just restrict the result set to those cliques with 17 vertices. That's just O(n + k) because DFS is the limiting factor. The structure of your graph might also make your idea of deleting vertices of degree 16 a nice way to speed things up. 2 DFS's on 12.8M edges certainly is likely not going to be blazingly fast, but I would think it would be doable in a reasonable amount of time. I'm unfortunately not seeing how you could multi-thread it. I've got some Java code that does a DFS and stronglyConnectedComponents() if you think it might be of use to you (my email: [email protected]; and please do email me if you're interested, as I'd be interested to see how my code works on something that big!). Or am I misunderstanding the problem altogether? (if so, my apologies)

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ A clique is not the same thing as a strongly connected component. $\endgroup$
    – Dave Clarke
    Commented May 2, 2011 at 8:16
  • $\begingroup$ tx, now i see what the difference is. $\endgroup$
    – marshallf
    Commented May 2, 2011 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.