Generating random graphs with arbitrary specified degree distribution

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Generating random graphs with arbitrary specified degree distribution

Rui Carvalho
Hello,

I'd like to use graph-tool to generate random graphs obeying example (d)
from Newman et al., PRE 64, 026118.

Basically, there are 1000 people and each person knows between zero and five
others, the number of people in each category being from zero to
five:{86,150,363,238,109,54} -this is the histogram.

Can I use graph-tool to generate graphs with this pdf a la Newman et al.?
Did I miss an example in the documentation detailing how to do this?

Also can I use graph tool to generate random graphs *exactly* with this
degree sequence as in the configurational model?

Cheers,
Rui


Reply | Threaded
Open this post in threaded view
|

Re: Generating random graphs with arbitrary specified degree distribution

Tiago de Paula Peixoto
"Rui Carvalho" <[hidden email]> writes:

> Hello,
>
> I'd like to use graph-tool to generate random graphs obeying example
> (d) from Newman et al., PRE 64, 026118.
>
> Basically, there are 1000 people and each person knows between zero
> and five others, the number of people in each category being from zero
> to five:{86,150,363,238,109,54} -this is the histogram.
>
> Can I use graph-tool to generate graphs with this pdf a la Newman et
> al.?  Did I miss an example in the documentation detailing how to do
> this?
>
> Also can I use graph tool to generate random graphs *exactly* with
> this degree sequence as in the configurational model?

With graph-tool you can specify the sampling function for the degrees,
so you could (inside your function) simply sample one degree from each
bucket, and subtract from one from it, and stop when it's empty. This
implies also that you could supply a function which "samples" in a
specific sequence, and thus achieves what you asked for in the second
question.

For details on how to implement this see this part of the documentation:
http://projects.forked.de/graph-tool/wiki/RandomGraphGeneration#Moreelaboratedistributions

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>

Reply | Threaded
Open this post in threaded view
|

Re: Generating random graphs with arbitrary specified degree distribution

Rui Carvalho
Hi Tiago,

The reason why I want to do this is I have a "real world" network and would
like to benchmark it against random networks. I had a look at the
documentation and it didn't seem oriented towards this task -correct me if
I'm wrong, but it sounds too difficult?

I'm not sure whether this would be of interest to others, but if the answer
would be yes, than perhaps we could have it easier in a future release? Or
maybe I'm just missing the point -anyway, graph-tool is a great program :)

Cheers,
Rui


-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On
Behalf Of Tiago de Paula Peixoto
Sent: 07 March 2008 23:42
To: Main discussion list for the graph-tool project
Subject: Re: [graph-tool] Generating random graphs with arbitrary specified
degree distribution

"Rui Carvalho" <[hidden email]> writes:

> Hello,
>
> I'd like to use graph-tool to generate random graphs obeying example
> (d) from Newman et al., PRE 64, 026118.
>
> Basically, there are 1000 people and each person knows between zero
> and five others, the number of people in each category being from zero
> to five:{86,150,363,238,109,54} -this is the histogram.
>
> Can I use graph-tool to generate graphs with this pdf a la Newman et
> al.?  Did I miss an example in the documentation detailing how to do
> this?
>
> Also can I use graph tool to generate random graphs *exactly* with
> this degree sequence as in the configurational model?

With graph-tool you can specify the sampling function for the degrees,
so you could (inside your function) simply sample one degree from each
bucket, and subtract from one from it, and stop when it's empty. This
implies also that you could supply a function which "samples" in a
specific sequence, and thus achieves what you asked for in the second
question.

For details on how to implement this see this part of the documentation:
http://projects.forked.de/graph-tool/wiki/RandomGraphGeneration#Moreelaborat
edistributions

Cheers,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>
_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.forked.de/mailman/listinfo/graph-tool