Re: Maximal Clique

[Rodrigo Lins <lins.oliveira AT gmail.com>]

Thanks all for your effort!
In my test take about 8 seconds to find the maximum clique with 140 nodes, and the maximum clique have 28 nodes.
Thanks a lot for your algorithm Stefan!

Cheers,
Rodrigo.

On Mon, Jun 20, 2011 at 1:48 PM, Stefan Balev <stefan.balev AT gmail.com> wrote:

Hi again,

Just a small optimization. Add the following instruction at the beginning of enumerateCliques method:

    if (currentClique.size() + candidates.size() <= bestClique.size())

        return;

It stops the search if the currently constructed clique cannot be better than the best found so far.

Good luck,

--

Stefan

2011/6/20 Rodrigo Lins <lins.oliveira AT gmail.com>

Thanks Julien and Stefan
I'll try to find the maximum cliques and i'll post the results.

Thanks a lot for your help!
Rodrigo.

On Mon, Jun 20, 2011 at 11:51 AM, Stefan Balev <stefan.balev AT gmail.com> wrote:

Hi Rodrigo,

Here is a "quick and dirty" implementation. Basically it consists in
enumerating all the cliques and keeping the best found. As Julian, I
think that it is hopeless for the size of your graphs, but you can
give it a try.

Cheers,

--
Stefan

2011/6/20 Rodrigo Lins <lins.oliveira AT gmail.com>:

> Hi Julien,
> You can do this algorithm?
> In my project, i use all active stock (140 stocks) in BOVESPA (a stock
> exchange from Brazil).
> And i use an algorithm to find the Pearson Product Momentum between all
> stocks. Every stock represent an node in my graph and If the PPM > than a
> empirical value, i put a vertice between this nodes. Then i need to find the
> maximum cliques and plot this graph.
> I'm already calculating the PPM. Now, i need to calculate the maximal clique
> and plot a graph.
>
> Thanks for all,
> Rodrigo.
>
> On Mon, Jun 20, 2011 at 10:21 AM, julien schleich <julien.schleich AT uni.lu>
> wrote:
>>
>>
>> Thanks Frederic,
>> My graph have at the maximum 140 nodes and 140*140 vertices.
>>
>> With this size of graphs, I would give up finding an optimal solution.
>> Really.
>>
>> The computational effort it's no a problem. I need only to make an image
>> with the graph.
>> I have found this implementation
>> (http://code.google.com/p/jung/issues/attachmentText?id=2&aid=20000001&name=BronKerboschCliqueFinderTest.java&token=7f10e4f3acb29d35ffa92a2744dfc3ca)
>> but i'm using the Graph Stream graph objects and i dont want to use the
>> JUNG framework.
>> If you can make an implementation of this algorithm i'll be very happy!
>> Thanks for your patience and your help!
>> If you can't do this, let me know, and I will try to use a JUNG or make an
>> implementation!
>>
>> Thanks a lot,
>> Rodrigo.
>>
>> 2011/6/20 Frédéric Guinand <frederic.guinand AT gmail.com>
>>>
>>> Hello Rodrigo,
>>>
>>> What is the size of your graph(s)?
>>>
>>> I can try to implement a quick'n'dirty algo if you really need this
>>> urgently.
>>>
>>>
>>>     Frederic
>>>
>>>
>>> Rodrigo Lins wrote:
>>>>
>>>> Hi Stefan,
>>>> I need only to find a maximum cardinality.
>>>> I mount the graph based in a correlation algorithm.
>>>> I`m looking for a implemented algorithm or if the graph stream have one
>>>> implementation.
>>>>
>>>> Thanks a lot,
>>>> Rodrigo.
>>>>
>>>> On Sun, Jun 19, 2011 at 5:56 PM, Stefan Balev <stefan.balev AT gmail.com
>>>> <mailto:stefan.balev AT gmail.com>> wrote:
>>>>
>>>>    Hi Rodrigo,
>>>>
>>>>    If you can wait, just use a brute force approach. Is your graph
>>>>    weighted or you just want to find a maximum cardinality clique ?
>>>>
>>>>    Cheers,
>>>>
>>>>    --
>>>>    Stefan
>>>>
>>>>
>>>>    2011/6/19 Rodrigo Lins <lins.oliveira AT gmail.com
>>>>    <mailto:lins.oliveira AT gmail.com>>:
>>>>     > Thanks Frederic for your answer.
>>>>     > But I really need to find de cliques in a graph, and I know this
>>>>    algorithm
>>>>     > is a NP-Hard problem.
>>>>     > I realy need to find the maximum cliques in a graph. I can wait.
>>>>     > Thanks,
>>>>     > Rodrigo.
>>>>     >
>>>>     > 2011/6/19 Frédéric Guinand <frederic.guinand AT gmail.com
>>>>    <mailto:frederic.guinand AT gmail.com>>
>>>>     >>
>>>>     >> Hello Rodrigo,
>>>>     >>
>>>>     >> The problem of finding the maximum clique in a graph is an
>>>> NP-Hard
>>>>     >> problem. In other words, it is not possible to do so in a
>>>>    reasonable time
>>>>     >> (polynomial in the size of the graph). So, any method for
>>>>    finding a maximum
>>>>     >> clique is equivalent to use a brute force approach.
>>>>     >>
>>>>     >> If you want to know more:
>>>>     >>
>>>>     >> http://en.wikipedia.org/wiki/NP-complete
>>>>     >> http://en.wikipedia.org/wiki/Clique_problem
>>>>     >>
>>>>     >> What was the original problem you try to deal with?
>>>>     >>
>>>>     >>     Bye,
>>>>     >>
>>>>     >>         Frederic
>>>>     >>
>>>>     >>
>>>>     >> Rodrigo Lins wrote:
>>>>     >>>
>>>>     >>> Anyone knows if it is possible to find a maximal clique in a
>>>>    graph using
>>>>     >>> GraphStream?
>>>>     >>> If it is possible what class do it?
>>>>     >>>
>>>>     >>> Thanks a lot!
>>>>     >>> Rodrigo.
>>>>     >
>>>>     >
>>>>
>>>>
>>
>>
>
>