Power Law Graphs with Degree Distributions less than 2

[Dionysios]

Hi everyone,

Is there any way networkx can generate graphs with power law degree
distributions with exponent 0<gamma<2?

Thanks a lot!

[Dan Schult]

Is there any way networkx can generate graphs with power law degree

distributions with exponent 0<gamma<2?

The configuration model is a good way to build networks with given

degree sequence.  Take a look at the example in:

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

That uses powerlaw_sequence which has a default exponent of gamma=2.0

You can change that using something like:

>>> powerlaw_gamma = lambda N: powerlaw_sequence(N, exponent=gamma)

>>> z=nx.create_degree_sequence(100,powerlaw_gamma)

>>> G=nx.configuration_model(z)

Dan

[Dionysios]

Hi Dan,

Thanks for your reply!
Actually that is exactly what I was trying. For 0<gamma<1, I
invariably get a binary matrix (which cannot be true; plus this means
the network is disconnected).
For 1<gamma<2, it fails to generate a valid degree sequence, even if
the maximum number of tries is set to a large number.

Below is a slightly different version of your code, so that others can
just copy and try it.

import networkx as nx
from networkx.utils import *

gamma=1.3

powerlaw_gamma = lambda N: powerlaw_sequence(N, exponent=gamma)

z=nx.create_degree_sequence(10000,powerlaw_gamma,max_tries=10000)
G=nx.configuration_model(z)
print z

Any other ideas?

Thanks in advance,
Dionysios

[Ryan James]

On Fri, 2009-12-25 at 08:26 -0800, Dionysios wrote:
> Hi everyone,
>
> Is there any way networkx can generate graphs with power law degree
> distributions with exponent 0<gamma<2?
>

I don't think it's in networkx, but the chinese buffet process is
commonly used to generate power law distributions with exponent between
1 and 2. see http://arxiv.org/abs/0905.4666 for a good discussion.

-ryan

> Thanks a lot!
>
> --
>
> 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.
>
>

[Aric Hagberg]

On Fri, Dec 25, 2009 at 9:30 PM, Dionysios <barmp...@gmail.com> wrote:
> Hi Dan,
>
> Thanks for your reply!
> Actually that is exactly what I was trying. For 0<gamma<1, I
> invariably get a binary matrix (which cannot be true; plus this means
> the network is disconnected).
> For 1<gamma<2, it fails to generate a valid degree sequence, even if
> the maximum number of tries is set to a large number.
>
> Below is a slightly different version of your code, so that others can
> just copy and try it.
>
> import networkx as nx
> from networkx.utils import *
>
> gamma=1.3
>
> powerlaw_gamma = lambda N: powerlaw_sequence(N, exponent=gamma)
> z=nx.create_degree_sequence(10000,powerlaw_gamma,max_tries=10000)
> G=nx.configuration_model(z)
> print z

create_degree_sequence() attempts to make a sequence
of integers following the given distribution
that has a maximum of len(seq) and is graphical.

If you don't have those restrictions you can try e.g.
>>> z=map(int,powerlaw_sequence(100,1.3))

You don't need a graphical sequence to pass to configuration_model()
since it creates a MultiGraph with parallel edges and self loops.
The sum of the sequence must be even.

To produce a graph with a power-law degree distribution for
low exponents you might need a very large graph.
This paper has some theory on generating random power-law graphs:
http://math.ucsd.edu/~fan/power.pdf

Aric