六度分隔理论可以用什么数学模型证明？ 第1页

这学期在学Network，现学现卖一下。

“小世界性质(small world property)”的一个规范定义是：图G的“平均路径长度(average path length)”或“直径(diameter)”是 的，其中 是图G的结点数目， 是图G的平均度(average degree)。

注解：路径(path)指的是从图G中的一个结点走到另一个结点，且不重复经过任意结点的边序列。

平均路径长度就是所有路径长度的平均值；直径是所有路径长度的最大值。

结点的度(degree)指与该结点相连的边数；平均度就是所有结点的度的平均值。

最后， 表示，如果图G自然“增长”，随着结点数目增加，其平均路径长度或直径的增长速度最多和括号内的表达式一样快。

所以 @傅渥成 的说法的第一点其实有待商榷。上述规范定义当中那个表达式其实就是根据指数增长的想法来的：如果每个结点的度都约为平均度 ，那么拓展k层之后，覆盖的结点数大约是 ，假如此时恰好能够覆盖所有结点，我们就有 。

之所以可以这样做是因为稀疏网络大多是Tree-like的，比如Erdos-Renyi随机网络的稀疏情况(np_n=O(log n))，或者Leskovec et al.(2007)的野火模型，都使用了类似的想法。

Barabasi的一个统计：

如何解释（或者说生成“小世界”性质）呢？实际上随机图模型中最经典的Erdos-Renyi模型就可以：假设有n个结点，两两之间以概率p连边，得到的就是ER(n,p)。

显然我们可以选择固定的p，但是更符合现实的做法是考虑p_n随n变化，比如上面提到的np_n=O(log n)

Chung and Lu(2001)给出了如下定理：

如果 ，则随机图 的直径几乎总是与 有相同的增长率。

注意到 恰好就是随机图各结点的度的期望，所以这一设定下的Erdos-Renyi随机图就呈现“小世界”性质。

但是ER除了能给出小世界性质以外，比如度的幂律分布(power-law degree distribution)或者高聚集度(high clustering)都没法实现。 @Ly Rus 提到了Watts-Strogatz模型，但是似乎和我学的不太一样……

总之，Watts-Strogatz(1998)的想法是，从一个高聚集度的初始网络开始，随机重连一些边，可以降低直径。如果随机重连的概率小，那么就是高聚集度、高直径的初始网络，如果随机重连的概率大，那么就是低聚集度、低直径（小世界）的Erdos-Renyi网络，如果概率介于两者之间，那么就能够同时实现高聚集度和低直径（小世界）的网络。