使用SNAP构造小世界网络

毕业设计需要用到小世界网络作为测试用例，所以研究了一下这种图的特点以及怎么生成它。现在整理成文档，希望对后来人有用。

什么是小世界网络？

小世界网络（Small-world network）是一种特殊的复杂网络结构，在这种网络中绝大多数节点彼此并没有连接，但是只要经过少数几跳就可以从一个节点到达另一个节点。

现实世界中的人际关系就满足这种特征，那些看似和你八杆子打不着的人只要通过若干个中间人的介绍就可以和你扯上关系，“六度分割理论”正是基于这种现象提出。

用数学的语言来描述小世界网络就是，在一个由许多顶点组成的图中，任意两个顶点之间的平均路径(average path)长度比顶点数小得多。

怎样构造小世界网络？

小世界网络的构造方法由 Duncan Watts 和 Steven Strogatz 在 1998 年给出，他们提出了一种叫 Watts-Strogatz model 的模型。

这个模型体现了小世界网络的两大特征：

• 平均路径长度短
• 聚集度高

这个数学模型有以下几个参数：

• N：顶点数量
• k：平均度数
• p：随机因子（0到1之间的一个概率值）

根据这些参数，通过一定算法就可以构造出一个具有 N 个顶点， (N*K)/2 条边的图。因子 p 用来决定生成图的随机度，p 越大图的随机度越高。当 p 等于 0 时，生成的图是一个正则图；当 p 等于 1 时，生成的图是一个 Erdos-Renyi 随机图。

这个幻灯片中有详细的证明：Random graphs and Watts-Strogatz 可以证明：

• p = 0 时，生成的正则图的平均路径长度为 N/(2*K)，是一个远大于 1 的数
• p = 1 时，生成的随机图的平均路径长度等于 ln(N)/ln(k)，是一个很小的数

使用 SNAP 库构造小世界网络

什么是 SNAP？

SNAP’s homepage SNAP 全名叫 Stanford Network Analysis Platfom（斯坦福网络分析平台），它提供了一些对大规模网络进行数据分析和数据挖掘时需要用到的库函数。

当然它也提供了 Watts-Strogatz 这种模型的算法的实现，通过它我们可以很方便地生成一个小世界网络。

如何使用 SNAP？

1. 从这里下载源代码
2. 进入 example/graphgen 目录（并不需要编译包中全部的代码，只需要编译用来生成图的代码即可）
3. 修改 Makefile，根据你所使用的操作系统撤销一些注释
4. make opt 进行编译

事实上，SNAP 库可以生成很多种类的图，小世界网络只是其中一种：

1. Complete graph
2. Star graph
3. 2D Grid
4. Erdos-Renyi
5. Random k-regular graph
6. Albert-Barabasi Preferential Attachment
7. Random Power-Law graph
8. Copying model by Kleinberg et al
9. Small-world model

在命令行参数中使用 -g:w 选项可以让程序生成我们想要的小世界网络。-n -k -p 选项分别代表了 Watts-Strogatz 模型的算法在生成小世界网络时需要几个参数。

一句完整的命令如下所示：

./graphgen -g:w -n:5000 -k:4 -p:0.1 -o:output.txt