摘? 要： 從六度空間理論的假設(shè)入手，結(jié)合數(shù)據(jù)結(jié)構(gòu)中圖論的相關(guān)知識及圖論中的最短路徑問題，從理論上闡述并分析驗證六度空間理論的思想方法，設(shè)計了驗證算法，分析了算法的性能，在此基礎(chǔ)上總結(jié)并推導(dǎo)出該理論在互聯(lián)網(wǎng)中的應(yīng)用。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu); 六度空間; 最短路徑; 算法

中圖分類號：TP392? ? ? ? ? 文獻(xiàn)標(biāo)志碼：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）理論。該理論可以通俗地描述為：“您和這個地球上任何一個陌生人之間所間隔的人數(shù)不會超過六個，也就是說，最多通過五個人您就能夠認(rèn)識世界上任何一個陌生人?！痹摾碚撟钤绠a(chǎn)生于20世紀(jì)60年代，是由美國心理學(xué)家米爾格倫提出。該設(shè)想透露出這樣一個概念：兩個素不相識的人，通過一定的方式，總能夠產(chǎn)生必然的聯(lián)系或形成相應(yīng)的關(guān)系。

近年來，六度空間理論的應(yīng)用價值越來越受到更多人的關(guān)注。不管是現(xiàn)實生活中的人際網(wǎng)絡(luò)還是Web的構(gòu)架，或者是通過超文本鏈接的網(wǎng)絡(luò)，再如經(jīng)濟(jì)活動中的商業(yè)聯(lián)系網(wǎng)絡(luò)，以及生態(tài)系統(tǒng)中的食物鏈等等，甚至是人類腦神經(jīng)元以及細(xì)胞內(nèi)的分子交互作用網(wǎng)絡(luò)，都有著非常相似的組織結(jié)構(gòu)。利用計算機(jī)網(wǎng)絡(luò)使六度空間理論在人與人之間構(gòu)成“弱紐帶”，通過弱紐帶會讓人與人之間的距離變得更為“貼近”，這在整個社會關(guān)系中可以發(fā)揮強(qiáng)大的作用。

六度空間理論雖然在現(xiàn)實中屢屢應(yīng)驗，但在過去的數(shù)十年里，卻從來沒有得到過嚴(yán)謹(jǐn)?shù)淖C明。IEEE-CS/ACM 的CS2008 教程將數(shù)據(jù)結(jié)構(gòu)課程列為計算機(jī)類核心課程之首，報告分析數(shù)據(jù)結(jié)構(gòu)課程在信息學(xué)科中的重要地位和該課程對程序設(shè)計能力培養(yǎng)的重要作用[1] 。這里結(jié)合數(shù)據(jù)結(jié)構(gòu)學(xué)科中圖論的相關(guān)知識及圖論中的最短路徑問題，從理論上闡述并分析驗證六度空間理論的思想方法。

1 算法設(shè)計

1.1 最短路徑

Dijkstra算法是求有向圖中從某一源點到其余各點最短路徑的算法[2]。對于圖中從一個確定頂點到其余各頂點的最短路徑問題，Dijkastra提出了一個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的構(gòu)造算法。其基本思想是：首先設(shè)置兩個頂點的集合S和T，集合S中存放已經(jīng)找到的最短路徑頂點序列，集合T中存放當(dāng)前還未找到的最短路徑頂點序列[3]。初始狀態(tài)時，集合S中只包含圖中源點，這里設(shè)為V0，然后從集合T中選擇到源點V0路徑長度最短的頂點u加入到集合S中，集合S中每加入一個新的頂點u都要修改源點v0到集合T中剩余頂點的當(dāng)前最短路徑長度值，集合T中各頂點的新的當(dāng)前最短路徑長度值，為原來的當(dāng)前最短路徑長度值與從源點經(jīng)過頂點u到達(dá)該頂點的路徑長度中的較小者[4]。此操作不斷重復(fù)，直到集合T中的頂點全部加入到集合S中為止。

1.2 Dijkastra算法

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

//帶權(quán)圖G從下標(biāo)StartVertex頂點到其它頂點的最短距離distance和相應(yīng)的目標(biāo)頂點的//前一頂點下標(biāo)path

