Timeline for Which algorithm does Mathematica use for FindClique?
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2020 at 18:00 | history | tweeted | twitter.com/StackMma/status/1256644630826889218 | ||
| May 2, 2020 at 1:26 | comment | added | kglr | @Szabolcs, very good point. I don't. | |
| May 2, 2020 at 1:23 | history | edited | J. M.'s missing motivation♦ |
edited tags
|
|
| May 1, 2020 at 18:18 | comment | added | Szabolcs |
@kglr Do you have any evidence that that is the function that FindClique is actually using? FindClique's definition is hidden. It may not be using InternalFindClique. InternalFindClique may be an unrelated experimental implementation. Notably, InternalFindClique seems to ignore the size argument. So I don't think this is what FindClique really uses ...
|
|
| May 1, 2020 at 18:13 | history | edited | Szabolcs | CC BY-SA 4.0 |
added 10 characters in body; edited title
|
| May 1, 2020 at 17:54 | answer | added | Szabolcs | timeline score: 3 | |
| May 1, 2020 at 17:33 | comment | added | Kiril Danilchenko | @Szabolcs Thank you for your comments and the ranks that you give to my question. In this case, I can't use IGraph/M. | |
| May 1, 2020 at 17:31 | comment | added | Kiril Danilchenko | @Juho Thank you. I look for the maximal cliques solver | |
| May 1, 2020 at 17:14 | comment | added | Szabolcs |
@KirilDanilchenko There are three separate things here: 1) what problem does FindClique solve? 2) How does it solve it? 3) How can on solve that problem, in general? (1) is relevant, (3) is also a useful thing to ask, but not for this QA site. (2) is on-topic, but in my opinion quite pointless to ask. If you insist anyway, realistically, your options are what kglr said (read the code) or to ask Wolfram Support. I predict they will not give you any satisfactory answer though. If you want to use a program whose implementation is completely open and documented, I recommend IGraph/M.
|
|
| May 1, 2020 at 17:10 | comment | added | Szabolcs |
@Juho FindClique[g] does in fact find a maximum clique.
|
|
| May 1, 2020 at 16:57 | comment | added | Juho | @KirilDanilchenko For which problem? Finding a maximum clique or a maximal clique? If you want maximum cliques, google for pmc. Another solver is cliquer which is older but still solid. | |
| May 1, 2020 at 16:36 | comment | added | Kiril Danilchenko | @Szabolcs I think I didn't explain myself correctly. A maximal clique is one of the steps of the whole solution. To find the maximal clique, I would use WL so I want to understand this function in more detail | |
| May 1, 2020 at 16:27 | comment | added | Kiril Danilchenko | @Juho Can you suggest a good solver of this problem, where the size of the graph is around 40K nodes and 2-3M edges? | |
| May 1, 2020 at 16:12 | comment | added | Juho |
@KirilDanilchenko First, you don't have to use a heuristic to find a maximum cliques. Indeed, there are very good exact solvers for the problem. Second, IIRC, FindClique just finds a maximal clique but there's no guarantee a larger clique wouldn't exist.
|
|
| May 1, 2020 at 15:44 | comment | added | Szabolcs | It seems to me that then the right thing to research is how to find maximal cliques, not how Mathematica does it specifically. | |
| May 1, 2020 at 10:43 | comment | added | Kiril Danilchenko | @Szabolcs I want to know which algorithm WL uses to compute a maximal clique. The reason for that is straightforward. I'm planning to use it as one of the phases of the solution of a "big" problem. Before to use it as a "black box" I prefer to understand the prof and con of the "black box." | |
| May 1, 2020 at 10:36 | comment | added | kglr | @Szabolcs, the code is not too long and it looks like the core method is just LP. | |
| May 1, 2020 at 10:24 | comment | added | Szabolcs | @kglr I don't think that spelunking will give a productive answer to this question. I really wonder if OP wants to know the specific algorithm Mathematica uses, or if he just wants to know how to find maximal cliques, e.g. en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm | |
| May 1, 2020 at 10:16 | comment | added | kglr |
try PrintDefinitions[GraphComputation`InternalFindClique] and click on the link to get the notebook that gives definition of findClique.
|
|
| May 1, 2020 at 10:13 | comment | added | Szabolcs | Why do you want to know? (It's a serious question.) | |
| May 1, 2020 at 10:11 | comment | added | Kiril Danilchenko |
@kglr In WL 12.1, I get an error. FindClique[g] finds the largest clique in the graph g. Is it means finding a maximum clique or something else? If yes, it is an NP problem, and to solve it, we have to use a heuristic solution, which one WL uses for that?
|
|
| May 1, 2020 at 9:48 | comment | added | kglr |
you can see the definition of the function called by FindClique using Needs["GeneralUtilities`"]; PrintDefinitions[GraphComputation`GraphCliqueDump`findClique]
|
|
| May 1, 2020 at 9:23 | history | asked | Kiril Danilchenko | CC BY-SA 4.0 |