Re: [networkx-discuss] creating a conneted scale-free network with a given exponent

[Daniel Schult]

Remember that the powerlaw relations are only approximations. 

It might be reasonable to generate a slightly larger network and only take the largest connected component. The resulting network will be close to the right size and close to the right exponent/distribution.

If you don't like that approach, perhaps there is another algorithm like barabasi-albert only where you can select for an expected exponent. I vaguely recall a paper on that from a long time ago. Anyone?

On Mon, Dec 22, 2014 at 10:39 PM, Seyed Hossein Mortazavi <hosein.m...@gmail.com> wrote:

Hi,

I was wondering whether it's possible to create a connected scale-free network (that has a power-law node distribution) with a given exponent(between 2 and 3)

I've been using the following code:

while not is_connected(G):
    powerlaw_gamma = lambda N: nx.utils.powerlaw_sequence(N, exponent=2.5)
    z=nx.utils.create_degree_sequence(10000,powerlaw_gamma,max_tries=1000)
    G=nx.configuration_model(z)

but the problem is that for bigger networks (10000) nodes, It takes a lot of time and doesn't produce the graph (it works fine without the graph being connected condition)

Using the barabasi_albert_graph function, I am able to create such graphs, but I can't know about the exponent and I also can't give the exponent as an input.

while not is_connected(G):
    G=barabasi_albert_graph(n,m)


-Thanks!

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Seyed Hossein Mortazavi]

Thank you for your kind reply, do you know how I can get the largest connected component and turn into a graph?

-Thanks!

[Daniel Schult]

Here's the doc page for some ideas:

https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.components.connected.connected_components.html

Something like the example there should work.... maybe this:

>>>CCs=sorted(nx.connected_components(G), key = len, reverse=True)

>>>H=G.subgraph(CCs[0])

[Seyed Hossein Mortazavi]

Ok, I figured that out as follows:

from networkx.utils import create_degree_sequence
import pylab as pl
import numpy as np

try:
    import matplotlib.pyplot as plt
    import matplotlib
except:
    raise
from networkx import *

n=10000
print 'Creating powerlaw cluster with %d Nodes.' % n
gamma=2.2

powerlaw_gamma = lambda N: nx.utils.powerlaw_sequence(N, exponent=gamma)
z=nx.utils.create_degree_sequence(n,powerlaw_gamma,max_tries=100)
G=nx.configuration_model(z)

G = nx.connected_component_subgraphs(G)[0];

But something doesn't seem to be right. When I draw the Node Degree histogram, its not what it should be. Try this code:

degree_seq= list(degree(G).values());
uniques=np.unique(degree_seq);
uniques = np.append(uniques,uniques[-1]+1);
[y,x] = np.histogram(degree_seq,uniques);
x=x[:len(y)];
pl.loglog(x,y/float(sum(y)),'*r');

Alpha=gamma*-1;
XAxis  = pl.unique(np.round(pl.logspace(0,pl.log10(n),25)));
YAxis  = pl.unique(np.round(pl.logspace(0,pl.log10(n),25)))**(Alpha);
pl.loglog(XAxis,YAxis/float(sum(YAxis)),':b');

pl.xlabel('k,Degree');
pl.ylabel('P(k)');
pl.title('Node Degree Distribution');
pl.legend({'Expected (Alpha = -2.2)','Node Degree Distribution'});
pl.plot();
pl.show();

I have attached the resulting pdf in this post. The degree distribution doesn't appear to be quite right (or does it?)

Thanks!
-Hossein

[Daniel Schult]

What do you see that looks wrong? The intercept of the line? the long tail to the right?  

[Seyed Hossein Mortazavi]

The long tail to the right

[Daniel Schult]

I think you're OK with the tail on the right because it is basically at 10^-4 and you've got 10^4 nodes. No points can be below 10^-4 with your data set. Some people call this a finite size effect. Presumably with a larger graph you would have the linear behavior extend to smaller values until it ran into the smallest value for that network, etc. The powerlaw holds in the limit of large (infinite) networks.

[Seyed Hossein Mortazavi]

This was really helpful, thank you very much.