{ int n=G.Vertex;

int *s=new int [n];? ? ? ?//s用來存放n個頂點的標(biāo)記

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;? ? ? ? ? ? ?//標(biāo)記頂點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;? ? ? ? ? //標(biāo)記頂點u已從集合T加入到集合S中

for（j=0;j

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

{ distance[j]=distance[u]+G.Weight（u，j）;? //頂點StartVertex經(jīng)頂點u到其它頂點的最短//距離和最短路徑

path[j]=u;

}

}

}

1.3 圖論法描述

結(jié)合六度空間理論的基本思想，該理論可以形式化描述成圖論中的最短路徑問題：首先，用一個無向圖G來表示K個人的人際關(guān)系網(wǎng)絡(luò)圖。假定有K（K=10億）個人，用G中的一個頂點代表1個人，則該圖共有F=109個頂點。如果兩個人認(rèn)識，就在代表兩個人的頂點之間添加一條邊表示，這里假定平均每個人“認(rèn)識”150 個人，則圖G大約有150*K/2=75*109條邊，記為E，并設(shè)每條邊上的權(quán)值都為1。這樣，六度空間理論可以描述為：在人際關(guān)系網(wǎng)絡(luò)圖G中，任意兩個頂點之間都有一條最短路徑不超過6的路徑。

每次以某個頂點為源點，執(zhí)行上述Dijkstra算法，可以計算出一個人到其余所有人之間的最短距離，由于該人際關(guān)系圖是稀疏矩陣，這里可以用鄰接表作為存儲結(jié)構(gòu)，再以二叉堆結(jié)構(gòu)執(zhí)行DeleteMin操作，則查找最小值的時間是O（log2V）[5]，V為圖中頂點的數(shù)目。該算法的時間復(fù)雜度改進(jìn)后約為T（n）=O（E*log2V）≈75*109*log2109≈75*109*30≈2250G，如果用每秒萬億次運算速度的計算機(jī)來執(zhí)行此算法，在幾秒鐘可以驗證一個頂點，每天可以驗證的人數(shù)近萬。當(dāng)求得一個人到其余所有人的最短距離后，就可以進(jìn)一步計算出最短距離不超過6的頂點在所有頂點中所占百分比例。

1.4 圖論法證明

上述算法理論上是可行的，但實際執(zhí)行時時間開銷較大，在此提出一種更簡便高效的算法。首先，把人際關(guān)系網(wǎng)絡(luò)圖G看成是一個不帶權(quán)的圖，然后，將六度空間理論理解為：在人際關(guān)系網(wǎng)絡(luò)圖G中，任意兩個頂點之間都存在一條路徑長度不超過6的路徑。這里采用圖的廣度優(yōu)先搜索（BFS）算法，以任意一個頂點作為起始頂點，通過對圖G的“6層”遍歷，就可以統(tǒng)計圖中所有路徑長度不超過6的頂點數(shù)目，從而得到這些頂點在所有頂點數(shù)目中所占的百分比例。相關(guān)算法如下：

void SixDegree_BFS（Graph G，Vtertex StartVertex）

{

Queue *Q;? ? ? ? ? ? ? ? ? ? ?//定義隊列，借用隊列完成圖的廣度優(yōu)先遍歷

Vertex? v，w;

long int VisitedCount=0;? ? ? //統(tǒng)計路徑長度不超過6的頂點數(shù)目

int length;

for（v=0;v

Visited[v]=False;

Visited[StartVertex]=True;? ? ?//將起始頂點的訪問標(biāo)志域置為真

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標(biāo)志為六度頂點

VisitedCount++;? ? ? ? //增加路徑長度不超過6的頂點總數(shù)

AddQueue（Q，w）;

}

}

cout<<“從頂點”<

}

這里沒有給出路徑上所經(jīng)過的中間頂點的編號及相關(guān)信息，如果需要這些信息，可以對該算法進(jìn)行修改后實現(xiàn)。

2 算法分析

