CODEWITHSUNDEEP
network-programmingnetlogo
user7558372
user7558372

Reputation:

Create networks with parameter number of nodes and mean degree

I would like to create a random network (and a scale-free) with N nodes and <k> as a mean degree. How can I do that?

The nw: generate-random (and nw:generate-preferential-attachment) method of the NW extension of NetLogo doesn't seem to allow to handle the average degree of nodes.

I am wrong? Tips? Thanks.

Upvotes: 2

Views: 225

Answers (1)

Bryan Head
Bryan Head

Reputation: 12580

It's true that neither nw:generate-random nor nw:generate-preferential-attachment allow you to specify exact average degree. In the case of nw:generate-random however, the average degree will be approximately connection-probability * num-nodes. For instance:

observer> repeat 10 [ ca nw:generate-random turtles links 1000 0.1 print 2 * count links / count turtles ]
99.902
100.358
100.522
99.674
100.338
100.272
99.772
100.24
100.24
100.412

That said, if you do want to specify exact average degree, you can use the following:

to generate-random [ num-nodes avg-degree ]
  crt num-nodes
  while [ 2 * count links < avg-degree * count turtles ] [
    ask one-of turtles [
      create-link-with one-of other turtles
    ]
  ]
end

Note that that code intentionally does not do something like create-link-with one-of other turtles with [ not link-neighbor? myself ], as that will end up creating more turtles with larger degree than it should (that is, the average degree will be right, but the degree distribution will be skewed).

Preferential attachment is a little more complicated. We have to seed with enough turtles that incoming turtles have enough turtles to attach to:

to generate-preferential-attachment [ num-nodes avg-degree ]
  crt avg-degree + 1 [
    create-links-with other turtles
  ]
  repeat (num-nodes - (avg-degree + 1)) [
    crt 1 [
      while [ 2 * count links < avg-degree * count turtles ] [
        create-link-with one-of other [ both-ends ] of one-of links
      ]
    ]
  ]
end

This code uses the same mechanism for preferential attachment as the Preferential Attachment model in the models library. From that mode:

;; This code is the heart of the "preferential attachment" mechanism, and acts like
;; a lottery where each node gets a ticket for every connection it already has.
;; While the basic idea is the same as in the Lottery Example (in the Code Examples
;; section of the Models Library), things are made simpler here by the fact that we
;; can just use the links as if they were the "tickets": we first pick a random link,
;; and than we pick one of the two ends of that link.

In most cases, I just use the NW procedures for generation in my models, but when I really need to control exact average degree, I use variants on the above. Again, they're a little more complicated than you might expect to prevent bias in the degree distribution from creeping in.

Both procedures assume that there are no pre-existing turtles. If that's not the case in your model, let me know, and I'll modify. It's unnecessarily complicates the code otherwise (as you have to keep track of which turtles you've created).

Edit is response to question in comments:

The while [ 2 * count links < avg-degree * count turtles ] [ ... ] will cause the ... to run over and over until the average degree is equal to avg-degree. Recall that average degree is equal to 2 * count links / count turtles.

Thus, in the case of generating a random network, we try to add a link, check to see if we have enough, and if don't, we keep going until we do. The reason to use while here instead of repeat because the body of the look might not actually create a link (if a turtle tries to link with a turtle it's already linked with). It's written this way to prevent bias in the degree distribution: the more links a turtle has, the less likely it should acquire new inks.

In the case of preferential attachment, we add one node at a time and then add links to that node until our average degree is correct. This is preferable to always just having the turtle come in with avg-degree / 2 links because it plays nicer with odd degrees.

Upvotes: 1

Related Questions