Generate scale-free and small-world networks

Question

I'm googling around a lot in order to find a very basic version of algorithms able to generate scale-free and small-world networks. Unfortunately, my search is not giving results.

I don't need something very complicated. Just need something that explain how to generate the desired networks and why the algorithms work that way.

I know very well how to generate Erdos-Renyi graph, but I can't find something similar for scale-free and small-world cases.

Pseudo-code, as well as C/C++, Maltab, Java and Python are good for me.

Answer 1

I know nothing about scale-free or small-world networks (only have heard the names), but a quick google search led me to the following wikipedia pages:

https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism

https://en.wikipedia.org/wiki/Watts_and_Strogatz_model

The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering

Both algorithms are well-descriped in these Wikipedia pages.

Answer 2

Sorry if this is not what you want, but in Netlogo there is a really good example in the models library for both type of networks.

The code to generate a small world network in netlogo v. 5 is:

to setup_network
  if network = "small-world" [
    let max-who 1 + max [who] of turtles
    let sorted sort ([who] of turtles)
    foreach sorted[ ?1 ->
      ask turtle ?1 [
        let i 1
        repeat number-of-links [
          create-link-with turtle ((?1 + i) mod max-who)
          set i i + 1
        ]
      ]
    ]
    repeat round (rewire-prop * number-of-agents) [
      ask one-of turtles [
        ask one-of my-links [die]
        create-link-with one-of other turtles with [link-with myself = nobody]
      ]
    ]
  ]
  if display-network? [
    layout-circle (sort turtles) (max-pxcor - 1)
    display
  ]
end

Im sure the models library can help you out further.