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

[Tamas Nepusz]

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.