(Oh, i'm stupid, i wanted to post the message below to the list. )

Anyway, i checked randomNodeGraph() and it essentially uses the same
algorithm as igraph.

Gabor

On Thu, Apr 24, 2008 at 4:10 PM, Gábor Csárdi <csardi.gabor@gmail.com>
wrote:

> Robert,
>
> I definitely acknowledge the hard work you put into 'graph' and all the
> other packages on CRAN and/or in Bioconductor, and of course into R itself.
> The same applies to all the developers. I did not intend my remark to be
> negative, i'm sorry if it ended up so. Btw. the same (negative?) remark
> applies to the graph generator in the 'igraph' package, which is my work, I
> know that this generator is biased. (In case this makes my situation any
> better....)
>
> Just to make this thread a bit more useful. Do you know what algorithm
> randomNodeGraph uses?
> 'degree.sequence.game' in 'igraph' does the following: it attaches
> 'half-edges' to every vertex, the number of
> 'half-edges' is the prescribed degree for that vertex. Then it selects
> pairs of 'half-edges' and merges them into
> real edges. The problem with this is that 1) it can generate looops, 2) it
> can generate multiple edges and 3) it is biased.
>
> Does randomNodeGraph() do kind of the same?
>
> Best,
> Gabor
>
>
> On Thu, Apr 24, 2008 at 3:57 PM, Robert Gentleman <rgentlem@fhcrc.org>
> wrote:
>
> > Hi Gabor,
> >  It is clear to me, but a lot of people have invested their time and
> > effort into writing the graph package and related software. They deserve
> > much better consideration than an off-the-cuff disparaging remark about
> > their work. In my view, you should be a little more careful about such
> > statements.
> >
> >  best wishes
> >   Robert
> >
> >
> > Gábor Csárdi wrote:
> >
> > > Robert,
> > >
> > >
> > > On Thu, Apr 24, 2008 at 3:32 PM, Robert Gentleman <rgentlem@fhcrc.org<mailto:
> > > rgentlem@fhcrc.org>> wrote:
> > > [...]
> > >
> > >
> > >        2) I don't know what algorithm 'randomNodeGraph' uses, but this
> > > is a
> > >        non-trivial
> > >        problem if you want to assign a uniform probability over the
> > >        graphs with the
> > >        given degree
> > >        sequence, see e.g. http://arxiv.org/abs/cond-mat/0312028v1
> > >        'igraph' has a function called 'degree.sequence.game', which
> > >        does the same,
> > >        but uses a
> > >        naive algorithm that 1) generates non-simple graphs and 2)
> > > known
> > >        to be
> > >        biased.
> > >
> > >
> > >     I am not sure how to take this, but since you suggest caution, I
> > >    don't think it is positive.  If you are saying you think our
> > >    algorithm is wrong, then could you at least provide some details on
> > >    why you think that, perhaps an example where it appears to give the
> > >    incorrect output, rather than this sort of unpleasant
> > >    unsubstantiated innuendo?
> > >
> > >
> > > sorry for the misunderstanding, i'm not saying it is wrong. I'm just
> > > suggesting the user to check which algorithm 'graph' uses to generate
> > > these graphs. This is only based on my intuition that since this is a
> > > complex probem, it is unlikely that the ~20 lines implementation in
> > > randomNodeGraph() does it "correctly". But i might be wrong, and sorry
> > > about not checking it out myself.
> > >  By 'correctly' i mean that it generates all graphs with the given
> > > degree sequence with equal probability. Obviously, sometimes this
> > > 'correctness' is not needed and in these cases randomNodeGraph() is great. I
> > > hope it is clearer now.
> > >
> > > Best,
> > > Gabor
> > >
> > >
> > >
> > >     Robert
> > >
> > > [...]
> > >
> >
> > --
> > Robert Gentleman, PhD
> > Program in Computational Biology
> > Division of Public Health Sciences
> > Fred Hutchinson Cancer Research Center
> > 1100 Fairview Ave. N, M2-B876
> > PO Box 19024
> > Seattle, Washington 98109-1024
> > 206-667-7700
> > rgentlem@fhcrc.org
> >
> >
>

	[[alternative HTML version deleted]]

