社交網(wǎng)絡(luò)中低代價(jià)路徑發(fā)現(xiàn)

張若愚

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

六度空間理論[1]（Six Degrees of Separation）是上世紀(jì)60年代心理學(xué)教授Stanley Milgram提出的，又稱為六度分割理論。該理論指出：任何兩個(gè)陌生人之間，最多通過六個(gè)人，就可以建立聯(lián)系。用一個(gè)簡單的說法，最多通過六個(gè)中間人，你能夠認(rèn)識(shí)任何一個(gè)原本素不相識(shí)的人。

六度空間理論旨在呈現(xiàn)出這一概念：世界很小，研究表明，在某些特定的社交網(wǎng)絡(luò)中，任意的兩個(gè)節(jié)點(diǎn)可能通過更少的中間節(jié)點(diǎn)就能聯(lián)系起來。Lars Back?stromd等人在Facebook上驗(yàn)證了四度分割[2]，他們得到Facebook上用戶的“度分離”為3.74,進(jìn)一步證實(shí)了“社交網(wǎng)絡(luò)拉近了不同國家、地區(qū)人與人之間的關(guān)系”這一論斷，但是文獻(xiàn)[2]只是驗(yàn)證了Facebook用戶間隔距離更小，并沒有對(duì)用戶之間的關(guān)系進(jìn)行定量分析，而且在線社交網(wǎng)絡(luò)中用戶互相關(guān)注就可以建立連接，這與現(xiàn)實(shí)社交網(wǎng)絡(luò)還是有一定區(qū)分。文獻(xiàn)[4]發(fā)現(xiàn)在科研合作者網(wǎng)絡(luò)DBLP中，學(xué)者在過去的15年里平均距離都穩(wěn)定在6附近，驗(yàn)證了在科研合作者網(wǎng)絡(luò)中也存在所謂的“六度分離”的現(xiàn)象。David Liben-Nowell等人在文獻(xiàn)[5]中研究了社交網(wǎng)絡(luò)中的鏈接預(yù)測問題。James Cheng等人在文獻(xiàn)[6]中研究了有向圖中k-hop可達(dá)性查詢的問題。

本文所要解決的問題就是在人際關(guān)系傳播中發(fā)現(xiàn)強(qiáng)關(guān)聯(lián)傳遞，更清楚地發(fā)現(xiàn)各類交際圈子，以梳理自己的人際關(guān)系網(wǎng)絡(luò)。考慮下面的例子：

假設(shè)，我想認(rèn)識(shí)曾在中央電視臺(tái)馬年春節(jié)聯(lián)歡晚會(huì)演唱的法國影星Madame Sophie Marceau（蘇菲瑪索），我可以通過我的導(dǎo)師A，他認(rèn)識(shí)大學(xué)校長B，B認(rèn)識(shí)教育部部長C，C又認(rèn)識(shí)中央電視臺(tái)臺(tái)長D，D在春晚邀請(qǐng)過Madame SophieMarceau，顯然他們是認(rèn)識(shí)的，這樣我可以通過A→B→C→D→Sophie Marceau。但是通過這條人際關(guān)系鏈聯(lián)系到Sophie Marceau可行嗎？我的導(dǎo)師A會(huì)幫我傳遞到校長B，可是B會(huì)輕易去麻煩C嗎？C又會(huì)拿這不靠譜的事情去動(dòng)用他的關(guān)系D嗎？盡管我與SophieMarceau之間僅僅隔了四個(gè)人，但三個(gè)環(huán)節(jié)都可能面臨無法逾越的阻力。如果換種方式，我的研究生舍友E，他的好朋友F在某大學(xué)讀書，F(xiàn)的同學(xué)G認(rèn)識(shí)劉一絲（劉歡女兒），劉歡曾在春晚和Sophie Marceau合作過，這條關(guān)系傳播雖然多了一跳，但每一步的可達(dá)性顯然要比上一種方法強(qiáng)，問題描述如圖1。

圖1 問題描述

