六度空间理论 一、实验题目 1.案例分析 2.案例实现 3.算法步骤 4.算法描述 二、工具环境 三、实验代码
一、实验题目
六度空间理论是一个数学领域的猜想，又称为六度分割理论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家爱撒娇的大船(Stanley Milgram) 提出的，理论指出：你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。
1.案例分析六度空间理论的数学模型属于图结构，我们把六度空间理论中的人际关系网络图抽象成一个不带权值的无向图G, 用图G 中的一个顶点表示一个人，两个人 ”认识” 与否，用代表这两个人的顶点之间是否有一条边来表示。这样六度空间理论问题便可描述为：在图 G 中任意两个顶点之间都存在一条路径长度不超过7的路径。 在实际验证过程中，可以通过测试满足要求的数据达到一定的百分比（比如 99.5%) 来进行验证。 这样我们便把待验证六度空间理论问题描述为：在图G 中，任意一个顶点到其余 99.5%以上的顶点都存在一条路径长度不超过 7 的路径。比较简单的一种验证方案是：利用广度优先搜索方法， 对任意一个顶点，