[Top][All Lists]

[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 


reply via email to

[Prev in Thread] Current Thread [Next in Thread]