傳統(tǒng)的六度空間考慮了人與人之間的聯(lián)系，但并沒有考慮社交網(wǎng)絡(luò)中關(guān)系傳遞的成本、阻尼和激勵(lì)等問題,也就是說未對(duì)社交網(wǎng)絡(luò)中的人際關(guān)系進(jìn)行強(qiáng)弱區(qū)分。兩個(gè)人僅僅是認(rèn)識(shí)，但較少聯(lián)系，他們之間的聯(lián)系可稱之為“微弱聯(lián)系”（Weak ties）。親人、配偶、關(guān)系密切的朋友可被認(rèn)為是強(qiáng)聯(lián)系。本文在六度空間理論的基礎(chǔ)上進(jìn)一步考慮個(gè)體關(guān)系的強(qiáng)弱，進(jìn)而可得在任意給定兩個(gè)陌生個(gè)體之間建立聯(lián)系的代價(jià)，以及建立聯(lián)系的低代價(jià)路徑發(fā)現(xiàn)算法，并將本文算法與傳統(tǒng)六度空間理論下最短路徑進(jìn)行比較，實(shí)驗(yàn)證明本文算法所得路徑代價(jià)更低。

1 社交網(wǎng)絡(luò)特征分析

大量研究發(fā)現(xiàn)，與許多其它種類的復(fù)雜網(wǎng)絡(luò)相似，社交網(wǎng)絡(luò)也具有一些結(jié)構(gòu)特性，例如，小世界現(xiàn)象、無標(biāo)度特性、冪律分布等。

1.1 社交網(wǎng)絡(luò)好友數(shù)量分析

美國社會(huì)學(xué)家格蘭諾維特認(rèn)為：無論你認(rèn)識(shí)多少人，那些強(qiáng)關(guān)系符合150法則，即80%的社會(huì)活動(dòng)可能被150個(gè)強(qiáng)關(guān)系所占有。以自己為中心，關(guān)系最近的人（密友）僅有3-5人，越外層關(guān)系越弱，但人數(shù)卻越多，如圖2[8]所示。

圖2 朋友關(guān)系親疏程度分布

本文對(duì)Gowalla社交網(wǎng)絡(luò)中用戶的平均好友數(shù)量進(jìn)行了統(tǒng)計(jì)，50%用戶的好友少于5個(gè)，70%用戶的好友少于10個(gè)，這也比較符合社交網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)有少量連邊，少數(shù)節(jié)點(diǎn)有大量連邊的現(xiàn)象。結(jié)果如圖3所示（圖中縱坐標(biāo)代表累計(jì)分布比例，橫坐標(biāo)代表每個(gè)用戶的好友數(shù)），曲線分布并沒有之前想象的那么陡峭。

圖3 Gowalla用戶好友數(shù)量統(tǒng)計(jì)

1.2 無標(biāo)度特性

自然界與社會(huì)生活中，我們感興趣的事件往往都會(huì)有一個(gè)典型的模型，比如說人的身高分布符合泊松分布（Poisson Distribution）。如圖4所示，大部分個(gè)體數(shù)據(jù)都會(huì)集中在網(wǎng)絡(luò)平均度＜k＞附近并達(dá)到峰值，而遠(yuǎn)離平均值的個(gè)體數(shù)按照指數(shù)衰減。另一些真實(shí)網(wǎng)絡(luò)的度分布則有很大不同，如財(cái)富分布、國家人口分布、社交網(wǎng)絡(luò)朋友數(shù)量分布等。這些網(wǎng)絡(luò)中個(gè)體間差異懸殊，大多數(shù)節(jié)點(diǎn)有少量連邊，少數(shù)節(jié)點(diǎn)有大量連邊，將這種節(jié)點(diǎn)度分布不存在有限衡量分布范圍的特征標(biāo)度的性質(zhì)稱為無標(biāo)度。Albert-Laszlo Barabasi和Reka Albert發(fā)現(xiàn)這類異質(zhì)網(wǎng)絡(luò)的度分布服從冪律分布（Pow?er-law Distribution）:P(k)∝Ck-r,r為冪律指數(shù)，將這種度分布形式的網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)，其網(wǎng)絡(luò)頂點(diǎn)的度所表現(xiàn)出來的冪律分布特征稱為無標(biāo)度特性。

