六度空间理论的图论法证明及应用

摘  要： 从六度空间理论的假设入手，结合数据结构中图论的相关知识及图论中的最短路径问题，从理论上阐述并分析验证六度空间理论的思想方法，设计了验证算法，分析了算法的性能，在此基础上总结并推导出该理论在互联网中的应用。

关键词： 数据结构; 六度空间; 最短路径; 算法

中图分类号：TP392          文献标志码：A     文章编号：1006-8228（2019）12-54-03

The graph theory proof of six degrees of separation and the application

Yuan Yuli

（Department of Computer Science， Neijiang Normal University， Neijiang， Sichuan 641100， China）

Abstract： Starting from the hypothesis of theory of six degrees of space （also known as six degrees of separation）， based on the relevant knowledge of graph theory in data structure and the shortest path problem in graph theory， this paper theoretically analyzes and verifies the thinking method of six degrees of space theory， designs the verification algorithm， and analyzes the performance of the algorithm. On this basis， a summary is made and the application of the theory in the Internet is deduced thereafter.

Key words： data structure; six degrees of space; the shortest path; algorithm

0 引言

“六度空间”理论又可称作“六度分隔”（Six Degrees of Separation）理论。该理论可以通俗地描述为：“您和这个地球上任何一个陌生人之间所间隔的人数不会超过六个，也就是说，最多通过五个人您就能够认识世界上任何一个陌生人。”该理论最早产生于20世纪60年代，是由美国心理学家米尔格伦提出。该设想透露出这样一个概念：两个素不相识的人，通过一定的方式，总能够产生必然的联系或形成相应的关系。

近年来，六度空间理论的应用价值越来越受到更多人的关注。不管是现实生活中的人际网络还是Web的构架，或者是通过超文本链接的网络，再如经济活动中的商业联系网络，以及生态系统中的食物链等等，甚至是人类脑神经元以及细胞内的分子交互作用网络，都有着非常相似的组织结构。利用计算机网络使六度空间理论在人与人之间构成“弱纽带”，通过弱纽带会让人与人之间的距离变得更为“贴近”，这在整个社会关系中可以发挥强大的作用。

六度空间理论虽然在现实中屡屡应验，但在过去的数十年里，却从来没有得到过严谨的证明。IEEE-CS/ACM 的CS2008 教程将数据结构课程列为计算机类核心课程之首，报告分析数据结构课程在信息学科中的重要地位和该课程对程序设计能力培养的重要作用[1] 。这里结合数据结构学科中图论的相关知识及图论中的最短路径问题，从理论上阐述并分析验证六度空间理论的思想方法。

1 算法设计

1.1 最短路径

Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法[2]。对于图中从一个确定顶点到其余各顶点的最短路径问题，Dijkastra提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法。其基本思想是：首先設置两个顶点的集合S和T，集合S中存放已经找到的最短路径顶点序列，集合T中存放当前还未找到的最短路径顶点序列[3]。初始状态时，集合S中只包含图中源点，这里设为V0，然后从集合T中选择到源点V0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u都要修改源点v0到集合T中剩余顶点的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点经过顶点u到达该顶点的路径长度中的较小者[4]。此操作不断重复，直到集合T中的顶点全部加入到集合S中为止。

1.2 Dijkastra算法

void Dijkstra（Graph G， int StartVertex，int distance[]，int path[]）

//带权图G从下标StartVertex顶点到其它顶点的最短距离distance和相应的目标顶点的//前一顶点下标path

{ int n=G.Vertex;

int *s=new int [n];       //s用来存放n个顶点的标记

int minDis，I，j，u;

for（i=0;i

{ distance[i]=G.Weight（StartVertex，i）;

s[i]=0;

if（i！=StartVertex && distance[i]

path[i]=StartVertex;

else path[i]=-1;

}

s[StartVertex]=1;             //标记顶点StartVertex已从集合T加入到集合S中

for（i=1;i

{ minDis=MaxWeight;

for（j=0;j

if（s[j]==0 && distance[j]

{

u=j;

minDis=distance[j];

}

if（minDis==MaxWeigth return;

s[u]=1;          //标记顶点u已从集合T加入到集合S中

for（j=0;j

if（s[j]==0 && G.Weight（u，j）

{ distance[j]=distance[u]+G.Weight（u，j）;  //顶点StartVertex经顶点u到其它顶点的最短//距离和最短路径

path[j]=u;

}

}

}

1.3 图论法描述

结合六度空间理论的基本思想，该理论可以形式化描述成圖论中的最短路径问题：首先，用一个无向图G来表示K个人的人际关系网络图。假定有K（K=10亿）个人，用G中的一个顶点代表1个人，则该图共有F=109个顶点。如果两个人认识，就在代表两个人的顶点之间添加一条边表示，这里假定平均每个人“认识”150 个人，则图G大约有150*K/2=75*109条边，记为E，并设每条边上的权值都为1。这样，六度空间理论可以描述为：在人际关系网络图G中，任意两个顶点之间都有一条最短路径不超过6的路径。

