Re: [igraph] Understanding Barabasi Function and how to simulate a scale free()

[Daniele Capocefalo]

Dear Tamas,

Thanks for your detailed reply.

I have one doubt regarding this part:

Anyway, if you need to generate scale-free networks with a degree distribution that follows a given exponent, then Graph.Barabasi() is not the way to go. You need Graph.Static_Power_Law() instead:

>>> g = Graph.Static_Power_Law(n=100000, m=200000, exponent=3)

>>> fit = power_law_fit(g.degree())

>>> fit.alpha

3.0757961750805816

Static_Power_Law() is essentially a variation of the Static_Fitness() method where each node is given a "fitness" value and the generation process tries to ensure that the degrees of nodes are proportional to their fitness values. Static_Power_Law() simply pre-generates a power-law degree distribution and feeds it into Static_Fitness().

I have found the alpha of my networks using power_law_fit(), then generated  Random scale-free  network that has only one large components using Static_Power_Law(). For some of my networks, when recomputing the power_law_fit on the simulated scale free networks, the alpha varies consistenyl. As of an example, I'll post here the results obtained using a network of 84 nodes and 221 edges and an alpha estimated on 2.614071596

Example #1

a= g.Static_Power_Law(n=84,m=221,exponent_out = 2.61407159636724, loop = False,  multiple = False)
fit = st.power_law_fit(a.degree())
fit.alpha
6.616842211661753

Example #2

b= g.Static_Power_Law(n=84,m=221,exponent_out = 2.61407159636724, loops= False, multiple = False)
fit = st.power_law_fit(b.degree())
fit.alpha
4.455056295669706

Example #3

c= g.Static_Power_Law(n=84,m=221,exponent_out = 2.61407159636724, loops= False, multiple = False)
fit = st.power_law_fit(c.degree())
fit.alpha
8.086323608487003

Is this to be expected? I have proven this in several simulations using different networks and parameters.

Thanks a lot!

cheers,

Daniele

On 21/04/17 11:38, Tamas Nepusz wrote:

I have one question regarding the Barabasi Function in GraphBase (python). The "m" parameter states [...]
It isn't clear whether this m implies the average degree of the scale free network or something else.

Additionally, since it clearly states "outgoing edges", do I need to convert the network to undirect after calling the Barabasi() method?

No, simply use the directed=... keyword argument of the Graph.Barabasi() constructor to decide whether you want an undirected or a directed network in the end. However, note that the _generation process_ of the Barabasi-Albert model assumes a _directed_ graph, i.e. the graph "stays" directed during the whole generation process, and the arrowheads of the edges are dropped only at the end of the generation process if you use directed=False (which is also the default). That's why the "m" parameter refers to the number of "outgoing edges" to generate because the edge directions are distinguished while the graph is being generated.

This also ties into your other question regarding the relation of "m" to the average degree. When the generated graph is directed, m is the out-degree of each vertex except the first few where there are not enough other vertices to connect to:

>>> g = Graph.Barabasi(n=20, m=2, directed=True)

>>> g.outdegree()

[0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

So, in this case, the average out-degree tends to m as the graph becomes large (i.e. n tends to infinity).

When the graph is undirected, the arrowheads are dropped at the end, but this does not influence the outcome:

>>> g = Graph.Barabasi(n=20000, m=2, directed=False)

>>> g.ecount() / float(g.vcount())

1.99985

So, yes, m is "almost" the average degree.

Moreover, I need to simulate several scale free networks  that "mirrors" real networks I'm studying. To this extent, I was searching for a function or an algorithm to infer the exponential parameter for the power law. does igraph for python offer something like this?

Yes; see the power_law_fit() function.

 

Alternatively, could I use the average degree of the real networks  and give it to the Barabasi() function when defining "m"?

No, because the Barabasi-Albert model always generates networks with an exponent of alpha=3 -- but only in the infinite limit, so don't expect that power_law_fit() would return a fitted exponent of 3 for a finite graph that you have generated with Graph.Barabasi().

Anyway, if you need to generate scale-free networks with a degree distribution that follows a given exponent, then Graph.Barabasi() is not the way to go. You need Graph.Static_Power_Law() instead:

>>> g = Graph.Static_Power_Law(n=100000, m=200000, exponent=3)

>>> fit = power_law_fit(g.degree())

>>> fit.alpha

3.0757961750805816

Static_Power_Law() is essentially a variation of the Static_Fitness() method where each node is given a "fitness" value and the generation process tries to ensure that the degrees of nodes are proportional to their fitness values. Static_Power_Law() simply pre-generates a power-law degree distribution and feeds it into Static_Fitness().

T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
———
Daniele Capocefalo
Bioinformatics unit
Casa Sollievo della Sofferenza - Mendel
Viale Regina Margherita 261 - 00198 Roma IT

Tel: +39 06 44160526 - Fax: +39 06 44160548
E-mail: address@hidden
Web page: http://www.css-mendel.it/
Web page: http://bioinformatics.css-mendel.it