圖4

重尾現(xiàn)象是無標(biāo)度網(wǎng)絡(luò)中冪律分布的重要特征，由圖4（b）可知，冪律分布不存在泊松分布一樣的峰值，曲線拖著一條長尾巴，在線社交網(wǎng)絡(luò)中的度分布普遍具有重尾現(xiàn)象。

Gowalla社交網(wǎng)絡(luò)中用戶節(jié)點(diǎn)的度分布統(tǒng)計(jì)結(jié)果如圖5所示，實(shí)驗(yàn)結(jié)果表明其好友度分布明顯符合冪律分布。

圖5 Gowalla社交網(wǎng)絡(luò)度分布

1.3 小世界現(xiàn)象

社交網(wǎng)絡(luò)具有顯著的小世界現(xiàn)象,網(wǎng)絡(luò)的平均路徑長度越短，小世界現(xiàn)象越明顯。相對(duì)于傳統(tǒng)復(fù)雜網(wǎng)絡(luò)，社交網(wǎng)絡(luò)具有更短的平均路徑長度和有效直徑。聚集系數(shù)和平均最短路徑一起能展示所謂的小世界效應(yīng)，有較短的平均路徑長度和較高的聚集系數(shù)的網(wǎng)絡(luò)就可以稱為小世界網(wǎng)絡(luò)。

2 社交網(wǎng)絡(luò)人際傳播模型

六度空間理論雖然揭示了人與人之間存在普遍聯(lián)系，但沒有對(duì)這種聯(lián)系作定量的分析。研究表明社會(huì)型社交網(wǎng)絡(luò)中的朋友關(guān)系存在強(qiáng)弱之分[12]，而那些強(qiáng)關(guān)系是個(gè)體時(shí)常能意識(shí)到的，往往對(duì)該個(gè)體有直接影響。我們會(huì)認(rèn)識(shí)成百上千的人，并且會(huì)根據(jù)某一屬性，對(duì)這些關(guān)系做出分類：比如由血緣關(guān)系而產(chǎn)生的親屬這一分類，且根據(jù)血緣的相似程度，可進(jìn)一步確定這種關(guān)系的強(qiáng)弱；根據(jù)地理位置的遠(yuǎn)近，可以劃分出同一國家，同鄉(xiāng)，同城，甚至是鄰居；還有因人類活動(dòng)而產(chǎn)生的同事、同學(xué)、朋友。然而，六度空間理論并沒有對(duì)這些關(guān)系種類做區(qū)分，亦沒有考慮關(guān)系之間的相對(duì)強(qiáng)弱。在實(shí)際生活中，若一個(gè)人想通過中間人認(rèn)識(shí)新朋友，往往會(huì)考慮到其中的成本，以此確定合適的中間人選，一般每個(gè)個(gè)體在選擇下一個(gè)節(jié)點(diǎn)時(shí)，往往會(huì)優(yōu)先考慮與自身關(guān)系密切的人，即強(qiáng)連接。強(qiáng)連接最有可能的是你目前工作同事，事業(yè)伙伴，親屬等，弱連接范圍更加廣泛，同學(xué)、朋友、親友等皆有可能。

2.1 人際傳播模型

由于社交關(guān)系數(shù)據(jù)涉及隱私問題，真實(shí)數(shù)據(jù)集難以獲取，所以本文根據(jù)獲取的社交網(wǎng)絡(luò)數(shù)據(jù)集，在社交網(wǎng)絡(luò)三方閉合和近鄰機(jī)制理論的基礎(chǔ)上，研究建立人際傳播模型。

（1）三方閉合

社會(huì)網(wǎng)絡(luò)發(fā)展的基本原則之一三方閉合（Triadic Closure）[14]認(rèn)為如果兩個(gè)未連接的用戶有共同的朋友，則他們成為朋友的可能性增加。

進(jìn)而，兩個(gè)節(jié)點(diǎn)的鄰居重疊程度越高，這兩個(gè)節(jié)點(diǎn)之間的關(guān)系越緊密。可以用Jaccard系數(shù)度量這種關(guān)系的緊密程度：