每次以某个顶点为源点，执行上述Dijkstra算法，可以计算出一个人到其余所有人之间的最短距离，由于该人际关系图是稀疏矩阵，这里可以用邻接表作为存储结构，再以二叉堆结构执行DeleteMin操作，则查找最小值的时间是O（log2V）[5]，V为图中顶点的数目。该算法的时间复杂度改进后约为T（n）=O（E*log2V）≈75*109*log2109≈75*109*30≈2250G，如果用每秒万亿次运算速度的计算机来执行此算法，在几秒钟可以验证一个顶点，每天可以验证的人数近万。当求得一个人到其余所有人的最短距离后，就可以进一步计算出最短距离不超过6的顶点在所有顶点中所占百分比例。

1.4 图论法证明

上述算法理论上是可行的，但实际执行时时间开销较大，在此提出一种更简便高效的算法。首先，把人际关系网络图G看成是一个不带权的图，然后，将六度空间理论理解为：在人际关系网络图G中，任意两个顶点之间都存在一条路径长度不超过6的路径。这里采用图的广度优先搜索（BFS）算法，以任意一个顶点作为起始顶点，通过对图G的“6层”遍历，就可以统计图中所有路径长度不超过6的顶点数目，从而得到这些顶点在所有顶点数目中所占的百分比例。相关算法如下：

void SixDegree_BFS（Graph G，Vtertex StartVertex）

{

Queue *Q;                     //定义队列，借用队列完成图的广度优先遍历

Vertex  v，w;

long int VisitedCount=0;      //统计路径长度不超过6的顶点数目

int length;

for（v=0;v

Visited[v]=False;

Visited[StartVertex]=True;     //将起始顶点的访问标志域置为真

Q=InitQueue（G.size）;         //初始化生成空的队列

AddQueue（Q，StartVertex）;

for（length=1;length<=6 && ！IsEmptyQueue（Q）; length++）

{  v=DeleteQueue（Q）;

for（w=FirstAdjVertex（G，v）; w！=0; w=NextAdjVertex（G，v，w））

if（！Visited[w]）           //若w是v的尚未访问的邻接点

Visited[w]=True;        //将w标志为六度顶点

VisitedCount++;        //增加路径长度不超过6的顶点总数

AddQueue（Q，w）;

}

}

cout<<“从顶点”<

}

这里没有给出路径上所经过的中间顶点的编号及相关信息，如果需要这些信息，可以对该算法进行修改后实现。

2 算法分析

算法分析的目的在于选择合适算法和算法改进，一个算法的评价主要从时间复杂度和空间复杂度来考虑[6]。该算法的时间复杂度是T（n）=O（E+V）≈75*109≈100G，对于现代计算机来说，以每秒万亿次的运算速度来执行，每秒钟可以验证数个顶点，一天可以验证数万个顶点，即数万人。再来分析其空间复杂度，该算法的空间复杂度与Dijkastra算法基本相当，需要存储Visited数组和当前队列数组，它们分别需要数G的存储容量，这在实际中也是可行的。六度空间理论中所指的“每个人”应该是指全世界的几十亿人口，所以上述算法從原理上可以应用于地球上的每一个人。但是，出于现实生活中原始数据的可靠获取受到限制来考虑，并出于对个人信息的保护来考虑，可以把测试范围限定在某个固定的范围区域内。

3 具体应用

六度空间理论和互联网的亲密结合，已经开始显露出其商业价值。研究人员近年来倾向于关注社会网络的研究，很多网络软件也开始支持人们建立更加互信和紧密的社会关联，这些软件被统称为“社会性软件”（Social Software）。该类软件的核心思想是聚合产生的效应。随着Internet的迅猛发展，尤其是WWW（Worl Wide Web）的全球普及，使互联网上的信息丰富无比，如何快速准确的提取出人们所关心和需要的内容是非常重要的，也是Web信息提取所研究的主要问题，笔者认为可以利用六度空间理论所折射出的聚合效应，设计出相应算法，通过标记识别，统计出一篇文档中某些“突发性”或“积聚性”增长的文字信息，而这些信息极有可能是最新的趋势和相关热点问题，因为此类信息的最大特征就是短期内迅速膨胀，通过此方法可以更有效地筛选出重要信息，这也弥补了传统搜索技术只简单统计文字/单词出现频率，而忽略了文字使用增长的速率这一不足。此类算法一经成熟便可应用于Web信息提取中，可以将信息提取技术推进到一个新的高度。

4 结束语

本文结合数据结构中的图论知识，对六度空间理论进行了分析和图论法证明。该算法所折射的聚合效应，可以应用在Web信息提取领域，提高信息提取的精准性。在成功构建算法模型的基础上，后续工作是测试数据的进一步收集与算法运行，进而，与信息提取技术有效地融合并最终服务于Web信息提取。

参考文献（References）：

[1] 袁宇丽.数据结构线性探测法在随机出题中的应用[J].内江师范学院学报，2014.4：19-22

[2] 一种改进的Dijkstra算法的分析及程序实现[J].计算机与现代化，2011（1）：36-38

[3] 耿国华.数据结构—C语言描述[M].北京：高等教育出版社，2011：253-255

[4] 朱战立.数据结构（C++语言描述）[M].北京：高等教育出版社，2010：203.

[5] 陈越.数据结构[M].北京：高等教育出版社，2012：243.

[6] 乔亚男.算法设计与问题求解[M].北京：高等教育出版社，2018：6