生成无标度和小世界网络

Question

为了找到能够生成无标度和小世界网络的非常基本的算法版本，我进行了很多谷歌搜索。不幸的是，我的搜索没有给出结果。

我不需要很复杂的东西。只需要一些东西来解释如何生成所需的网络以及算法为何如此工作。

我很清楚如何生成 Erdos-Renyi 图，但我找不到类似的无标度和小世界案例。

伪代码以及C/C++、Maltab、Java和Python对我来说都很好。

Answer 1

我对无标度网络或小世界网络一无所知（只听说过名称），但快速 google 搜索使我进入了以下维基百科页面：

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

这两种算法在这些维基百科页面中都有详细描述。

Answer 2

抱歉，如果这不是您想要的，但是在 Netlogo 中，模型库中有一个非常好的示例，适用于两种类型的网络。

netlogo v.5中生成小世界网络的代码是：

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

我相信模型库可以进一步帮助您。

生成无标度和小世界网络

Generate scale-free and small-world networks

algorithm

graph

graph-algorithm