Re: [igraph] Barabasi Algorithm

[Tamas Nepusz]

> I was wondering if you have any specifications about the Barabasi algorithm
> described in the Python iGraph package.
There is no formal specification available, sorry - you can always
take a look at the source code of the algorithm in the C core, though:

https://github.com/igraph/igraph/blob/master/src/games.c#L486

Also, the C function that is behind the Graph.Barabasi() constructor
in Python is somewhat documented in the C layer:

http://igraph.org/c/doc/igraph-Generators.html#igraph_barabasi_game

> I was wondering what exactly the zero_appeal parameter does and how it is 
> used in the algorithm.

zero_appeal is the attractiveness of vertices with zero indegree. In
particular, the probability that a vertex is cited is proportional to
d^power+A, where d is its degree of the vertex, "power" is the "power"
parameter in the Python call and "A" is the "zero_appeal" parameter.

> like to know how the algorithm works specifically as I have looked through
> the sources cited and found only a generic algorithm for creating a scale
> free graph of a set power value.

igraph basically uses a "partial prefix sum tree" to generate the
graph. The tree can be used to sample items from an arbitrary discrete
probability distribution. When a new vertex is added to the graph
during the generation, the endpoints of the k edges originating from
this vertex are selected by drawing k samples from the existing vertex
set using the tree (which allows us to do this efficiently), then the
probabilities in the tree are updated with the new vertex degrees
after the edge additions. The source code for this particular
algorithm is here:

https://github.com/igraph/igraph/blob/master/src/games.c#L297

Gabor's dissertation contains a more detailed explanation of the
sampling part, i.e. the partial prefix sum tree in Appendix A.1:

http://gaborcsardi.org/files/Csardi_Gabor_Ertekezes.pdf

All the best,
T.