-
2021-11-19 21:11:22
一、实验题目
六度空间理论是一个数学领域的猜想,又称为六度分割理论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家米格兰姆(Stanley Milgram) 提出的,理论指出:你和任何一个陌生人之间所间隔的人不会超过6个,也就是说,最多通过6个中间人你就能够认识任何一个陌生人。
1.案例分析
六度空间理论的数学模型属于图结构,我们把六度空间理论中的人际关系网络图抽象成一个不带权值的无向图G, 用图G 中的一个顶点表示一个人,两个人 ”认识” 与否,用代表这两个人的顶点之间是否有一条边来表示。这样六度空间理论问题便可描述为:在图 G 中任意两个顶点之间都存在一条路径长度不超过7的路径。 在实际验证过程中,可以通过测试满足要求的数据达到一定的百分比(比如 99.5%) 来进行验证。 这样我们便把待验证六度空间理论问题描述为:在图G 中,任意一个顶点到其余 99.5%以上的顶点都存在一条路径长度不超过 7 的路径。比较简单的一种验证方案是:利用广度优先搜索方法, 对任意一个顶点,
更多相关内容 -
六度空间理论
2021-12-08 12:46:34“七度空间”理论hh 基于无向网的Dijsktra算法六度空间理论
描述
“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入
多组数据,每组数据m+1行。第一行有两个数字n和m,代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b,代表这两个人互相认识。当n和m都等于0时,输入结束。
输出
多组数据,每组数据m+1行。第一行有两个数字n和m,代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b,代表这两个人互相认识。当n和m都等于0时,输入结束。
输入样例 1
10 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 0 0
输出样例 1
1: 70.00% 2: 80.00% 3: 90.00% 4: 100.00% 5: 100.00% 6: 100.00% 7: 100.00% 8: 90.00% 9: 80.00% 10: 70.00% 1: 70.00% 2: 80.00% 3: 80.00% 4: 80.00% 5: 80.00% 6: 80.00% 7: 80.00% 8: 70.00% 9: 20.00% 10: 20.00%
AC 代码
#include <iostream> #include <cstdio> using namespace std; const int N = 100; typedef struct { int vexs[N]; int arcs[N][N]; int vexnum, arcnum; }AMGraph; void createUDN(AMGraph &g, int vexnum, int arcnum) // 这里创建的是无向网 { g.vexnum = vexnum; g.arcnum = arcnum; for (int i = 1; i <= vexnum; i++) g.vexs[i] = i; for (int i = 1; i <= vexnum; i ++) for (int j = 1; j <= vexnum; j ++) g.arcs[i][j] = N; for (int i = 0; i < arcnum; i ++) { int v1, v2; cin >> v1 >> v2; g.arcs[v1][v2] = 1; // 无向网的特性,对称和对角线为0 g.arcs[v2][v1] = 1; } for (int i = 1; i <= arcnum; i++) g.arcs[i][i] = 0; } void shortPath_Dij(AMGraph g, int v1) { bool s[N]; // 表示是否找到了最短路径 int D[N]; // 表示该点到起点的距离 for (int i = 1; i <= g.vexnum; i++) { s[i] = false; D[i] = g.arcs[v1][i]; } s[v1] = true; D[v1] = 0; int min; int tmp; for (int v = 1; v < g.vexnum; v++) // 寻求的次数 { for (int i = 1; i <= g.vexnum; i++) { min = N; if (!s[i] && D[i] < min) { tmp = i; min = D[i]; } } s[tmp] = true; // 注意将这个的状态置为true,表示找到了最短路径 for (int i = 1; i <= g.vexnum; i++) if (!s[i] && (D[tmp] + g.arcs[tmp][i] < D[i])) D[i] = D[tmp] + g.arcs[tmp][i]; } int cnt = 0; for (int i = 1; i <= g.vexnum; i++) if (D[i] <= 6) cnt++; double rate = ((double)cnt / g.vexnum) * 100; // 数据处理和符号要小心 printf("%d: %.2lf\%%\n",v1, rate); } int main() { int n, m; while (cin >> n >> m, n && m) { AMGraph g; createDN(g, n, m); for (int i = 1; i <= n; i++) // 进行遍历求最短路径 shortPath_Dij(g, i); } return 0; }
-
实例6.1 六度空间 (30 分)
2021-04-10 20:45:55“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤10 3 ,表示人数)、边数M(≤33×N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。
输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
输入样例:
10 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
输出样例:
1: 70.00% 2: 80.00% 3: 90.00% 4: 100.00% 5: 100.00% 6: 100.00% 7: 100.00% 8: 90.00% 9: 80.00% 10: 70.00%
思路:
一开始用的深搜,就是不行,好像是链会被截断所以不行,就换了广搜,直接通过。
代码:
#include<iostream> #include<string> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int f[1005][1005]; int n , m; int book[1005] , ans , e[1005]; struct stu { int kk; int s;//存储步数 }que[1005]; void bfs(int k) { int head = 1 , tail = 1 , cur; que[tail].kk = k; book[k] = 1; que[tail].s = 0; ans++;//加上自己本身 tail++; while(head < tail) { cur = que[head].kk; for(int i = 1 ; i <= n ; i++) { if(f[cur][i] == 1 && book[i] == 0) { book[i] = 1; que[tail].kk = i; que[tail].s = que[head].s + 1;//步数是父亲的步数加1 if(que[tail].s <= 6) ans++; else break; tail++; } } head++; } } int main() { cin>>n>>m; int x , y; for(int i = 1 ; i <= m ; i++) { cin>>x>>y; f[x][y] = 1;f[y][x] = 1; } for(int i = 1 ; i <= n ; i++) { memset(book , 0 , sizeof(book)); ans = 0; bfs(i); e[i] = ans; } for(int i = 1 ; i <= n ; i++) { cout<<i<<": "; printf("%.2f" , e[i]*1.0 / n * 100); cout<<"%"<<endl; } }
-
距离-六度空间理论感悟
2019-07-02 19:52:40在现实生活中,人际关系错综复杂,遇到难题,左右为难,致命问题保大保... 六度空间理论-在理论情况下,你与任何人的距离不超过6,即通过自我关系网,每一环节达到关系网的极值,不会超过6。然而在现实中,这个理论...在现实生活中,人际关系错综复杂,遇到难题,左右为难,致命问题保大保小、老妈还是老婆,这个是送命题,一般是不会出现,但是由于社会的发展,过年问题(孩子少,在哪里过年,另一方都会不热闹),这些困扰我们的问题,通过人与人的距离计算可以辅助我们做出选择。
六度空间理论-在理论情况下,你与任何人的距离不超过6,即通过自我关系网,每一环节达到关系网的极值,不会超过6。然而在现实中,这个理论只是纸上谈兵,例如我与某某名人,他们看都不会看我一眼,关系就等同我与路边的乞丐的关系,绝不是看不起乞丐。回到主题,距离,在学校,我们知道点与点的距离可以由公式得到,那么人与人的距离如何计算呢?有什么标准呢?人与人的距离可以解决人际关系吗?
以自己为例子,将朋友,同事,亲人划分三流九等,距离数据从1~5 ,其一为亲人初始为1, 其一为朋友初始为3,其一为其他人初始值为4,其他人包括同事、见过几面的陌生人,距离划分完成,每一个等级划分后,同等级也是有区别的,朋友有酒肉朋友,知心朋友等,等级划分完成,通过距离值得大小,即离中心的距离,决定着我们对人的态度,矛盾的时候的处理方法。有时候我也很困惑,明明距离是4甚至是5,却做着3才能做的事情,陌生人应该有陌生人的状态,在力所能及和不给他人带来麻烦的情况下,可以适当帮助。
距离也不是一成不变的,人与人的距离随着关系的相处,可以做加减法,随着距离的变迁,等级也会跨越,比如从陌生人到达朋友,再如亲人冷漠也会变为陌生人。
-
六度空间系统开发(APP理论)
2020-10-28 17:37:25六度空间系统开发(APP理论) 首先说一下六度空间系统的含义:小世界现象(又称小世界效应),也称六度空间APP理论。 这种现象,并不是说任何人与其他人之间的联系都必须通过六个层次才会产生联系,而是表达了这样一... -
六度空间
2015-03-21 15:46:45六度空间理论,又名六度分隔理论,意思是你至多只要通过六个人就能认识全世界的任意一个人,可以这样算:假设一个人能认识25个人或以上,那经过7次介绍之后(间隔6人),一个人可以被介绍给25的7次方,等于6103515625... -
浙大数据结构: 06-图3 六度空间 (30 分) BFS与DFS方法
2019-08-27 14:14:15“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如... -
PTA-六度空间-BFS
2020-06-10 21:13:24“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如... -
六度空间理论算法及在好友推荐中应用(加批)
2011-10-14 11:48:31【六度空间算法理论简介】 有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论或小世界理论等。 理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是... -
06-图3 六度空间 (30分)
2020-11-11 09:24:15“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如... -
PTA-06-图3 六度空间 (30 分)为什么不能用DFS
2019-11-01 15:10:47“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如... -
7-7 六度空间(30 分)(图的遍历)
2018-03-05 22:07:35“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如... -
尺度空间理论与图像金字塔
2018-03-06 15:55:20我们之所以决定使用卷积后的特征是...1尺度空间理论每个物体,我们总可以用一些词语或部件来描述它,比如人脸的特征:两个眼睛、一个鼻子和一个嘴巴。对于图像而言,我们需要计算机去理解图像,描述图像就需要计算... -
#第六章 四维股市理论数学模型基础6.1四维股市拟合理论的数学基础
2020-06-09 09:18:00我把用三维或三维以下的数学方法解读四维或四维以上数学现象的理论暂且称为伪四维或者跨维解读。实际上,这类理论已经发现三维数学系统中存在的不足,从而通过增加考量因素的方法试图解决跨维解读的问题。 历史上,... -
数据库系统概论——第六章 关系数据理论
2020-01-27 19:40:06数据库系统概论——第六章 关系数据理论 (零)引言 基于某个数据库管理系统设计数据库,如何基于数据库编程 第6章 关系数据理论 第7章 数据库设计 第8章 数据库编程 (一) 问题的提出 一、 关系数据库逻辑设计 (1... -
MySQL | 数据库基础理论、六大设计范式详解
2019-05-09 04:16:34从本篇博文开始,会陆续介绍MySQL数据库的相关内容,分为以下几个部分: 数据库基础理论 基本CURD操作(常用SQL) 索引及其底层实现原理 MySQL体系结构与存储引擎 MySQL优化之SQL和索引的优化、应用优化、MySQL ... -
机器学习(六)统计学习理论
2018-03-09 21:19:01统计学习理论的意义 统计学习理论提供了机器学习的一个理论基础。通过理论推导,从本质上说明了机器学习为什么会出现过拟合现象,以及过拟合与模型选择、训练数据之间有什么关系。 数学推导 设训练集S={(xi,yi)... -
一文带你看懂~混沌理论
2019-10-28 23:07:00混沌理论 相信大家听过这样一个实验:量子薛定谔的猫。 实验是这样的:在一个普通盒子里有一只小花猫,以及少量放射性物质。之后,有50%的概率放射性物质将会衰变并释放出毒气杀死这只小花猫,同时有50%的概率放射... -
【土地评价与土地管理】案例:某地区柑橘种植适宜性评价
2021-03-06 22:11:05文章目录一、确定评价单元二、评价因子选择三、评价因子权重的确定四、构建评价分级标准五、综合评价六、适宜性等级划分七、得出适宜性评价结果 柑橘种植所需的自然条件: 柑橘果树生长发育、开花结果与温度、日照... -
测试理论面试题
2019-11-06 09:13:26这个要充分准备,最好能举出例子(非常考察课外积累和工作经验!) 几种常见的测试方法:错误推断法、正交实验法、因果图法、场景分析法、判定表法,必须对这些测试方法都能说出一二,面试官很有可能根据你说的... -
软件测试基础知识 + 面试理论(超详细)
2021-02-25 10:47:13三、软件测试工程师的工作内容四、常见的软件生命周期模型五、软件开发的几个阶段六、软件bug的五个要素七、软件测试的分类八、什么是测试用例九、测试用例几大要素【面试理论知识】1、你的测试职业发展是什么?... -
第六章 电磁新理论
2015-04-16 17:15:09第六章 电磁新理论 声明 本人自称:三空道士。可看作是社会底层的无业游民,也无不妥。虽修行于俗世,甘于过平淡艰苦的隐居生活,但从不放弃对宇宙真理的探索。因学艺不精、情关难过,在我的博客文章会充满... -
《网络空间内生安全》读书笔记:第六章 内生安全与可靠性技术
2020-07-16 15:53:30第六章 内生安全与可靠性技术 网络空间最大的安全威胁是**基于目标对象内生安全问题的不确定攻击* 网络空间最大的防御难题是在缺乏先验知识条件下能否可靠应对基于未知的未知因素的不确定攻击 最大的... -
扩张的矩阵三要素——时间、空间和事件
2020-09-12 07:35:06甚至是通过三个要素的组合和不同颗粒度的划分,创造出全新的使用场景,使产品进入空白的市场实现新的扩张和增长。 时间 本篇我们从场景的第一个要素时间来看。时间相对于另外两个要素空间和实物更加的线性和... -
因果推断笔记——自整理因果推断理论解读(七)
2021-09-04 11:26:13之前有整理过一篇:因果推断笔记—— 相关理论:Rubin Potential、Pearl、倾向性得分、与机器学习异同(二) 不过,那时候刚刚开始学,只能慢慢理解,所以这边通过一轮的学习再次整理一下手里的笔记。 文章目录1 ... -
混沌性时间序列的分析方法:EEMD+相空间重构
2019-10-30 22:55:05上一篇文章中,我们理解了混沌理论的发展、定义以及特点。接下来,要结合我的研究方向,在机械振动时间序列信号的基础上,做出故障的诊断和预判。 由于篇幅的限制,本文以轴承信号为例,着重讨论混沌性的判定方法。... -
算法理论基础
2019-03-14 13:32:37:利用已有样本生成更多样本,这类方法在小数据场景下有很多成功案例,比如医学图像分析等。 SMOTE为每个小众样本合成相同数量的新样本,这带来一些潜在的问题: 一方面是增加了类之间重叠的可能性,另一方面...