算法分析的目的在于選擇合適算法和算法改進(jìn)，一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮[6]。該算法的時間復(fù)雜度是T（n）=O（E+V）≈75*109≈100G，對于現(xiàn)代計算機(jī)來說，以每秒萬億次的運算速度來執(zhí)行，每秒鐘可以驗證數(shù)個頂點，一天可以驗證數(shù)萬個頂點，即數(shù)萬人。再來分析其空間復(fù)雜度，該算法的空間復(fù)雜度與Dijkastra算法基本相當(dāng)，需要存儲Visited數(shù)組和當(dāng)前隊列數(shù)組，它們分別需要數(shù)G的存儲容量，這在實際中也是可行的。六度空間理論中所指的“每個人”應(yīng)該是指全世界的幾十億人口，所以上述算法從原理上可以應(yīng)用于地球上的每一個人。但是，出于現(xiàn)實生活中原始數(shù)據(jù)的可靠獲取受到限制來考慮，并出于對個人信息的保護(hù)來考慮，可以把測試范圍限定在某個固定的范圍區(qū)域內(nèi)。

3 具體應(yīng)用

六度空間理論和互聯(lián)網(wǎng)的親密結(jié)合，已經(jīng)開始顯露出其商業(yè)價值。研究人員近年來傾向于關(guān)注社會網(wǎng)絡(luò)的研究，很多網(wǎng)絡(luò)軟件也開始支持人們建立更加互信和緊密的社會關(guān)聯(lián)，這些軟件被統(tǒng)稱為“社會性軟件”（Social Software）。該類軟件的核心思想是聚合產(chǎn)生的效應(yīng)。隨著Internet的迅猛發(fā)展，尤其是WWW（Worl Wide Web）的全球普及，使互聯(lián)網(wǎng)上的信息豐富無比，如何快速準(zhǔn)確的提取出人們所關(guān)心和需要的內(nèi)容是非常重要的，也是Web信息提取所研究的主要問題，筆者認(rèn)為可以利用六度空間理論所折射出的聚合效應(yīng)，設(shè)計出相應(yīng)算法，通過標(biāo)記識別，統(tǒng)計出一篇文檔中某些“突發(fā)性”或“積聚性”增長的文字信息，而這些信息極有可能是最新的趨勢和相關(guān)熱點問題，因為此類信息的最大特征就是短期內(nèi)迅速膨脹，通過此方法可以更有效地篩選出重要信息，這也彌補(bǔ)了傳統(tǒng)搜索技術(shù)只簡單統(tǒng)計文字/單詞出現(xiàn)頻率，而忽略了文字使用增長的速率這一不足。此類算法一經(jīng)成熟便可應(yīng)用于Web信息提取中，可以將信息提取技術(shù)推進(jìn)到一個新的高度。

4 結(jié)束語

本文結(jié)合數(shù)據(jù)結(jié)構(gòu)中的圖論知識，對六度空間理論進(jìn)行了分析和圖論法證明。該算法所折射的聚合效應(yīng)，可以應(yīng)用在Web信息提取領(lǐng)域，提高信息提取的精準(zhǔn)性。在成功構(gòu)建算法模型的基礎(chǔ)上，后續(xù)工作是測試數(shù)據(jù)的進(jìn)一步收集與算法運行，進(jìn)而，與信息提取技術(shù)有效地融合并最終服務(wù)于Web信息提取。

參考文獻(xiàn)（References）：

[1] 袁宇麗.數(shù)據(jù)結(jié)構(gòu)線性探測法在隨機(jī)出題中的應(yīng)用[J].內(nèi)江師范學(xué)院學(xué)報，2014.4：19-22

[2] 一種改進(jìn)的Dijkstra算法的分析及程序?qū)崿F(xiàn)[J].計算機(jī)與現(xiàn)代化，2011（1）：36-38

[3] 耿國華.數(shù)據(jù)結(jié)構(gòu)—C語言描述[M].北京：高等教育出版社，2011：253-255

[4] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)（C++語言描述）[M].北京：高等教育出版社，2010：203.

[5] 陳越.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，2012：243.

[6] 喬亞男.算法設(shè)計與問題求解[M].北京：高等教育出版社，2018：6