[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] igraph_barabasi_game doubt
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] igraph_barabasi_game doubt |
Date: |
Sat, 14 Jun 2014 23:16:10 +0200 |
> I just want to make sure that I am using the function properly.
> I know that it only will be 3 in the limit of large N, however I expected a
> higher value for
> gamma. Besides, I tried to generate a similar network using the networkx
> python library
> and got a gamma approximately 2.8
The NetworkX implementation starts the preferential attachment process from a
star graph with m+1 nodes; the igraph implementation starts from a single node.
(The original publication of Barabasi and Albert did not specify the starting
conditions so different implementations use different seeding methods). I think
that the NetworkX approach (i.e. starting from a star graph) yields alphas
closer to the theoretical value for small networks because the initial
condition already includes a large hub and the generating process will be
biased towards this node.
If you want to make igraph's behaviour compatible with NetworkX (and don't mind
the above mentioned bias), use the start_from argument of igraph_barabasi_game
and provide a star graph there (generated using igraph_star()). This yields
alphas close to 2.9 for me; I tried it in Python but the result should be the
same in C as well:
>>> n, m = 4000, 4
>>> alphas = RunningMean()
>>> seed = Graph.Star(m+1, mode="undirected")
>>> for i in xrange(5000):
... g = Graph.Barabasi(n=n, m=m, start_from=seed, outpref=True)
... alphas << power_law_fit(g.degree()).alpha
...
>>> print alphas
Running mean (N=5000, 2.919277 +- 0.089871)
FWIW, there is a third approach that is commonly used for seeding the
generation process in the Barabasi-Albert model: one could use a fully
connected clique of size m+1. This eliminates the bias towards the center of
the star graph, but it introduces another: the clustering coefficient of the
graph will be higher than expected in the early stages of the generation
process.
T.