百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   richard-xu-25 网友的相关建议: 
      

这学期在学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网络,如果概率介于两者之间,那么就能够同时实现高聚集度和低直径(小世界)的网络。





  

相关话题

  伽马函数中,Γ(1/2)=√π 怎么来的? 
  从经济学角度来看,「随大流」通常是理性的吗? 
  你最满意自己的科研成果是什么? 
  伟大的数学家是如何培养的呢? 
  为什么直到到 2013 年 11 月社会舆论才开始集中批评 2008 年的四万亿投资计划? 
  如果你是阿里巴巴数学竞赛的出题官,你会出什么题目? 
  经济周期一定存在吗?为什么? 
  我国数学教材中的「勾股定理」是否应该改成「毕达哥拉斯定理(Pythagoras theorem)」? 
  你认为你所在学科最杰出的思想是什么? 
  有没有碰到过可以通过建立物理模型且运用了物理基本原理来得到解析解的数学题? 

前一个讨论
为什么现在拍不出来《家有儿女》《武林外传》这样的情景喜剧?
下一个讨论
日本文化与韩国文化在世界的影响力何者较大?





© 2025-05-08 - tinynew.org. All Rights Reserved.
© 2025-05-08 - tinynew.org. 保留所有权利