[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [igraph] Random Graph Genereation

**From**: |
Gabor Csardi |

**Subject**: |
Re: [igraph] Random Graph Genereation |

**Date**: |
Tue, 29 Apr 2008 10:44:11 +0200 |

**User-agent**: |
Mutt/1.5.13 (2006-08-11) |

Gang, personally i don't know any algorithms that
generate a graph with a given modularity (apart from the trivial ones,
like trees and full graphs), conditioning on the
degree distribution or not.
If someone can point out one, i would be more than
happy to put it into igraph.
Btw, there is this:
http://arxiv.org/abs/physics/0608255
They show an algorithm that can calculate modularity
exactly (without doing brute-force).
It is (obviously) quite slow, but it works
for graphs with a couple of ten vertices, maybe more.
It is based on integer programming, you can use the
GLPK (http://www.gnu.org/software/glpk/) to "implement"
it.
Best,
G.
On Mon, Apr 28, 2008 at 08:39:23PM -0400, Gang Su wrote:
>* Dear developers,*
>* *
>* Is there any algorithms that could be used to generate a random graph *
>* with known modularity?*
>* Newman has tested the community detection algorithms on a 4 cluster *
>* model, is there any algorithms that can be used to generate larger *
>* networks with known modularity,*
>* but with defined edge degree distribution(power law)?*
>* *
>* Thanks*
>* *
>* Gang*
>* *
>* *
>* _______________________________________________*
>* igraph-help mailing list*
>* address@hidden*
>* http://lists.nongnu.org/mailman/listinfo/igraph-help*
--
Csardi Gabor <address@hidden> UNIL DGM