六度空間理論的圖論法證明及應(yīng)用

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

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

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

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

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

1 算法設(shè)計(jì)

1.1 最短路徑

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

1.2 Dijkastra算法

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

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

{ int n=G.Vertex;

int *s=new int [n];? ? ? ?//s用來(lái)存放n個(gè)頂點(diǎ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)記頂點(diǎn)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)記頂點(diǎn)u已從集合T加入到集合S中

for（j=0;j

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

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

path[j]=u;

}

}

}

1.3 圖論法描述

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

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

1.4 圖論法證明

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

void SixDegree_BFS（Graph G，Vtertex StartVertex）

{

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

Vertex? v，w;

long int VisitedCount=0;? ? ? //統(tǒng)計(jì)路徑長(zhǎng)度不超過(guò)6的頂點(diǎn)數(shù)目

int length;

for（v=0;v

Visited[v]=False;

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

Q=InitQueue（G.size）;? ? ? ? ?//初始化生成空的隊(duì)列

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的尚未訪問(wèn)的鄰接點(diǎn)

Visited[w]=True;? ? ? ? //將w標(biāo)志為六度頂點(diǎn)

VisitedCount++;? ? ? ? //增加路徑長(zhǎng)度不超過(guò)6的頂點(diǎn)總數(shù)

AddQueue（Q，w）;

}

}

cout<<“從頂點(diǎn)”<

}

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

2 算法分析

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

3 具體應(yīng)用

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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