1、小世界,作者：谢莉娟093667刘萍093651,2,小世界,3,从这个星球上任何地方随意挑选的任何两个人，都可以通过一条很短的“相识关系链”彼此“相连”。维萨（Ouisa）,4,六度分离,这星球上的每一个人都不过是被其他六个人分隔开来。也就是在我们与这个星球上的另外一个任何一个人之间的六度分离关系。,小世界的发展,20世纪50年代到60年代，芝加哥大学的阿纳托尔拉波波特和他的同事建立了“随机有偏网络”理论。20世纪60年代，伊锡尔德柯亨进行了初步的数学分析，得出三度分离。,5,”随机有偏网络”,：新成员被感染比例k：每个元素都有相同的连接数目,6,图论背景定义,图包括：顶点，边图的性质与分类
2、：（1）无向（2）未加权：没有为边指定任何优先强度（3）简单：不能用多边连接同一对顶点（4）连通性：任何定点都已通过由有限个数的边所构成的路径到达任何其他顶点,7,图论背景特殊类型图之格图,定义：一个d-格是带标号、未加权、无方向的简单图，这种简单图与d维欧几里得立方格相似。,8,K=4的1-格的例子,9,K=2的1-格的例子,K=4的2-格的例子（边界是周期性的）,10,K=8的2-格的一个顶点,11,图模型 模型,【预备知识】卡夫曼世界 你认识的每个人除了认识你认识的其他人以外，不认识任何其他人阳光浴室 未来的人类各自孤立居住，通过机器人和计算机相互接触,12,卡夫曼与阳光浴室的关系图,1
3、3,成为朋友的可能,共同朋友占所有朋友的比例,卡夫曼,阳光浴室,14,成为朋友的可能,共同朋友占所有朋友的比例,卡夫曼,阳光浴室,结构,=顶点i与j向量的可能性的量度 =与i和j都相邻接的顶点的数目 k = 图的平均度 =一个可调参数0， ）,15,的标准化,16,模型算法,固定一个顶点i对每一另外的顶点j，计算将结果标准化，从而得到变量生成一个位于（0,1）区间内的随机变量，它必定落在某个子区间内，亦即，与j*一致的那一个连接i和j*,17,18,=0 连通性问题,如果 =0 ，那么， ，很明 显，该值非常小。相比之下，如果，无论多 么小，都有。这意味着，所有标准化后的落入的单位区间，几乎完全被代表那些与定点i已有共同连接的定点的子区间覆盖。,19,=0 连通性问题,因此，给定了一个当前“朋友”子图，明显完全有可能加入新“朋友”，并且这些新朋友不断增加与孩子图的互联，而该子图并没有向新的领域延伸很多。,20,当 值较小时（ 1）连通性较弱的聚类中产生的结果更像高度内部连通的聚类，如连通的卡夫曼图当 值较大时（ 11）近似于随机图，所以可以称这个 区间的图“小”对于中间的 值，有一个非常迅速的但又很光滑的从“大”图到“小”图的过渡,21,作者：谢莉娟 刘萍,
