how to generate a power-law degree sequence?

[wdg]

Hi,

This question may not be directly related to networkx, but hopefully
there may be functions that can help to solve this problem in
networkx.

The problem is the following:

I need to generate a sequence of degrees that obeys the power law
degree distribution. The number of nodes are 10000, so the cut-off
value of the degree is 9999 (no node has degree larger than 9999).
Moreover, there is one more constraint: <k> is fixed at 6,8,10,etc.

Is there any function in networkx that can help me generate the
sequence? If no, could you tell me an efficient way to generate the
sequence?

wdg

[Daπid]

See the example at the bottom:

http://networkx.lanl.gov/reference/generated/networkx.generators.degree_seq.configuration_model.html

>>> from networkx.utils import powerlaw_sequence
>>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)

> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>

[wdg]

This is indeed nice. However, the degree sequence I need is a little
bit more than that.

See http://iopscience.iop.org/0295-5075/81/2/28005,

In page 3, the paragraph under Fig.1 talks about a "scale-free network
with natural cutoff and fixed average connectivity <k>=6,8,10". In
nx.utils.powerlaw_sequence, we can only specify the exponent, but not
the average degree. I'm looking for a sequence generator that can
generates a power-law degree sequence that has given exponent and
average degree.

Thanks.

On Jun 9, 9:16 pm, Daπid <davidmen...@gmail.com> wrote:
> See the example at the bottom:
>

> http://networkx.lanl.gov/reference/generated/networkx.generators.degr...

>
>
>
>
>
>
>
> >>> from networkx.utils import powerlaw_sequence
> >>> z=nx.utils.create_degree_sequence(100,powerlaw_sequence)

[Matthias Ekman]

you might want to have a look at:
http://www-rp.lip6.fr/~latapy/FV/generation.html

That provides the functions you asked for.

Best,
Matthias

[Marcel Blattner]

Hi there

Check this one. I use it to generate simple uncorrelated graphs with pre-described degree sequence and mean.

http://www-rp.lip6.fr/~latapy/FV/generation.html

Cheers
M.

[wdg]

Thanks to Marcel and Matthias for pointing me to a wonderful tool. But
my question is more about generating degree sequence per se rather
than generating the graph with that given degree sequence.

See the reference I mentioned above. Generating a naive degree
sequence obeying the continuous power-law distribution is easy, but it
is quite troublesome for me to generate a sequence obeying the
discrete power-law distribution and with natural degree cutoff.
Moreover, I have no idea how to generate a degree sequence when both
the power-law exponent and the average degree are specified, as
described in the reference (http://iopscience.iop.org/
0295-5075/81/2/28005, page 3, the paragraph under Fig.1).

Thanks.

On Jun 10, 4:16 pm, Marcel Blattner <blatt...@gmail.com> wrote:
> Hi there
>
> Check this one. I use it to generate simple uncorrelated graphs with pre-described degree sequence and mean.
>
> http://www-rp.lip6.fr/~latapy/FV/generation.html
>
> Cheers
> M.
>

> On 10.06.2012, at 09:16, wdg <samuelan...@gmail.com> wrote:
>
>
>
>
>
>
>
> > This is indeed nice. However, the degree sequence I need is a little
> > bit more than that.
>

> > Seehttp://iopscience.iop.org/0295-5075/81/2/28005,

[Daπid]

On Sun, Jun 10, 2012 at 9:16 AM, wdg <samue...@gmail.com> wrote:
> This is indeed nice. However, the degree sequence I need is a little
> bit more than that.

Then you will need to dive a bit in the code. The function
powerlaw_sequence is just:


def powerlaw_sequence(n,exponent=2.0):
"""
Return sample sequence of length n from a power law distribution.
"""
return [random.paretovariate(exponent-1) for i in range(n)]

I don't have access to the paper you linked, so I don't know exactly
what you want, but if the Wikipedia [1] is right about it, you want
something following $x^\alpha e^{-\beta x}$. So, your task would be to
cook a function that generates n random numbers following that
distribution.

Numpy has the function numpy.random.gamma [2] that, if I am not
mistaken, it is what you want. If your function is slightly different
and you cannot find them there, you would have to code your own
generating method, like rejection or the inverse method (both
explained marvelousely in [3] or in any basic numerical analysis
book).

[1]
http://en.wikipedia.org/wiki/Powerlaw#Power_law_with_exponential_cutoff
[2] http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.gamma.html#numpy.random.gamma
[3] W. Press et al, Numerical Recipes

[wdg]

Thank you very much for your reply. I am looking into the information
you provide. Meanwhile, you can download the mentioned paper
temporarily through this link:
https://dl.dropbox.com/u/7383429/Bianconi%20-%202008%20-%20The%20entropy%20of%20randomized%20network%20ensembles.pdf.

Thanks.

On Jun 10, 8:01 pm, Daπid <davidmen...@gmail.com> wrote:

> [2]http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.gamm...

[Daπid]

On Sun, Jun 10, 2012 at 4:59 PM, wdg <samue...@gmail.com> wrote:
> Meanwhile, you can download the mentioned paper
> temporarily through this link:
> https://dl.dropbox.com/u/7383429/Bianconi%20-%202008%20-%20The%20entropy%20of%20randomized%20network%20ensembles.pdf.

Thanks, seems interesting, but they don't define the "powerlaw with
cutoff value" distribution. It can be deduced from the context, but it
is not clear at all. Maybe it is something standard in Mathematics,
but I am doubtful, I cannot find it in any of the mathematical
handbooks I have around (Abramowitz, Schaun...).

[Daπid]

>> gsequence=nx.utils.create_degree_sequence(N,

                        degree_distribution, max_tries=100)

>> G=nx.configuration_model(gsequence)

where degree_distribution is a function that returns a list of N elements drawn randomly. Example:

>> def degree_distribution(n):

        return np.random.uniform(size=n)

On Sun, Aug 12, 2012 at 2:32 PM, xpt <xpt...@gmail.com> wrote:

在 2012年6月9日星期六UTC+8下午3时48分35秒，wdg写道：

Have you solved your problem?

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To view this discussion on the web visit https://groups.google.com/d/msg/networkx-discuss/-/qwv-NwVzRyAJ.

[wdg]

I think his or her question may be more related to the inconvenience of working out the degree distribution with cut-off. Your solution is nice, but it would even better if there is a helper function that can help tackle this inconvenience.

[wdg]

I have just taken a look at the code of degree_distribution, and I found something subtle. Basically, the code deals with the cutoff by setting all random numbers larger than the natural cut-off (meaning degree k > n-1, n is the size of the network) to the natural cut-off n-1. This approximation actually bothers me a lot. Could anyone give out an error estimation?