六度空間理論的圖論法證明及應用

摘? 要： 從六度空間理論的假設入手，結合數據結構中圖論的相關知識及圖論中的最短路徑問題，從理論上闡述并分析驗證六度空間理論的思想方法，設計了驗證算法，分析了算法的性能，在此基礎上總結并推導出該理論在互聯網中的應用。

關鍵詞： 數據結構; 六度空間; 最短路徑; 算法

中圖分類號：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