其中，Γ(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合,Γ(j)表示節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集合。

（2）近鄰機(jī)制

本文研究的近鄰機(jī)制主要是指地理鄰近。一般認(rèn)為，兩個(gè)人活動(dòng)的地理位置越接近，則二者相似度越大，他們更可能有相似的背景、年齡、興趣，因而他們之間的關(guān)系可能更密切。進(jìn)一步地，如果兩個(gè)人體活動(dòng)區(qū)域（每個(gè)人的活動(dòng)區(qū)域往往不止一個(gè)）的重合度越高，則他們的關(guān)系可能越密切。雖然計(jì)算機(jī)技術(shù)的發(fā)展促進(jìn)了交流，使地理的作用在減弱,但研究發(fā)現(xiàn)人們?nèi)匀悔呄蛴诤涂臻g近似的人聯(lián)系[15]。因此，本文假設(shè),地理位置越近，社交網(wǎng)絡(luò)用戶認(rèn)識(shí)或者成為朋友的可能性更大。

本文在實(shí)驗(yàn)中獲取了Gowalla用戶2008年4月到2010年10月之間的簽到記錄，根據(jù)這些簽到數(shù)據(jù)，對(duì)經(jīng)緯度按合適的網(wǎng)格劃分后，得到不同的區(qū)域，每個(gè)經(jīng)緯度會(huì)對(duì)應(yīng)到唯一的區(qū)域，計(jì)算每個(gè)用戶在不同區(qū)域簽到的次數(shù)，得到用戶的簽到向量，并根據(jù)這些簽到向量計(jì)算用戶之間位置的相似性，本文使用余弦相似度來度量：

具體地，分別用向量A=(A1,A2,…,An)和B=(B1,B2,…,Bn)來表示用戶ui和uj基于位置的簽到向量，用戶位置的相似性可表示為：

基于以上原則，本文建立人際傳播模型，選取合適的傳播個(gè)體，實(shí)現(xiàn)以較小的代價(jià)進(jìn)行人際傳播的目的。

2.2 社交網(wǎng)絡(luò)陌生個(gè)體聯(lián)系路徑

在實(shí)際生活中，兩個(gè)人的關(guān)系可能存在不對(duì)等的情況。考慮以下兩種情況：（1）領(lǐng)導(dǎo)與下屬的關(guān)系，從下屬到領(lǐng)導(dǎo)花費(fèi)的代價(jià)可能遠(yuǎn)高于從領(lǐng)導(dǎo)到下屬的代價(jià)；（2）微博、Twitter這類社交應(yīng)用，其中的聯(lián)系通過“關(guān)注”這一方式來建立，這類關(guān)系則是單向的，可能A可以從B獲取信息，而B可能獲取不到A的信息。

本文使用的Gowalla數(shù)據(jù)集中，邊均為雙向邊，即若存在邊A-＞B，則一定存在B-＞A這一條邊。實(shí)際上這種情況可以看作上面第二種情況的一個(gè)特例，本文結(jié)論同樣適用于上面第二種情況。對(duì)于上面第一條這種不對(duì)等關(guān)系，因相關(guān)數(shù)據(jù)難以獲取，因而本文不做考慮，即在后續(xù)工作中，均認(rèn)為A-＞B與B-＞A兩條邊代價(jià)一定相等。

根據(jù)之前介紹的社交網(wǎng)絡(luò)的傳播理論和原則，人際傳播在選擇路徑的下一跳時(shí)總是在鄰居節(jié)點(diǎn)中選取，在上一節(jié)定義的用戶ui和ui的關(guān)系強(qiáng)度score(ui,uj)的基礎(chǔ)上，我們只需考慮(ui,uj∈E)的情況，并且認(rèn)為傳播代價(jià)反比于用戶關(guān)系的強(qiáng)度，定義如下播代價(jià)函數(shù)cost：

|Γ(j)|表示下一跳節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集合的數(shù)量。

基于公式（4）確定網(wǎng)絡(luò)中每條邊的代價(jià)后，原始的社交網(wǎng)絡(luò)可轉(zhuǎn)化為帶權(quán)圖，而本文問題則轉(zhuǎn)化為在帶權(quán)圖求“最小代價(jià)路徑”問題，而不同于六度空間理論中的“最短路徑”問題。對(duì)該問題求解，可通過傳統(tǒng)的Dijkstra算法來進(jìn)行。然而考慮到社交網(wǎng)絡(luò)規(guī)模龐大，求解“最小代價(jià)路徑”代價(jià)過高，且在人際交往中，用戶往往并不追求代價(jià)絕對(duì)最小，而僅僅要求代價(jià)可接受，即選取合適的傳播個(gè)體，實(shí)現(xiàn)以較小的代價(jià)進(jìn)行人際傳播的目的。因而，本文在考慮共同好友和近鄰機(jī)制的基礎(chǔ)上，本文提出 DLCRP（Discover Low Cost and Reachable Path）算法，具體實(shí)現(xiàn)如算法1，對(duì)任意兩個(gè)陌生個(gè)體可以找到一條低代價(jià)可達(dá)路徑。

算法 1：Discover Low Costand Reachable Path

輸入：好友關(guān)系網(wǎng)絡(luò)FN，起始節(jié)點(diǎn)s，目標(biāo)節(jié)點(diǎn)d，每一跳候選節(jié)點(diǎn)個(gè)數(shù)k

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集

Gowalla是一個(gè)基于位置的社會(huì)型社交網(wǎng)絡(luò)平臺(tái)。本文獲取了Gowalla數(shù)據(jù)集中完整的社交關(guān)系數(shù)據(jù),共有196591個(gè)用戶，950327條社交關(guān)系，6442890條2008年4月到2010年10月的簽到記錄，簽到記錄中包含用戶簽到的具體時(shí)間，經(jīng)緯度信息。

3.2 實(shí)驗(yàn)結(jié)果

離心率（Eccentricity），是指從一個(gè)給定起始節(jié)點(diǎn)到距其最遠(yuǎn)節(jié)點(diǎn)的距離。圖6給出了Gowalla社交網(wǎng)絡(luò)用戶的離心率分布，從下圖可以看出Gowalla社交網(wǎng)絡(luò)用戶的離心率主要集中在10附近。

圖6 Gowalla用戶離心率

圖7 傳播代價(jià)對(duì)比

圖7為進(jìn)行10次實(shí)驗(yàn)后的傳播代價(jià)對(duì)比結(jié)果，每次實(shí)驗(yàn)隨機(jī)生成1000對(duì)用戶，然后計(jì)算生成1000對(duì)用戶人際傳播路徑所需要的平均傳播代價(jià)。從對(duì)比實(shí)驗(yàn)結(jié)果可看出，整體上DLCRP算法要優(yōu)于BFS，并且可以看出在發(fā)現(xiàn)路徑的代價(jià)相對(duì)較小時(shí)，DLCRP的優(yōu)勢并不是很明顯，但當(dāng)尋找路徑的代價(jià)比較大時(shí)，DL?CRP就能明顯表現(xiàn)出其優(yōu)勢。

隨機(jī)選取1000對(duì)用戶節(jié)點(diǎn)，兩種算法發(fā)現(xiàn)的路徑長度統(tǒng)計(jì)結(jié)果如圖8所示?？梢钥闯觯啾扔贒LCRP算法，BFS算法發(fā)現(xiàn)的路徑長度整體要較低,廣度優(yōu)先搜索算法在不考慮路徑代價(jià)的情況下總能找出跳數(shù)最短的路徑。并且路徑長度主要集中2附近，也側(cè)面反映了Gowalla網(wǎng)絡(luò)的小世界特性。相比之下，本文提出的算法在考慮低代價(jià)的情況下路徑長度主要集中在5附近，這也側(cè)面說明了最短路徑不一定是最佳路徑。

圖8 路徑長度對(duì)比

圖9 運(yùn)行時(shí)間

圖9為隨機(jī)選取100到600對(duì)用戶節(jié)點(diǎn)，兩種算法發(fā)現(xiàn)路徑的運(yùn)行時(shí)間的對(duì)比結(jié)果，DLCRP雖然時(shí)間開銷上比廣度優(yōu)先搜索大，但從實(shí)驗(yàn)結(jié)果可以看出其時(shí)間開銷基本呈線性增長，算法的可擴(kuò)展性也很強(qiáng)。

通過以上實(shí)驗(yàn)結(jié)果可以觀察到，DLCRP算法雖然在傳播代價(jià)上優(yōu)于廣度優(yōu)先搜索算法，但在平均路徑的長度和時(shí)間開銷上卻劣于BFS，正如天下“沒有免費(fèi)的午餐”的定理（No Free Lunch THeorem），任何一種學(xué)習(xí)算法必有其偏好，在某些方面表現(xiàn)好，在另一些方面卻可能不盡如人意。本文提出的模型和算大主要是解決社交網(wǎng)絡(luò)中人際傳播低代價(jià)的問題。

4 結(jié)語

本文在分析社交網(wǎng)絡(luò)結(jié)構(gòu)特征及特性的基礎(chǔ)上，根據(jù)社交網(wǎng)絡(luò)中的三方閉合和近鄰機(jī)制建立人際傳播模型，并在模型基礎(chǔ)上進(jìn)行陌生個(gè)體之間的低代價(jià)可達(dá)路徑發(fā)現(xiàn)，實(shí)驗(yàn)結(jié)果表明本文提出的DLCRP算法在陌生個(gè)體之間路徑發(fā)現(xiàn)時(shí)的傳播代價(jià)明顯低于BFS算法。本文在三方閉合原則的基礎(chǔ)上只考慮了朋友的朋友是朋友，下一步工作還可以進(jìn)行更有意思的考慮，例如三角關(guān)系中“朋友的敵人是敵人”、“敵人的敵人是朋友”等。

參考文獻(xiàn)：

[1]Travers J,Milgram S.An Experimental Study of the Small World Problem[J].Sociometry,1969:425-443.

[2]Backstrom L,BoldiP,RosaM,etal.Four Degrees of Separation[C].Proceedings of the 4th Annual ACMWeb Science Conference.ACM,2012:33-42.

[3]汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].清華大學(xué)出版社,2006.

[4]Elmacioglu E,Lee D.On Six Degrees of Separation in DBLP-DB and More[J].ACM SIGMOD Record,2005,34（2）:33-40.

[5]Liben NowellD,Kleinberg J.The Link Prediction Problem for Social Networks[J].Journal of the American Society for Information Science and Technology,2007,58（7）:1019-1031.

[6]Cheng J,Shang Z,Cheng H,etal.K-reach:Who is in Your Small World[J].Proceedings of the VLDB Endowment,2012,5（11）:1292-1303.

[7]WUXin-dong,LIYi,LILei.Influence Analysis of Online Social Networks[J].Chinese Journal of Computers 2014,37（4）:735-752.

[8]姜開達(dá).社交網(wǎng)絡(luò)中陌生個(gè)體間人際關(guān)系形態(tài)研究[D].上海交通大學(xué),2013.

[9]luo J.Analysisof Social Network[M].Beijing:Social Sciences Academic Press,2005:152-168

[10]Watts D.J，Strogatz S.H.Collective Dynamics of'Small-World'Networks[J].Nature,1998:440-442.

[11]Freeman LC.Centrality in Social Networks Conceptual Clarification[J].Social Networks,1978,1（3）:215-239.

[12]Newman M E J.A Measure of Betweenness Centrality Based on Random Walks[J].Socialnet works,2005,27（1）:39-54.

[13]Xiang R,Neville J,RogatiM.Modeling Relationship Strength in Online Social Networks[C].Proceedings of the 19th International Conference on World Wide Web.ACM,2010:981-990.

[14]X Shi,LA Adamic,M JStrauss.Networks of Strong Ties.Physicia A:Statistical Mechaics and its Applications,2007,387（1）:33～47.

[15]俞琰.社交網(wǎng)絡(luò)朋友推薦算法研究[D].南京航空航天大學(xué),2014.