网站建设立项申请报告,免费广告设计模板网站,手机软件商店,线上店铺思维导图#xff1a; 6.7 案例分析与实现
#### 案例6.2: 六度空间理论
【案例分析】
- **背景介绍**#xff1a; 六度空间理论提及在任意两人之间最多仅有6个人的连接。尽管这一理论被广泛提及并得到了某种程度的验证#xff0c;但从科学角度看#xff0c;它仍然只是一…
思维导图 6.7 案例分析与实现
#### 案例6.2: 六度空间理论
【案例分析】
- **背景介绍** 六度空间理论提及在任意两人之间最多仅有6个人的连接。尽管这一理论被广泛提及并得到了某种程度的验证但从科学角度看它仍然只是一个假说。
- **早期验证** 很多社会学家使用E-mail进行的验证研究。其中最著名的是2001年由美国哥伦比亚大学的Duncan J. Watts所进行的实验。他们的研究表明要通过邮件与某人联系平均需要经过57个中间人。
- **研究局限性** 1. 使用E-mail保持社会关系的人群是有限的 2. 跟踪E-mail的路径需要大量资源 3. 研究依赖于志愿者的积极性可能会有遗漏。
- **现代通信方法** 电话和短信是现代主流的通信方式与E-mail相比由于运营商的存在其通信路径更容易跟踪。但由于数据保密我们很难获取实际的通信数据。
- **理论模型** 我们可以将人际关系视为一个不带权值的无向图G。在此模型中六度空间理论可以被描述为在图G中任意两个顶点之间的路径长度不超过7。
【案例实现】
- **算法6.14 六度空间理论的验证** - **初始化** 设定一个变量Visit Num来记录路径长度不超过7的顶点数。初始化为0。数组level记录各个层次的顶点数。选择一个起始点Start标记为已访问并将其放入队列Q。 - **广度优先搜索** 当Q非空且循环次数小于7时执行以下操作 1. 取出队头顶点u 2. 检查u的所有未访问的邻接点w 3. 将w标记为已访问路径长度不超过7的顶点数Visit Num加1相应的层次顶点数也加1 4. 将w入队。 - **输出结果** 当退出循环后输出从顶点Start到其他所有顶点的路径长度不超过7的百分比。
**笔记总结**六度空间理论是一个有趣且广为人知的假说。尽管它在某种程度上得到了验证但从科学的角度来看仍存在局限性。现代的通信方式为其验证提供了新的机会但也带来了新的挑战。 **笔记六度空间理论的验证算法描述**
---
**算法名称**: 六度空间理论的验证
**方法**: 通过广度优先搜索 (BFS) 遍历图 G 来验证六度空间理论。
**输入**: 图 G, 指定的始点 Start
**主要步骤**: 1. 初始化 Visit Num 为 0用于记录路径长度不超过 7 的顶点个数。 2. 标记顶点 Start 已被访问并将其添加到队列 Q。 3. 初始化第一层人队的顶点个数为 1。 4. 使用循环进行广度优先搜索遍历 - 对于每个长度在 1 到 6 范围内的路径只要队列不为空执行以下操作 1. 队头顶点 u 出队。 2. 检查 u 的所有邻接点 w。 3. 如果 w 尚未被访问则标记 w 为六度顶点并增加 Visit Num 和该层的顶点数。 4. 将 w 添加到队列 Q。 5. 输出从顶点 Start 到其他顶点的路径长度不超过 7 的路径的百分比。
**算法分析**: - 时间复杂度: 假设图 G 中有 10 亿人即图的顶点个数 n 10亿。若平均每人认识 150 人则边数 e 约为 75 x 10^8。该算法的时间复杂度为 O(ne)。 - 空间复杂度: 该算法需要数组 visited 和队列 Q因此空间复杂度为 O(m)。 - 假设平均每个人都认识其他 150 个人基于“150定律”。
**其他方法**: 算法6.14 使用广度优先搜索方法进行验证实际上也可以使用求解最短路径的方法如迪杰斯特拉算法或弗洛伊德算法进行理论验证。
---
