Exponent of degree distribution in preferential attachment random graphs?


I am using the method sample_pa(), and I wonder if you know what is the approximate exponent of the degree distribution of the sampled networks

[link] (sample_pa function - RDocumentation)

more specifically, when you set out.pref=FALSE, ie, you use only the in-degree in the preferential attachment expression, is it valid the estimate from the following paper?

Krapivsky, P. L., Rodgers, G. J., & Redner, S. (2001). Degree distributions of growing networks. Physical Review Letters, 86(23), 5401.

if this is true, then the zero.appeal parameter would equal lambda from the paper, and in that case, if using default parameters (zero.appeal=1), and putting p=1 to make the two formulations equivalent, then the asymptotic exponent of the in-degree distribution would be 3, am I right?

more generally, the question is: what precise model of preferential attachment is used by this method? because the documentation cites Barabasi and Albert (1999), which is a model for undirected graphs, and this igraph method by default produces directed graphs.

Best regards

I was about to describe the precise procedure used by this function, but then I looked at the documentation and I realized that it is already explained there. In the interest of more effective communication, can you explain what was unclear to you in the documentation?

This function is rather general and can simulate many different variants of preferential attachment, including the undirected Barabási-Albert model and the directed Price model.

I wonder what the asymptotic distribution of the degree is, specifically in the case of the default parameters, to tell this you need to know the precise underlying model used to build the network. And in this point, I think the documentation is unclear, since only one of the possible models you may get is explicitly mentioned (Barabasi-Albert (1999), BA graphs), a model that is not the one obtained under the default parameters since this model does not consider the additive attractiveness. The exponent of the degree is only suggested in this publication, and is formally explored in

Krapivsky, P. L., Redner, S., & Leyvraz, F. (2000). Connectivity of growing random networks. Physical review letters, 85(21), 4629.

but this model does not consider attractiveness. This parameter is studied together with the degree exponent in the publication I put in my first post. The directed Price model, on the other hand, depends on another parameter, named m in the original paper, which is related to a scaling assumption of the distribution depending on the population size, and that is not the ‘m’ parameter from BA graphs which corresponds to the m parameter of sample_pa(), so the connection to the Price model is not as straightforward as you pose it.

All these assumptions have an impact on the resulting asymptotic degree distribution, so I suggest it would be positive for a cleaner usage of this function, to have a documentation more clear about what precise models are obtained under each parameter configuration, or at least in the most typical cases, such as the default parameters.

Quoting from the documentation:

We start with a single vertex and no edges in the first time step. Then we add one vertex in each time step and the new vertex initiates some edges to old vertices. The probability that an old vertex is chosen is given by

P[i] \sim k_i^\alpha + a

where k_i is the in-degree of vertex i in the current time step (more precisely the number of adjacent edges of i which were not initiated by i itself) and \alpha and a are parameters given by the power and zero.appeal arguments.

Please be specific about what information you need about the generation process that is not given here.

Indeed parts of the process are influenced by other parameters, and there are subtle details. If you can point out which detail you need, we can answer your question.

As for relating a specific version of this process to an asymptotic degree distribution, I will leave that part to you. I will note that depending on the chosen parameters, the distribution will not be a power-law. In case you simply want to generate networks with a power-law degree distribution (“scale-free” networks), keep in mind that preferential attachment networks are not representative of all scale-free networks.

The generation process is the one you quote. On the other hand, my original question was “what is the approximate exponent of the degree distribution of the sampled networks”. I think I was clear about the detail I need. For this question, you may contrast the generative process described in the documentation with existing literature, or make aggregate statistics, etc but the documentation has no direct answer. If the answer comes from the only model cited in the documentation, which is only one of the infinitely diverse models you may produce with this function, the exponent should be 3. But one knows from the literature that the distinct assumptions of the generative process that function sample_pa() implements, generate asymptotic distributions with different characteristics, in particular, with different resulting exponents. That is the motivation of my questions, regarding which estimates from the literature are valid for the processes implemented by this function.

Since the documentation has no direct answer, I put the question on this forum. And I do think that putting only 1 reference in the documentation about only 1 of the possible models you may get, may be misleading about the networks you are working with.