Hello (again),
I want to simulate a variety of preferential-attachment networks, with the probability proportional to a*deg + 1 with variable a. Now I want to allow certain negative values of a, specifically -1/n for natural n \ge 2. I have found this issue Barabasi aging game crashes on negative index from psumtree_search · Issue #1618 · igraph/igraph · GitHub on github which introduced a check for a negative degree coefficient in barabasi_aging_game so that the probabilities cant become negative. However, in this (very specific) scenario, they cannot become negative as a vertex with attachment-probability zero will not get any further neighbors and they all start with attachment-probability > 0. I have looked at the code and can’t find any reason against purely a negative deg_coef.
Therefore I am pretty sure that I can just remove this check for my use-case but wanted to ask if there is any reason not to?
Additionally, if this is possible just like that, then this is also an easy way to generate a random graph with a given max. degree and uniform attachment over the “free” edges (also known as random d-ary (search) tree). Maybe this is of interest to other users as well.
You need to make sure that the weights associated with vertices are never negative, otherwise you will get an error from the psumtree functions or worse (crash or misbehaviour).
If deg_coef is negative, some of the weights will be negative as well. See here for the weight formula used by this function: Barabasi aging game crashes on negative index from psumtree_search · Issue #1618 · igraph/igraph · GitHub So no, you cannot safely remove the check, as it will lead to errors.
Of course you can implement a different formula for the weights if you like, and experiment. The formula you mention here (deg/n + 1) is not the same as the one used by barabasi_aging_game().
I’m not sure I understand what you mean here, but be careful about what you mean by “random”. A die that lands on six 99% of the time is “random”, isn’t it? If you replace your random graph generator by such a die, will your results be meaningful?
Consider a non-preferential attachment where new nodes connect to any existing one with the same probability. Does it generate trees? Yes. Are they random? Sure, in some sense. Is every tree generated with the same probability? Not at all.
Thank you for your answer. I forgot to mention that I am always only adding one edge. Forgive me if I’m wrong, but as far as I know, then
-1/d * degree + 1
can’t become negative when iteratively constructing the graph if d >= 2. The root starts out with weight +1 > 0 and every new vertex gets initial weight -1/d +1 > 0. And the degree can always only increase by one and so we will reach -d/d +1 = 0 and then the weight will not decrease any further. Unsure if I’ve missed something in the construction of the graph. This might not work when adding multiple edges at once, I forgot to consider that (you might “skip over the zero” in that case). I guess I will just try it out and see if there is any error.
And thank you for your addition, but yes I am quite sure that this is a random tree generating process with sufficient amounts of randomness to be interesting! (:. The usual way to formulate the attachment probability is (d - deg(v))/normalization, which is probably easier to understand. But this can be re-formulated into (-1/d deg(v) +1)/normalization which is what I’m trying to exploit here! And since igraph provides a lot of random graph generators, I figured maybe it would be interesting to provide another variant.
Lastly, I am also not sure if I understand you correctly. Due to Wikipedia, these two processes absolutely generate the same type of random tree. I think the labelling of the nodes might be the crux here.