GraphStream Users

Archives de la liste Aide


Re: Maximal Clique


Chronologique Discussions 
  • From: Rodrigo Lins <lins.oliveira AT gmail.com>
  • To: graphstream-users AT litislab.fr
  • Cc: "<frederic.guinand AT gmail.com>" <frederic.guinand AT gmail.com>
  • Subject: Re: Maximal Clique
  • Date: Mon, 20 Jun 2011 11:17:24 -0300
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=WpL9ZKTuJRZpfH2QesWHbAIYsrzY1+PTuSyW6MIOIT8yeQ+ndHx0AxDqss7NUyt10i d9Xst9IUkM5i107xs11H3okf8ECKPJIhGYOGRyP87GVlJMIr8eV3RerOtleJurirNLOW 1KKwFRAmUQEH6UTgrCUsyygSvgVwJhq1C66/4=

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@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.
    >
    >








Archives gérées par MHonArc 2.6.16.

Top of page