Re: [igraph] degree sequence game

[Gabor Csardi]

Vincent, the problem with the "simple" method is that it is not proven
that it generates graphs uniformly, ie. giving the same probability 
for each graph (with given degree seq of course) to be generated. I would 
guess that it is easy to prove that it is not uniform. 
So i had benn looking for another way, eg. like this: 
http://arxiv.org/pdf/cond-mat/0312028
It's been a while since i read it but AFAIR they have a uniform 
method.

For the sort of thing you mention, i don't know any general method 
which can condition the graph to some other property as well besides 
the degree sequence. I know some (separate) algorithms which condition
on transitivity, degree correlations, etc. 

So there are no short-term plans for adding new 'method's now,
in general a uniform generator for simple graphs (ie. no loops, 
no multiple edges) would be good.

G.

On Thu, Jun 14, 2007 at 01:45:27PM -0400, Vincent Matossian wrote:
>      Gabor, thanks for the update and all line graph related functions, I
>    haven't used them yet but will definitely soon.
> 
>    I noticed that the degree.sequence.game is parametrized with "method"
>    which is set to "simple" for now. I am curious to know what are the
>    planned additions to extend the function to other aspects of degree
>    sequence generations (any pointers in literature?). I am creating
>    sequences that require the graph to be connected and have other structural
>    properties such as a certain transitivity and/or betweenness, is that what
>    a "not so simple" parameter will be intended for? :)
> 
>    Thanks,
> 
>    Vincent

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK