nw:generate-preferential-attachment doesn't use proper Barabasi-Albert model

[luis-r-izquierdo]

Dear NetLogo developers,

I believe the documentation of procedure nw:generate-preferential-attachment is not correct. In http://ccl.northwestern.edu/netlogo/docs/nw.html#nw:generate-preferential-attachment it is said that this procedure implements Barabási–Albert algorithm, with the wikipedia link also included in the documentation.

However, if I'm not mistaken, nw:generate-preferential-attachment makes use of Jung's BarabasiAlbertGenerator, which is a different algorithm, as explained here.

Basically, the algorithm used in Jung imposes that the probability p of creating an edge between an existing vertex v and the newly added vertex is p = (degree(v) + 1) / (|E| + |V|)

whereas this probability in the original paper is: p = degree(v) / |E|

Thank you so much for your amazing work, Luis

[qiemem]

Good catch and thank you for reporting (and sorry for the delayed response)! I'm wondering if we should actually just replace Jung's implementation with the original BA algorithm since we don't have the same concerns with regards to isolates (since generated nodes will only be attaching to each other, and thus there are no isolates that could be attached to anyway).

The pros of removing Jung's implementation are:

• The smoothing is actually going to mess up the scale-free distribution for smaller networks
• Since we're breaking stuff anyway, we could finally a min degree parameter to the primitive
• Jung's algorithm uses it's own RNG, so right now, the primitive is actually not using our RNG. This is definitely a bug. Using our own implementation would solve this.

The cons are:

• This would change people's model behavior silently, which is pretty bad. However, I feel like it would probably be changing behavior to what people think is already happening.

Alternative solutions:

• Just correct the documentation.
• Add an additional primitive with the true BA algorithm.
• Do something fancier as proposed in #17.
• Do a slightly less fancy version than #17 by just adding a reporter argument that allows users to customize the weight given to turtles. So, the current behavior would be reproducible with nw:generate-preferential-attachment turtles links 1000 [ count my-links + 1 ]. Original BA would be nw:generate-preferential-attachment turtles links 1000 [ count my-links ]. Etc.

I'm leaning towards just changing the primitive. The number of parameters will change, so people will know that the primitive has changed in some way. If we go with the last alternative, then users will have a choice of which implementation to use, though it definitely is more complicated.

The implementation I would use would be similar to:

to generate-preferential-attachment [ num-nodes min-degree ]
  crt min-degree + 1 [
    create-links-with other turtles
  ]
  repeat (num-nodes - (min-degree + 1)) [
    crt 1 [
      repeat min-degree [
        create-link-with one-of other [ both-ends ] of one-of links
      ]
    ]
  ]
end

[luis-r-izquierdo]

Thank you so much for dealing with this. For what it's worth, I fully agree with all your reasoning and I share your preference. Thanks a lot, You Guys are great, Luis

[weronikacwir]

Is this fix included in NetLogo 6.0.2?

I ended up here because while preparing to show my classmates in Modeling & Simulation class three different ways of building preferential attachment networks in NetLogo, I noticed that my implementations of Barabási–Albert algorithm seemed to produce networks with higher maximum degrees than the nw:generate-preferential-attachment procedure. If the fix hasn't made it into NetLogo 6.0.2 then I found the answer to my problem; if it has, then I have to keep looking.

Thank you!

Weronika

[luis-r-izquierdo]

Hi Weronika,

I don't think so. The issue was fixed in December 2017, but NetLogo 6.0.2 was released in August 2017. https://ccl.northwestern.edu/netlogo/docs/versions.html

[weronikacwir]

Thank you Luis!

This solves my problem, as in: I now have the reason for the discrepancy between the results of my BA model implementation and NetLogo's, and can quit scratching my head.